1-13hit |
Nuttapong ATTRAPADUNG Hideki IMAI
We present a new variant of Attribute based encryption (ABE) called Dual-Policy ABE. Basically, it is a conjunctively combined scheme between Key-Policy and Ciphertext-Policy ABE, the only two previous types of ABE. Dual-Policy ABE allows simultaneously two access control mechanisms over encrypted data: one involves policies over objective attributes ascribed to data and the other involves policies over subjective attributes ascribed to user credentials. The previous two types of ABE can only allow either functionality above one at a time.
Kotoko YAMADA Nuttapong ATTRAPADUNG Keita EMURA Goichiro HANAOKA Keisuke TANAKA
Attribute-based encryption (ABE), a cryptographic primitive, realizes fine-grained access control. Because of its attractive functionality, many systems based on ABE have been constructed to date. In such cryptographic systems, revocation functionality is indispensable to handle withdrawal of users, secret key exposure, and others. Although many ABE schemes with various functionalities have been proposed, only a few of these are revocable ABE (RABE). In this paper, we propose two generic constructions of RABE from ABE. Our first construction employs the pair encoding framework (Attrapadung, EUROCRYPT 2014), and combines identity-based revocation and ABE via the generic conjunctive conversion of Attrapadung and Yamada (CT-RSA 2015). Our second construction converts ABE to RABE directly when ABE supports Boolean formulae. Because our constructions preserve functionalities of the underlying ABE, we can instantiate various fully secure RABE schemes for the first time, e.g., supporting regular languages, with unbounded attribute size and policy structure, and with constant-size ciphertext and secret key.
Nuttapong ATTRAPADUNG Goichiro HANAOKA Shinsaku KIYOMOTO Tomoaki MIMOTO Jacob C. N. SCHULDT
Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols. We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.
Yuji UNAGAMI Natsume MATSUZAKI Shota YAMADA Nuttapong ATTRAPADUNG Takahiro MATSUDA Goichiro HANAOKA
In this paper, we propose a similarity searchable encryption in the symmetric key setting for the weighted Euclidean distance, by extending the functional encryption scheme for inner product proposed by Bishop et al. [4]. Our scheme performs predetermined encoding independently of vectors x and y, and it obtains the weighted Euclidean distance between the two vectors while they remain encrypted.
Takahiro MATSUDA Nuttapong ATTRAPADUNG Goichiro HANAOKA Kanta MATSUURA Hideki IMAI
Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.
Nuttapong ATTRAPADUNG Goichiro HANAOKA Takato HIRANO Yutaka KAWAI Yoshihiro KOSEKI Jacob C. N. SCHULDT
In this paper, we put forward the notion of a token-based multi-input functional encryption (token-based MIFE) scheme - a notion intended to give encryptors a mechanism to control the decryption of encrypted messages, by extending the encryption and decryption algorithms to additionally use tokens. The basic idea is that a decryptor must hold an appropriate decryption token in addition to his secrete key, to be able to decrypt. This type of scheme can address security concerns potentially arising in applications of functional encryption aimed at addressing the problem of privacy preserving data analysis. We firstly formalize token-based MIFE, and then provide two basic schemes; both are based on an ordinary MIFE scheme, but the first additionally makes use of a public key encryption scheme, whereas the second makes use of a pseudorandom function (PRF). Lastly, we extend the latter construction to allow decryption tokens to be restricted to specified set of encryptions, even if all encryptions have been done using the same encryption token. This is achieved by using a constrained PRF.
Naohisa NISHIDA Tatsumi OBA Yuji UNAGAMI Jason PAUL CRUZ Naoto YANAI Tadanori TERUYA Nuttapong ATTRAPADUNG Takahiro MATSUDA Goichiro HANAOKA
Machine learning models inherently memorize significant amounts of information, and thus hiding not only prediction processes but also trained models, i.e., model obliviousness, is desirable in the cloud setting. Several works achieved model obliviousness with the MNIST dataset, but datasets that include complicated samples, e.g., CIFAR-10 and CIFAR-100, are also used in actual applications, such as face recognition. Secret sharing-based secure prediction for CIFAR-10 is difficult to achieve. When a deep layer architecture such as CNN is used, the calculation error when performing secret calculation becomes large and the accuracy deteriorates. In addition, if detailed calculations are performed to improve accuracy, a large amount of calculation is required. Therefore, even if the conventional method is applied to CNN as it is, good results as described in the paper cannot be obtained. In this paper, we propose two approaches to solve this problem. Firstly, we propose a new protocol named Batch-normalizedActivation that combines BatchNormalization and Activation. Since BatchNormalization includes real number operations, when performing secret calculation, parameters must be converted into integers, which causes a calculation error and decrease accuracy. By using our protocol, calculation errors can be eliminated, and accuracy degradation can be eliminated. Further, the processing is simplified, and the amount of calculation is reduced. Secondly, we explore a secret computation friendly and high accuracy architecture. Related works use a low-accuracy, simple architecture, but in reality, a high accuracy architecture should be used. Therefore, we also explored a high accuracy architecture for the CIFAR10 dataset. Our proposed protocol can compute prediction of CIFAR-10 within 15.05 seconds with 87.36% accuracy while providing model obliviousness.
Hiraku MORITA Nuttapong ATTRAPADUNG Tadanori TERUYA Satsuya OHATA Koji NUIDA Goichiro HANAOKA
We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of the result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P'17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise, servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgå rd et al. (TCC'06) and Nishide and Ohta (PKC'07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.
Nuttapong ATTRAPADUNG Hideki IMAI
We present generic frameworks for constructing efficient broadcast encryption schemes in the subset-cover paradigm, introduced by Naor et al., based on various key derivation techniques. Our frameworks characterize any instantiation completely to its underlying graph decompositions, which are purely combinatorial in nature. These abstract away the security of each instantiated scheme to be guaranteed by the generic one of the frameworks; thus, give flexibilities in designing schemes. Behind these, we present new techniques based on (trapdoor) RSA accumulators utilized to obtain practical performances. We then give some efficient instantiations from the frameworks, via a new structure called subset-incremental-chain. Our first construction improves the currently best schemes, including the one proposed by Goodrich et al., without any further assumptions (only pseudo-random generators are used) by some factors. The second instantiation, which is the most efficient, is instantiated based on RSA and directly improves the first scheme. Its ciphertext length is of order O(r), the key size is O(1), and its computational cost is O(n1/klog2 n) for any (arbitrary large) constant k; where r and n are the number of revoked users and all users respectively. To the best of our knowledge, this is the first explicit collusion-secure scheme in the literature that achieves both ciphertext size and key size independent of n simultaneously while keeping all other costs efficient, in particular, sub-linear in n. The third scheme improves Gentry and Ramzan's scheme, which itself is more efficient than the above schemes in the aspect of asymptotic computational cost.
Nuttapong ATTRAPADUNG Goichiro HANAOKA Shota YAMADA
Identity-based encryption (IBE) is an advanced form of public key encryption and one of the most important cryptographic primitives. Of the many constructions of IBE schemes, the one proposed by Boneh and Boyen (in Eurocrypt 2004) is quite important from both practical and theoretical points of view. The scheme was standardized as IEEE P1363.3 and is the basis for many subsequent constructions. In this paper, we investigate its multi-challenge security, which means that an adversary is allowed to query challenge ciphertexts multiple times rather than only once. Since single-challenge security implies multi-challenge security, and since Boneh and Boyen provided a security proof for the scheme in the single-challenge setting, the scheme is also secure in the multi-challenge setting. However, this reduction results in a large security loss. Instead, we give tight security reduction for the scheme in the multi-challenge setting. Our reduction is tight even if the number of challenge queries is not fixed in advance (that is, the queries are unbounded). Unfortunately, we are only able to prove the security in a selective setting and rely on a non-standard parameterized assumption. Nevertheless, we believe that our new security proof is of interest and provides new insight into the security of the Boneh-Boyen IBE scheme.
Nuttapong ATTRAPADUNG Jun FURUKAWA Takeshi GOMI Goichiro HANAOKA Hideki IMAI Rui ZHANG
In this paper, we present an efficient variant of the Boneh-Franklin scheme that achieves a tight security reduction. Our scheme is basically an IBE scheme under two keys, one of which is randomly chosen and given to the user. It can be viewed as a continuation of an idea introduced by Katz and Wang; however, unlike the Katz-Wang variant, our scheme is quite efficient, as its ciphertext size is roughly comparable to that of the original full Boneh-Franklin scheme. The security of our scheme can be based on either the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) assumptions.
Nuttapong ATTRAPADUNG Goichiro HANAOKA Kazuto OGAWA Go OHTAKE Hajime WATANABE Shota YAMADA
Attribute-Based Encryption (ABE) is an advanced form of public-key encryption where access control mechanisms based on attributes and policies are possible. In conventional ABE, attributes are specified as strings. However, there are certain applications where it is useful to specify attributes as numerical values and consider a predicate that determines if a certain numerical range would include a certain value. Examples of these types of attributes include time, position coordinate, person's age, rank, identity, and so on. In this paper, we introduce ABE for boolean formulae over Range Membership (ABE-RM). We show generic methods to convert conventional ABE to ABE-RM. Our generic conversions are efficient as they introduce only logarithmic overheads (in key and ciphertext sizes), as opposed to trivial methods, which would pose linear overheads. By applying our conversion to previous ABE schemes, we obtain new efficient and expressive ABE-RM schemes. Previous works that considered ABE with range attributes are specific and can only deal with either a single relation of range membership (Paterson and Quaglia at SCN'10, and Kasamatsu et al. at SCN'12), or limited classes of policies, namely, only AND-gates of range attributes (Shi et al. at IEEE S&P'07, and some subsequent work). Our schemes are generic and can deal with expressive boolean formulae.
Arisa FUJII Go OHTAKE Goichiro HANAOKA Nuttapong ATTRAPADUNG Hajime WATANABE Kazuto OGAWA Hideki IMAI
Broadcasters transmit TV programs and often need to transmit an individual message, e.g. an individual contract, to each user. The programs have to be encrypted in order to protect the copyright and the individual messages have to be encrypted to preserve the privacy of users. For these purposes, broadcasters transmit not only encrypted content but also encrypted personalized messages to individual users. Current broadcasting services employ an inefficient encryption scheme based on a symmetric key. Recently, several broadcast encryption schemes using a public key have been proposed in which the broadcaster encrypts a message for some subset S of users with a public key and any user in S can decrypt the broadcast with his/her private key. However, it is difficult to encrypt a personalized message and transmit it to every user efficiently. In this paper, we propose a broadcast encryption scheme that has a personalized message encryption function. We show that our scheme is efficient in terms of the ciphertext size.