Research On The Non-Malleability Of Zero-Knowledge Proof Systems And Commitment Schemes

In the last seventies and eighties, the research of modern cryptography has ushered in a new era of vigorous development, in which a series of milestone achievements, such as public key cryptography, interactive proof system and pseudo-random generators, have emerged, opening up the way of combining cryptography with complexity theory. In the FOCS’97conference, Goldwasser gives an invited talk with the tile "Cryptography and Complexity Theory:A Match Made in Heaven", and points out that, the most important progress made in modern cryptography is basing this field on complexity theory, and it is complexity theory that has transformed cryptography from an art to a rigorous science. Moreover, zero-knowledge is the best witness of the intertwining and cross-promoting between cryptography and complexity theory.Informally speaking, a zero-knowledge proof system is a two-party interactive protocol, in which a prover tries to convince a verifier the correctness of a statement, but ensures that the verifier learns no extra information during the interactive procedure. Zero-knowledge has been at the heart of cryptography since its invention, and plays a key role in the development of cryptography. First, zero-knowledge laid the foundation for the formal analysis of cryptographic protocols, and its simulation-based way of security proofs have become the core of provable security theory. More importantly, the seemingly contradictory nature enables zero-knowledge proof system to integrate "privacy" and "authentication" within the single primitive, which results in a wide array of applications, such as identification protocols, encryption schemes secure against chosen ciphertext attack, and secure multi-party protocols against malicious adversaries.As a fundamental building block of zero-knowledge proof system and other secure protocols, the idea of a commitment scheme (sealed envelope) appears earlier than zero-knowledge in the design of protocols for coin-tossing by telephone, mental poker and so on. Finally, it is formally defined by Brassard et al. and gets the vivid name of "commitment". Roughly speaking, a commitment scheme is a two-phase interactive protocol between two parties. First in the commit phase, the committer commits himself to a string (say v), and sends the commitment to the receiver, while ensuring that the receiver knows nothing about v; then in the reveal phase, the committer publishes v, and proves it is consistent with the messages in the first stage. Two basic properties of commitment scheme are known as hiding and binding, in which hiding says that, in the commit phase no malicious receiver can get any information about the secret string v, and binding says that, in the reveal phase no malicious committer can open the commitment to another value successfully while passing the decomitment verification.In the research of cryptographic protocols, commitment schemes are often used as sub-protocols to build more complex ones, in which they are taken to fix the inputs of the participants as well as keep their privacy. Furthermore, they usually cooperate with zero-knowledge proof systems to achieve secure multi-party protocols against malicious adversaries. Besides, there exit inherent relations between commitment schemes and zero-knowledge proof systems, so that the researches in both areas are always proceeding hand-in-hand.In recent years, with the rapid development of internet, cryptographic protocols that run in the concurrent and asynchronous network encounter more and more security challenges, so that the basic security properties of protocols are not sufficient to cope with the complex network applications. Therefore, how to build reasonable security models and design cryptographic protocols that enjoy higher security and apply to the internet applications has been one of the attractive areas in cryptography.Concurrent non-malleability defines the security property of zero-knowledge proof systems as well as commitment schemes against "man-in-the-middle" attack, when executing multi times concurrently. Taking zero-knowledge for example, consider the follow scenario:a man-in-the-middle adversary concurrently participates many sessions running the same zero-knowledge protocol, in some of which the adversary plays the role of verifier receiving and verifying proofs of some statements given by the honest provers, while in others the adversary interacts with the honest verifiers as a prover trying to construct proofs of some related statements, Zero-knowledge proof systems and commitment schemes secure against the above concurrent man-in-the-middle attack are called concurrent non-malleable. It is generally believed that, concurrent non-malleability is most suitable for modeling the security requirements in the open network. In this paper, we investigate concurrent non-malleable zero-knowledge as well as commitment schemes, and focus mainly on the robustness of protocols. Specifically, we work on the following points:·On concurrent non-malleable zero-knowledgeRecently, Lin et al. extends the original non-malleability of commitment schemes to a more general form called non-malleability with respect to arbitrary k-round protocol (or k-non-malleability for short), studying the security of commitments in the following scenario:the man-in-the-middle adversary participates one left session running an arbitrary k-round protocol, and multi right sessions interacting with a set of honest receivers and executing a commitment scheme. Loosely speaking, k-non-malleability shows the robustness of a commitment scheme when composed with other protocols. That is, a k-non-malleable commitment scheme can be composed with any protocols with no more than k rounds, and does not affect its security. Hence, this kind of protocol is easier to analyze when concurrently composed with other protocols.Highly inspired by the above literature, we turn to study the robustness of concurrent non-malleable zero-knowledge. In the existing concurrent non-malleable zero-knowledge protocols, some rely on non-black-box simulation technique. However, as we know that, less robustness is the inherent limitation of non-black-box techniques, let alone in the concurrent setting. Besides, all the other constructions applying black-box simulation follows the Goldreich-Kahan style incorporating a zero-knowledge sub-protocol, which makes robustness hard to argue (sine zero-knowledge is not closed under concurrent composition).In this paper, we present the first robust concurrent non-malleable zero-knowledge argument system that enjoys the properties below:a) Following the Feige-Shamir style, takes robust non-malleable commitment and specifically designed witness indistinguishable proofs as basic components to achieve zero-knowledge, and at the same time ensures the robustness of the whole protocol.b) Applies the "oblivious simulation" strategy to emulate the view of the adversary.c) Achieves optimal (super-logarithmic) round complexity under the minimal assumption of one-way functions.d) Can be composed with any protocols by appropriately adjusting the round complexity of the sub-protocols.·On concurrent non-malleable commitmentsThe non-malleability of commitment schemes are defined respectively for each stage, i.e. non-malleability with respect to commitment and non-malleability with respect to decommitment, describing the independence of each stage with respect to itself separately. In a recent work in TCC’09, Ostrovsky et al. investigate the relation between these two kinds of non-malleability definitions, and pointed out that, under the simulation-based definition, non-malleability with respect to commitment does not imply the non-malleability with respect to decommitment, so that it is of great theoretical significance to design a commitment protocol that satisfies both kind of non-malleability. Additionally, this paper shows a way to construct a computationally hiding and computationally binding commitment which is concurrent non-malleable with respect to commitment as well as decommitment. Later in PKC’10, Cao et al. patch this protocol to obtain a statistically binding version. However, both of these two schemes (and almost all existing non-malleable commitment schemes) are subjected to the same constraint:the commitment phase and decommit phase cannot overlap in time. Hence, it remains an open question to construct a fully concurrent non-malleable commitment scheme with stage-overlapping.In this paper, we do the following work on this problem:a) We show that under the current definition of non-malleability, it is impossible to solve the above problem. At the same time, we present a new definition for the concurrent non-malleability of commitment schemes, which is essentially the same with the original one but takes a different form to fit this scenario.b) We analyze the reason why this problem exists, and then solve it by constructing a computationally hiding and computationally binding commitment scheme, which is concurrent non-malleable with respect to commitment and decommitment, even though stage-overlapping is allowed. Based on the one-way function assumption, either the commit phase or the decommit phase needs super-logarithmic rounds.