A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins. A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC ’96). The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext ex-pansion that is logarithmic in the message length. Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size Õ(nλ) where n is the message length and λ is the security parameter. The second message consists of a ciphertext of size O(n logn+ λ). The security of our scheme is proved based on the Φ-hiding problem.
A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins. A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC ’96). The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext ex-pansion that is logarithmic in the message length. Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size Õ(nλ) where n is the message length and λ is the security parameter. The second message consists of a ciphertext of size O(n logn+ λ). The security of our scheme is proved based on the Φ-hiding problem.
Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where “hackers ” actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that is dependent both on the circuit size and the security parameter. In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, which we believe is the right security notion in the two-party setting. We study the feasibility of (1) NCE with constant number of public key operations for large message spaces. (2) Oblivious transfer with constant number of public key operations for large sender’s input spaces, and (3) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions, while this is not known for fully adaptive security (where both parties may get corrupted).
Non-committing encryption enables the construction of multiparty computation protocols secure against an adaptive adversary in the computational setting where private channels between players are not assumed. While any non-committing encryption scheme must be secure in the ordinary semantic sense, the converse is not necessarily true. We propose a construction of non-committing encryption that can be based on any public key system which is secure in the ordinary sense and which has an extra property we call simulatability. The construction contains an earlier proposed scheme by Beaver based on the Die-Hellman problem as a special case, and we propose another implementation based on RSA. In a more general setting, our construction can be based on any collection of trapdoor one-way permutations with a certain simulatability property. This offers a considerable efficiency improvement over the first non-committing encryption scheme proposed by Canetti et al. Finally, at some loss of efficiency, our scheme can be based on general collections of trapdoor one-way permutations without the simulatability assumption, and without the common domain assumption of Canetti et al.
Secure multi-party computation (MPC) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation.
This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity.
The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet.
With the focus on adaptive security and round efficiency, we obtain the following results:
(1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary.
(2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00].
We also show that the primitive can be constructed based on hardness of factoring.
(3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary.
(4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.
Public-key encryption is a cryptographic primitive used for establishing a secure channel between two parties.Depending on the situation and purpose, public-key encryption schemes must satisfy appropriate security requirements.Non-committing encryption (NCE) is a public-key encryption scheme that satisfies a security notion essential to establish a secure channel in adaptively secure multi-party computation (MPC) protocols.Informally, NCE can generate a dummy ciphertext.The dummy ciphertext is indistinguishable from the real ciphertext.Moreover, we can explain the dummy ciphertext as encryption of an arbitrary message by producing consistent randomness.It has been a challenge in the theory of adaptively secure MPC to find an NCE scheme with small ciphertext expansion (required ciphertext length per bit of message).This thesis proposes the first NCE schemes with constant ciphertext expansion in the standard model (i.e., without assuming the randomness used in the cryptosystem can be securely erased or use of the random oracle).We show two instantiations of the scheme, one from the Decisional Diffie-Hellman (DDH) problem and another from the Learning with Errors (LWE) problem.Before constructing the constant ciphertext expansion scheme, we demonstrate the new approach to constructing NCE through the construction of a simpler NCE scheme based on obliviously samplable key-encapsulation mechanism (KEM).The ciphertext expansion of this simpler scheme is O(λ) for security parameter λ.In detail, we use KEM to construct a weak NCE scheme with O(λ) ciphertext expansion.Weak NCE is NCE where its correctness and security requirements are weakened.Then weak NCE is amplified to a full-fledged NCE scheme using an information theoretical primitive called wiretap codes.This amplification increases the cipher text expansion only by a constant factor.The constant ciphertext expansion scheme is obtained by using a primitive called obliviously samplable chameleon encryption, instead of KEM in the above construction.We show instantiations of obliviously samplable chameleon encryption based on the DDH and the LWE problems.
Abstract. Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of alreadycorrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarilymany senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks. 1
Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.