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.
Verifiable Privacy-Preserving Data Aggregation Protocols YASUDA, Satoshi; KOSEKI, Yoshihiro; SAKAI, Yusuke ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2020/01/01, 2020-1-1, 20200101, Letnik:
E103.A, Številka:
1
Journal Article
Recenzirano
Homomorphic encryption allows computation over encrypted data, and can be used for delegating computation: data providers encrypt their data and send them to an aggregator, who can then perform ...computation over the encrypted data on behalf of a client, without the underlying data being exposed to the aggregator. However, since the aggregator is merely a third party, it may be malicious, and in particular, may submit an incorrect aggregation result to the receiver. Ohara et al. (APKC2014) studied secure aggregation of time-series data while enabling the correctness of aggregation to be verified. However, they only provided a concrete construction in the smart metering system and only gave an intuitive argument of security. In this paper, we define verifiable homomorphic encryption (VHE) which generalizes their scheme, and introduce formal security definitions. Further, we formally prove that Ohara et al.'s VHE scheme satisfies our proposed security definitions.
Card-Based Protocols Using Regular Polygon Cards SHINAGAWA, Kazumasa; MIZUKI, Takaaki; SCHULDT, Jacob C.N. ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
01/2017, Letnik:
E100.A, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Cryptographic protocols enable participating parties to compute any function of their inputs without leaking any information beyond the output. A card-based protocol is a cryptographic protocol ...implemented by physical cards. In this paper, for constructing protocols with small numbers of shuffles, we introduce a new type of cards, regular polygon cards, and a new protocol, oblivious conversion. Using our cards, we construct an addition protocol on non-binary inputs with only one shuffle and two cards. Furthermore, using our oblivious conversion protocol, we construct the first protocol for general functions in which the number of shuffles is linear in the number of inputs.
Let us consider a situation where someone wants to encrypt his/her will on an existing blockchain, e.g. Bitcoin, and allow an encrypted will to be decryptable only if designated members work ...together. At a first glance, such a property seems to be easily provided by using conventional threshold encryption. However, this idea cannot be straightforwardly implemented since key pairs for an encryption mechanism is additionally required. In this paper, we propose a new threshold encryption scheme in which key pairs for ECDSA that are already used in the Bitcoin protocol can be directly used as they are. Namely, a unique key pair can be simultaneously used for both ECDSA and our threshold encryption scheme without losing security. Furthermore, we implemented our scheme on the Bitcoin regtest network, and show that it is fairly practical. For example, the execution time of the encryption algorithm Enc (resp., the threshold decryption algorithm Dec) is 0.2sec. (resp., 0.3sec.), and the total time is just only 3sec. including all the cryptographic processes and network communications for a typical parameter setting. Also, we discuss several applications of our threshold encryption scheme in detail: Claiming priority of intellectual property, sealed-bid auction, lottery, and coin tossing service.
Very recently, Hofheinz, Jager, and Kiltz proposed novel digital signature schemes that yield significantly shorter signatures. However, in contrast to such remarkably short signatures, the size of ...the public key is still huge, making it desirable for this to be reduced. In this paper, we present a two-dimensional representation technique for cover free families, and show that this technique is quite useful for reducing the public key size in various cryptographic primitives. As immediate applications, we give constructions of the k-resilient identity-based key encapsulation mechanism (KEM), q-bounded CCA-secure KEM, and m-time signature which yield shorter public keys than previous schemes. Moreover, by applying our technique, we propose a (fully-fledged) signature scheme with the public key approximately 1/100 the size of that in the Hofheinz-Jager-Kiltz scheme with the same signature size and security assumption.
Recently Cash, Kiltz, and Shoup 13 showed a variant of the Cramer-Shoup (CS) scheme 14 whose chosen-ciphertext (CCA) security relies on the computational Diffie-Hellman (CDH) assumption. The cost for ...this high security is that the size of ciphertexts is much longer than the CS scheme (which is based on the decisional Diffie-Hellman assumption). In this paper, we show how to achieve CCA-security under the CDH assumption without increasing the size of ciphertexts. We also show a more efficient scheme under the hashed Diffie-Hellman assumption.
Both of our schemes are based on a certain broadcast encryption (BE) scheme while the Cash-Kiltz-Shoup scheme is based on the Twin DH problem. Of independent interest, we also show a generic method of constructing CCA-secure PKE schemes from BE schemes.
A New Combiner for Key Encapsulation Mechanisms HANAOKA, Goichiro; MATSUDA, Takahiro; SCHULDT, Jacob C. N.
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
12/2019, Letnik:
E102.A, Številka:
12
Journal Article
Recenzirano
Key encapsulation mechanism (KEM) combiners, recently formalized by Giacon, Heuer, and Poettering (PKC'18), enable hedging against insecure KEMs or weak parameter choices by combining ingredient KEMs ...into a single KEM that remains secure assuming just one of the underlying ingredient KEMs is secure. This seems particularly relevant when considering quantum-resistant KEMs which are often based on arguably less well-understood hardness assumptions and parameter choices. We propose a new simple KEM combiner based on a one-time secure message authentication code (MAC) and two-time correlated input secure hash. Instantiating the correlated input secure hash with a t-wise independent hash for an appropriate value of t, yields a KEM combiner based on a strictly weaker additional primitive than the standard model construction of Giaon et al. and furthermore removes the need to do n full passes over the encapsulation, where n is the number of ingredient KEMs, which Giacon et al. highlight as a disadvantage of their scheme. However, unlike Giacon et al., our construction requires the public key of the combined KEM to include a hash key, and furthermore requires a MAC tag to be added to the encapsulation of the combined KEM.
Attribute-Based Encryption for Range Attributes ATTRAPADUNG, Nuttapong; HANAOKA, Goichiro; OGAWA, Kazuto ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
09/2018, Letnik:
E101.A, Številka:
9
Journal Article
Recenzirano
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.
In this paper we propose generic conversions for transforming a chosen-plaintext (CPA) secure attribute-based encryption (ABE) to a chosen-ciphertext (CCA) secure ABE. The only known generic ...conversion, to the best of our knowledge, was presented by Goyal et al. in ACM-CCS 2006, which itself subsumes the well-known IBE-to-PKE conversion by Canetti, Halevi, and Katz proposed in Eurocrypt 2004. The method by Goyal et al. has some restrictions that it assumes the delegatability of the original ABE and can deal only with the key-policy type of ABE with large attribute universe. In contrast, our methodology is applicable also to those ABE schemes without known delegatability. Furthermore, it works for both key-policy or ciphertext-policy flavors of ABE and can deal with both small and large universe scheme. More precisely, our method assumes only either delegatability or a newly introduced property called verifiability of ABE. We then exhaustively check the verifiability of existing ABE schemes and found that most of them satisfy such a property, hence CCA-secure versions of these schemes can be obtained automatically.
PDF
