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.
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.
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).
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.
Two main goals of modern cryptography are to identify the minimal assumptions necessary to construct secure cryptographic primitives as well as to construct secure protocols in strong and realistic adversarial models. In this thesis, we address both of these fundamental questions. In the first part of this thesis, we present results on the black-box complexity of two basic cryptographic primitives: non-malleable encryption and optimally-fair coin tossing. Black-box reductions are reductions in which both the underlying primitive as well as the adversary are accessed only in an input-output (or black-box) manner. Most known cryptographic reductions are black-box. Moreover, black-box reductions are typically more efficient than non-black-box reductions. Thus, the black-box complexity of cryptographic primitives is a meaningful and important area of study which allows us to gain insight into the primitive. We study the black box complexity of non-malleable encryption and optimally-fair coin tossing, showing a positive result for the former and a negative one for the latter. Non-malleable encryption is a strong security notion for public-key encryption, guaranteeing that it is impossible to "maul" a ciphertext of a message m into a ciphertext of a related message. This security guarantee is essential for many applications such as auctions. We show how to transform, in a black-box manner, any public-key encryption scheme satisfying a weak form of security, semantic security, to a scheme satisfying non-malleability. Coin tossing is perhaps the most basic cryptographic primitive, allowing two distrustful parties to flip a coin whose outcome is 0 or 1 with probability 1/2. A fair coin tossing protocol is one in which the outputted bit is unbiased, even in the case where one of the parties may abort early. However, in the setting where parties may abort early, there is always a strategy for one of the parties to impose bias of Omega(1/r) in an r-round protocol. Thus, achieving bias of O(1/r) in r rounds is optimal, and it was recently shown that optimally-fair coin tossing can be achieved via a black-box reduction to oblivious transfer. We show that it cannot be achieved via a black-box reduction to one-way function, unless the number of rounds is at least Omega(n/log n), where n is the input/output length of the one-way function. In the second part of this thesis, we present protocols for multiparty computation (MPC) in the Universal Composability (UC) model that are secure against malicious, adaptive adversaries. In the standard model, security is only guaranteed in a stand-alone setting; however, nothing is guaranteed when multiple protocols are arbitrarily composed. In contrast, the UC model, introduced by (Canetti, 2000), considers the execution of an unbounded number of concurrent protocols, in an arbitrary, and adversarially controlled network environment. Another drawback of the standard model is that the adversary must decide which parties to corrupt before the execution of the protocol commences. A more realistic model allows the adversary to adaptively choose which parties to corrupt based on its evolving view during the protocol. In our work we consider the the adaptive UC model, which combines these two security requirements by allowing both arbitrary composition of protocols and adaptive corruption of parties. In our first result, we introduce an improved, efficient construction of non-committing encryption (NCE) with optimal round complexity, from a weaker primitive we introduce called trapdoor-simulatable public key encryption (PKE). NCE is a basic primitive necessary to construct protocols secure under adaptive corruptions and in particular, is used to construct oblivious transfer (OT) protocols secure against semi-honest, adaptive adversaries. Additionally, we show how to realize trapdoor-simulatable PKE from hardness of factoring Blum integers, thus achieving the first construction of NCE from hardness of factoring. In our second result, we present a compiler for transforming an OT protocol secure against a semi-honest, adaptive adversary into one that is secure against a malicious, adaptive adversary. Our compiler achieves security in the UC model, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. Combining our two results with the work of (Ishai et al., 2008), we obtain the first black-box construction of UC and adaptively secure MPC from trapdoor-simulatable PKE and the ideal commitment functionality.
The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.
Nielsen (CRYPTO 2002) demonstrated that constructing a non-committing encryption (NCE) scheme for an unbounded number of messages is impossible in both the standard model and the non-programmable random oracle model, underscoring fundamental barriers to achieving NCE within conventional cryptographic frameworks. However, he circumvented this impossibility in the programmable random oracle model by presenting a construction based on trapdoor functions, exploiting the oracle’s programmability to enable ciphertext equivocation. In this work, we analyze Nielsen’s construction in the quantum random oracle model (QROM), where quantum adversaries can query the oracle in superposition, and examine whether its security remains intact in this significantly stronger setting.
Non-committing encryption achieved only semantic security,in contrast,applications often require security against chosen ciphertext attacks.A main ingredient in the previous adaptive universally composable(UC)oblivious transfer protocols are non-committing encryptions.the previous proposals are not UC secure against adaptive adversaries in the so-called non-erase model.A new UC secure oblivious transfer protocols were proposed and schemes utilize two primitives of the verifiably smooth projective hashing and deniable encryption as constructed by.the double trapdoor decryption mechanism based on trapdoor commitment.Our construction is based on the decisional composite residuosity in common reference string (CRS) model.We constructed a two-message(1-round) string oblivious transfer protocol,which improves computational efficient that supports message spaces of size exponential and save O(n)-1 rounds communications efficient than bit-OT protocols.