Non-Malleable Commitments And Non-Malleable Zero-Knowledge

A cryptographic protocol is a communication protocol that uses cryptographic techniques. It is a basic factor in the design of secure information systems. With the recent development of Inter-net applications, it has become a main and important research direction to analyze the security of cryptographic protocols. Usually, cryptographic protocols are run over the Internet or distributed systems, where an adversary is able to intercept, modify and delete a message, and impersonate and manipulate a party. Among all these attacks, man-in-the-middle attack is the most common one which covers most of the specific attacks. Commitment schemes and zero-knowledge protocols are two basic cryptographic protocols, which can be applied in many other cryptographic proto-cols and advanced secure systems, such as coin-tossing protocol, secure two-party computation, secure multi-party computation, encryption schemes, signature schemes, identification schemes, key exchange protocol, secret sharing schemes, and e-voting protocols and so on. Recent research direction related with the two primitives mainly focuses on security analysis under man-in-the-middle attacks, which includes efficiency improvement, security enhancements and complexity assumptions reduction. If a commitment scheme or a zero-knowledge protocol is secure against man-in-the-middle attacks, then we call it non-malleable.In the literature, according to the practical security requirement, there are two kinds of non-malleability notions for commitment schemes. One is called non-malleability with respect to com-mitment, i.e., an adversary can not transform the commitment of a value into a commitment of a related value. The other one is called non-malleability with respect to opening, i.e., an adver-sary cannot construct a commitment from a given one, such that after having seen the opening of the original commitment, the adversary is able to correctly open his commitment to a related value. The above two non-malleability notions capture different security property of commitment schemes required by practical applications. Our goal of this research is to consider the security of commitment schemes against man-in-the-middle attacks, from the aspects of efficiency and the hardness assumptions, respectively. On the one hand, we want to design more secure schemes from weaker assumptions. On the other hand, we try to design more efficient schemes from stronger as-sumptions. Regarding non-malleable zero-knowledge protocols, we intend to protect the interests of the verifier of a zero-knowledge protocol to the large extent when an adversary can mount man-in-the-middle attacks. We address the problem of designing constant-round zero-knowledge protocols in the plain model that enjoy simultaneously non-malleability (i.e., security against man-in-the-middle attacks) and unconditional soundness (i.e., they are proof systems).The main results of the thesis are the following:1. The design and analysis of statistically hiding commitment schemes preventing man-in-the-middle attacks. We give a construction of non-malleable statistically hiding commitment scheme based on the existence of one-way functions. Actually, we give an unconditional transformation of non-malleable commitment schemes from any statistically hiding ones. By Impagliazzo and Luby (FOCS'89), the existence of statistically hiding commitment scheme implies the existence of one-way functions and the above result is tight. The proof of security requires only the use of black-box techniques. Compared with our work, previous results assume the existence of collision-resistant hash functions (which is a stronger assumption compared with ours) or rely on non-black-box techniques (which has high communication complexity).2. The design and analysis of statistically hiding commitment schemes preventing concurrent man-in-the-middle attacks. We present a modular construction of non-malleable statistically hiding commitment schemes that retain its properties when concurrently executed a polyno-mial number of times. Our protocol is based on a statistically hiding commitment scheme and a concurrent non-malleable zero-knowledge protocol for all of N P. Our result is achieved in the plain model without relying on any set-up assumptions. The proof of security only uses black-box techniques. Previous results rely on setup-assumptions such as the common refer-ence string model, key-registration model, or bare-public key model. These assumptions all need the existence of trusted-third parties or trusted directory available to all parties, which are sometimes hard to satisfy in practice and thus restrict the application of commitment schemes.3. The design and analysis of statistically binding commitment schemes preventing man-in-the-middle attacks. We give a construction of statistically binding commitment scheme which is concurrent non-malleable with respect to both commitment and decommitment. Our work can be seen as a complement of the work of Ostrovsky, Persiano and Visconti (TCC'09) in the plain model, which only achieves computational binding. Our construction relies on the existence of a family of pairs of claw-free permutations and only needs a constant number of communication rounds in the plain model. Our proof of security uses non-black-box techniques and satisfies the (most powerful) simulation-based definitions of non-malleability.4. The design and analysis of interactive proof systems preventing man-in-the-middle attacks. When interactive proof systems are applied in the complex environments, e.g., the Internet, it is interesting to consider whether they can simultaneously prevent man-in-the-middle attacks and achieve unconditional soundness, which means that even computationally unbounded adversary cannot prove a false statement to an honest verifier. Taking into account of the above two requirements, we give a construction of a constant-round one-many concurrent non-malleable zero-knowledge proof (in contrast to argument) system for every NP language in the plain model. We then give a construction of a constant-round concurrent non-malleable witness-indistinguishable proof system for every NP language. Compared with previous results, our constructions are the first constant-round proof systems that in the plain model guarantee simultaneously security against some non-trivial concurrent man-in-the-middle attacks and against unbounded malicious provers.