Blockchain Papers

Joan Boyar, René Peralta

No abstract is available for this record.

Uriel Feige, Adi Shamir

No abstract is available for this record.

Ning Ding, Dawu Gu

We provide the first proof of that for every language L isin NP there exists an O(1)-round computational zero-knowledge argument with polynomial precision for L. Our result assumes that ratio of running-time of any adversary verifier in some same verifier round of any two different executions of the argument is bounded by nalpha, where n is secure parameter and alpha is any predeterminate constant. Such verifiers are called restricted verifiers. Precise zero-knowledge was introduced by Micali and Pass in STOC'06 (They used the term "local zero-knowledge" there.) and they constructed some omega(1)-round polynomial/linear precise zero- knowledge protocols for NP and hence left an open problem how to construct O(1)-round polynomial/linear precise zero-knowledge protocols. By providing a precise simulator for Barak's O(1)-round non-black-box zero-knowledge argument, we prove that the argument is polynomial precise.

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai

In STOC'05, Aim, Hopper and Longford introduced the notion of covert computation. A covert computation protocol is one in which parties am run a protocol without knowing if other parties ore also participating in the protocol or not. At the end of the protocol, if all parties participated in the protocol and if the function output is favorable to all parties, then the output is revealed. Ahn et al. constructed a protocol for covert two-partv computation in the random oracle model In this paper, we offer a construction for covert multiparty computation. Our construction is in the standard model and does not require random oracles. In order to achieve this goal, we introduce a number of new techniques. Central to our work is the development of "zero-knowledge proofs to garbled circuits," which we believe could be of independent interest. Along the way, we also develop a definition of covert computation as per the Ideal/Real model simulation paradigm.

Edward Epsen

No abstract is available for this record.

Bruce M. Kapron, Lior Malka, Venkatesh Srinivasan

No abstract is available for this record.

Shanshan Duan

No abstract is available for this record.

Bo Yang, Yong Yu, Fagen Li, Ying Sun

No abstract is available for this record.

Donald Beaver

No abstract is available for this record.

Donald Beaver

No abstract is available for this record.

Charles Rackoff, Daniel Simón

No abstract is available for this record.

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

No abstract is available for this record.

Ivan Damgård

No abstract is available for this record.

Yonatan Aumann, Uriel Feige

No abstract is available for this record.

Mike Burmester, Yvo Desmedt

No abstract is available for this record.

Ivan Damgård

No abstract is available for this record.

Cynthia Dwork, Uri Feige, Joe Kilian, Moni Naor · 5 authors

No abstract is available for this record.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.

Sae-Ran Kwon, Sangho Lee

No abstract is available for this record.

Hoeteck Wee

No abstract is available for this record.

Hirotada Kobayashi

This paper studies the complexity classes QZK and HVQZK of problems having a quantum computational zero-knowledge proof system and an honest-verifier quantum computational zero-knowledge proof system, respectively. The results proved in this paper include: (a) HVQZK = QZK, (b) any problem in QZK has a public-coin quantum computational zero-knowledge proof system, (c) any problem in QZK has a quantum computational zero-knowledge proof system of perfect completeness, and (d) any problem in QZK has a three-message public-coin quantum computational zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. All the results above are unconditional and do not rely any computational assumptions. For the classes QPZK, HVQPZK, and QSZK of problems having a quantum perfect zero-knowledge proof system, an honest-verifier quantum perfect zero-knowledge proof system, and a quantum statistical zero-knowledge proof system, respectively, the following new properties are proved: (e) HVQPZK = QPZK, (f) any problem in QPZK has a public-coin quantum perfect zero-knowledge proof system, (g) any problem in QSZK has a quantum statistical zero-knowledge proof system of perfect completeness, and (h) any problem in QSZK has a three-message public-coin quantum statistical zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. It is stressed that our proofs are direct and do not use complete promise problems or those equivalents. This gives a unified framework that works well for all of quantum perfect, statistical, and computational zero-knowledge proofs, and enables us to prove properties even on the computational and perfect zero-knowledge proofs for which no complete promise problems are known.

Gilles Brassard, Claude Crépeau

A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed. Under cryptographic assumptions, we give a general technique for achieving this goal for every problem in NP. This extends to a presumably larger class, which combines the powers of non-determinism and randomness. Our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof: it is enough for Alice to convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, in order for her to be able to convince Bob as well, without compromising the trap-door in any way. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership x ∈ L) is a proof that can be verified by reading only one of its bits, with the help of a very short interactive-proof. We show that for membership in some languages L, there are interactive-PCPs that are significantly shorter than the known (non-interactive) PCPs for these languages. Our main result is that the satisfiability of a constant depth Boolean formula Φ(z1, . . . , zk) of size n (over the gates ∧,∨, ⊕,¬) can be proved by an interactive-PCP of size poly(k), followed by a short interactive proof of communication complexity polylog(n). That is, we obtain interactivePCPs of size polynomial in the size of the witness. This compares to the known (non-interactive) PCPs that are of size polynomial in the size of the instance. By reductions, this result extends to many other central NP languages (e.g., SAT, k-clique, Vertex-Cover, etc.). More generally, we show that the satisfiability of Vn i=1[Φi(z1, . . . , zk) = 0], where each Φi(z1, . . . , zk) is an arithmetic formula of size n (say, over GF[2]) that computes a polynomial of degree d, can be proved by an interactive-PCP of size poly(k, d), followed by a short interactive proof of communication complexity poly(d, log n). We give many cryptographic applications and motivations for our results. In particular, we show the following: 1. The satisfiability of a constant depth formula Φ(z1, . . . , zk) of size n (as above) has an interactive zero-knowledge proof of communication complexity poly(k) (rather than poly(n))1 . As before, this result extends to many other central NP languages. This zero-knowledge proof has some additional desired properties that will be elaborated on in the body of the paper. 2. Alice can commit to a Boolean formula Λ of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form Λ(x1) = z1, . . . ,Λ(xN ) = zN by a zero-knowledge proof of communication complexity poly(m, log N). Moreover, if Λ is a constant depth Boolean formula then the zero-knowledge proof has communication complexity poly(log m, log N). We further motivate this application in the body of the paper.

Jiawei Dou, Shundong Li

Non-malleable commitment is recently one of research focuses in international cryptographic community. It has many important applications in e-commerce, and plays important role in constructing other cryptographic protocols. Most existing non-malleable commitment schemes are constructed by requiring that a committer proves, by zero-knowledge proof, that he knows his committed secret. The attached zero-knowledge proof process makes existing non-malleable commitments have higher computational and communication complexity. More efficient schemes are appealing. This paper constructs three new efficient non-malleable commitment schemes which do not require that a committer proves he knows his committed secret by zero-knowledge proof, but rather require a committer proves, by other arguments, that he does know the secret at the same time he makes commitment. These non-malleable commitment schemes, without zero-knowledge proof, are much more efficient.