Blockchain Papers

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano

No abstract is available for this record.

Ning Chen, Jiawei Rong

Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system,which is extended from the original definition of interactive proof and is more applicable in reality.

Ronald Cramer, Ivan Damgård

No abstract is available for this record.

Rafail Ostrovsky, Charles Rackoff, Adam Smith

No abstract is available for this record.

Boaz Barak, Rafael Pass

No abstract is available for this record.

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of auxiliary-input zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge strong proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. This result also extends to bounded-resettable zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication.

Alon Rosen

No abstract is available for this record.

Emmanuel Godard, Yves Métivier

No abstract is available for this record.

Oded Goldreich

No abstract is available for this record.

Manoj Prabhakaran, Alon Rosen, Arun Sahai

We show that every language in NP has a (black-box) concurrent zero-knowledge proof system using O/spl tilde/(log n) rounds of interaction. The number of rounds in our protocol is optimal, in the sense that any language outside BPP requires at least /spl Omega//spl tilde/(log n) rounds of interaction in order to be proved in black-box concurrent zero-knowledge. The zero-knowledge property of our main protocol is proved under the assumption that there exists a collection of claw free functions. Assuming only the existence of one-way functions, we show the existence of O/spl tilde/(log n)-round concurrent zero-knowledge arguments for all languages in NP.

Boaz Barak, Oded Goldreich

We put forward a new type of computationally-sound proof systems, called universal-arguments, which are related but different from both CS-proofs (as defined by Micali, 2000) and arguments (as defined by Brassard et al., 1986). In particular, we adopt the instance-based prover-efficiency paradigm of CS-proofs, but follow the computational-soundness condition of argument systems (i.e., we consider only cheating strategies that are implementable by polynomial-size circuits). We show that universal-arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to subexponential-size circuits as used in the construction of CS-proofs). As an application of universal-arguments, we weaken the intractability assumptions used in the recent non-black-box zero-knowledge arguments of Barak (2001). Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions referring to circuits of some "nice" super-polynomial size).

Cynthia Dwork, Moni Naor, Omer Reingold, Larry Stockmeyer

We prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective decommitment problem. An adversary is given commitments to a collection of messages, and the adversary can ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are unopened. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a "magic function" that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function.It follows easily from definitions that if a 3-round public-coin argument system is zero-knowledge in the standard (fairly strong) sense, then it has no magic function. We define a weakening of zero-knowledge such that zero-knowledge ⇒ no-magic-function still holds. For this weakened form of zero-knowledge, we give a partial converse: informally, if a 3-round public-coin argument system is not weakly zero-knowledge, then some form of magic is possible for this argument system. We obtain our definition of weak zero-knowledge by a sequence of weakenings of the standard definition, forming a hierarchy. Intermediate forms of zero-knowledge in this hierarchy are reasonable ones, and they may be useful in applications. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment.

Arun Sahai

We introduce the notion of non-malleable non-interactive zero-knowledge (NIZK) proof systems. We show how to transform any ordinary NIZK proof system into one that has strong non-malleability properties. We then show that the elegant encryption scheme of Naor and Yung (1990) can be made secure against the strongest form of chosen-ciphertext attack by using a non-malleable NIZK proof instead of a standard NIZK proof. Our encryption scheme is simple to describe and works in the standard cryptographic model under, general assumptions. The encryption scheme can be realized assuming the existence of trapdoor permutations.

Jung Min Park, Edwin K. P. Chong, Howard Jay Siegel

Fueled by the exponential growth in the number of people with access to the Internet, electronic-commerce (e-commerce) transactions via the Internet have become a major part of our economy. For a wider range of e-commerce applications to take advantage of the untapped business potential of the Internet, some challenging and interesting security problems need to be solved. In this thesis, we study two such problems, and provide efficient solutions for both. In the foreseeable future, some e-commerce vendors will generate revenue by providing digital streaming applications such as information broadcasts (e.g., stock quotes). For the first issue, we investigate the problem of authenticating packet streams in multicast or broadcast networks. Our approach is to encode the hash values and digital signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. We evaluate the performance of our scheme using both analytical and empirical results. Applications such as e-commerce payment protocols using electronic money require that fair exchange be assured. For the second issue, we investigate the problem of constructing fair-exchange protocols. Our approach uses a novel signature paradigm---the gradational signature scheme---to construct protocols that are efficient and scalable. Unlike previous approaches, our scheme does not employ any costly zero-knowledge proof systems in the exchange protocol. Use of zero-knowledge proofs is needed only in the protocol setup phase-this is a one-time cost. The resulting exchange protocol is more efficient than the previous solutions in terms of computation and communication overhead.

Shouhuai Xu, Moti Yung

No abstract is available for this record.

Anderson C. A. Nascimento, Akira Otsuka, Hideki Imai, Joern Mueller-Quade

No abstract is available for this record.

David Pointcheval, Guillaume Poupard

No abstract is available for this record.

Yunlei Zhao, Xiaotie Deng, C.H. Lee, Hong Zhu

The nature of zero-knowledge is re-examined and the evidence for the following belief is shown: the classic simulation based definitions of zero- knowledge (simulation zero-knowledge) may be somewhat too strong to include some “nice” protocols in which the malicious verifier seems to learn nothing but we do not know how to construct a zero-knowledge simulator for it. To overcome this problem a new relaxation of zero-knowledge, reduction zero-knowledge, is introduced. It is shown that reduction zero- knowledge just lies between simulation zero-knowledge and witness indistinguishability. Under the assumption of existence of one-way permutations a 4-round public-coin reduction zero-knowledge proof system for NP is presented and in practice this protocol works in 3 rounds since the first verifier's message can be fixed once and for all.

Ueli Maurer

No abstract is available for this record.

Hirotada Kobayashi

No abstract is available for this record.

Yvo Desmedt, Yongge Wang

No abstract is available for this record.

Daniele Micciancio, Salil Vadhan

No abstract is available for this record.

Hongbin Yang, Ji Won Jung, Dong-Ho Won

This paper proposes the optimal 4-move ZKIP (Zero-Knowledge Interactive Proof systems) of knowledge for SAT and its application. Using the trapdoor bit commitment scheme and the WI(Witness Indistingushable) and the WH(Witness Hiding), it is shown that as compared with 6-move ZKIP for SAT, the proposed ZKIP is 4-move ZKIP for SAT and under claw-free pairs of functions the proposed ZKIP is also 4-move ZKIP. The proposed scheme is more efficient at the points of computational complexity and communication complexity.

Rafail Ostrovsky, Avi Wigderson

If one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. The authors prove that unless very weak one-way functions exist, zero-knowledge proofs can be given only for languages in BPP. For average-case definitions of BPP they prove an analogous result under the assumption that uniform one-way functions do not exist. Thus, very loosely speaking, zero-knowledge is either useless (exists only for 'easy' languages), or universal (exists for every provable language).>