Blockchain Papers

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

No abstract is available for this record.

Claus Akira Matsushigue

Various types of sysfems o/ proai/istc proa/s have played a decisive role in the development of Computer Science Theory in the last decade. This can be verified through the great number of studies about interactive proofs, zero-knowledge proofs, and transparent (or holographic) proofs. These topics are guided by the robustness of the codifications and by the computational capacity of checking them. In this text, we aim at presenting a ecncal ntroduc on reZaiue fo the proabilstcaZZy checkaZe robust proa/s. Within this approach. the new characterization of the non-deterministic polynomial-time class through the Probabilistically Checkable Proofs class formulated by Arara, Lund, Motwani. Sudan e Szegedy in IALM+92], ./V'P = PCP(logo, 1), is of central importance. We intend to prove this characterization, because it encompasses the principal points of the subject and. furthermore, covers subjacently a wide set of computational, algebraic. and probabilistic tools. which are fundamental in this topic.

Ivan Damgård, Birgit Pfitzmann

<p>We study the behavior of interactive arguments under sequential iteration, in particular how this affects the error probability. This problem turns out to be more complex than one might expect from the fact that for interactive proofs, the error trivially decreases exponentially in the number of iterations.<br />In particular, we study the typical efficient case where the iterated protocol is based on a single instance of a computational problem. This is not a special case of independent<br />iterations of an entire protocol, and real exponential decrease of the error cannot be expected, but nevertheless, for practical applications, one needs concrete relations<br />between the complexity and error probability of the underlying problem and that of the iterated protocol. We show how this problem can be formalized and solved using the<br />theory of proofs of knowledge.<br /> We also prove that in the non-uniform model of complexity the error probability<br />of independent iterations of an argument does indeed decrease exponentially - to our knowledge this is the first result about a strictly exponentially small error probability in a computational cryptographic security property. <br />As an illustration of our first result, we present a very efficient zero-knowledge argument<br />for circuit satisfiability, and thus for any NP problem, based on any collision-intractable hash function. Our theory applies to show the soundness of this protocol. Using an efficient hash function such as SHA-1, the protocol can handle about 20000 binary gates per second at an error level of 2^−50.</p><p>Keywords -- Interactive proofs, arguments, proofs of knowledge, computational security,<br />efficient general primitives, multi-bit commitment, statistical zero-knowledge.</p>

Giovanni Di Crescenzo, Tatsuaki Okamoto, Moti Yung

No abstract is available for this record.

Alfredo De Santis, Giovanni Di Crescenzo, Pino Persiano

No abstract is available for this record.

Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung

No abstract is available for this record.

Joe Kilian, Erez Petrank, Gábor Tardos

In the course of constructing these PCP'S we abstract a tool we call locking systems. We provide the definition and also a locking system with very efficient parameters. This mechanism may be useful in other settings as well.

Ronald Cramer, Ivan Damgård

We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, a<br />circuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)<br />interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication<br />of Omega(n^3 log n) bits.<br />Variations of the technique behind these protocols lead to other interesting applications.<br />We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)<br />bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.<br />As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proof<br />system with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.

Ivan B. Damg aard, R.J.F. Cramer

Assume we are given a language $L$ with an honest verifier perfect zero-knowledge proof system. Assume also that the proof system is a $\leq 3$ move Arthur-Merlin game. The class of such languages includes all random self-reducible language, and also any language with a perfect zero-knowledge non-interactive proof. We show that such a language satisfies a certain closure property, namely that languages constructed from $L$ by applying certain monotone functions to statements on membership in $L$ have perfect zero-knowledge proof systems. The new set of languages we can build includes $L$ itself, but also for example languages consisting of $n$ words of which at least $t\leq n$ are in $L$. A similar closure property is shown to hold for the complement of $L$ and for statistical zero-knowledge. The property we need for the monotone functions used to build the new languages is that there are efficient secret sharing schemes for their associated access structures. This includes (but is not necessarily limited to) all monotone functions with polynomial size monotone formulas.

Oded Goldreich, Hugo Krawczyk

The wide applicability of zero-knowledge interactive proofs comes from the possibility of using these proofs as subroutines in cryptographic protocols. A basic question concerning this use is whether the (sequential and/or parallel) composition of zero-knowledge protocols is zero-knowledge too. We demonstrate the limitations of the composition of zero-knowledge protocols by proving that the original definition of zero-knowledge is not closed under sequential composition; and that even the strong formulations of zero-knowledge (e.g., black-box simulation) are not closed under parallel execution. We present lower bounds on the round complexity of zero-knowledge proofs, with significant implications for the parallelization of zero-knowledge protocols. We prove that three-round interactive proofs and constant-round Arthur-Merlin proofs that are black-box simulation zero-knowledge exist only for languages in BPP. In particular, it follows that the “parallel versions” of the first interactive proofs systems presented for quadratic residuosity, graph isomorphism, and any language in NP, are not black-box simulation zero-knowledge, unless the corresponding languages are in BPP Whether these parallel versions constitute zero-knowledge proofs was an intriguing open questions arising from the early works on zero-knowledge. Other consequences are a proof of optimality for the round complexity of various known zero-knowledge protocols and the necessity of using secret coins in the design of “parallelizable” constant-round zero-knowledge proofs.

Ivan Damgård, Ronald Cramer

We present a zero-knowledge proof system [19] for any NP language L, which<br />allows showing that x in L with error probability less than 2^−k using communication<br />corresponding to O(|x|^c) + k bit commitments, where c is a constant depending only<br />on L. The proof can be based on any bit commitment scheme with a particular set<br />of properties. We suggest an efficient implementation based on factoring.<br />We also present a 4-move perfect zero-knowledge interactive argument for any NP-language<br />L. On input x in L, the communication complexity is O(|x|^c) max(k; l)<br />bits, where l is the security parameter for the prover. Again, the protocol can be<br />based on any bit commitment scheme with a particular set of properties. We suggest<br />efficient implementations based on discrete logarithms or factoring.<br />We present an application of our techniques to multiparty computations, allowing<br />for example t committed oblivious transfers with error probability 2^−k to be done<br />simultaneously using O(t+k) commitments. Results for general computations follow<br />from this.<br />As a function of the security parameters, our protocols have the smallest known<br />asymptotic communication complexity among general proofs or arguments for NP.<br />Moreover, the constants involved are small enough for the protocols to be practical in<br />a realistic situation: both protocols are based on a Boolean formula Phi containing and-<br />, or- and not-operators which verifies an NP-witness of membership in L. Let n be<br />the number of times this formula reads an input variable. Then the communication<br />complexity of the protocols when using our concrete commitment schemes can be<br />more precisely stated as at most 4n + k + 1 commitments for the interactive proof<br />and at most 5nl +5l bits for the argument (assuming k <= l). Thus, if we use k = n,<br />the number of commitments required for the proof is linear in n.<br />Both protocols are also proofs of knowledge of an NP-witness of membership in<br />the language involved.

Mike Burmester, Yvo Desmedt, Toshiya Itoh, Kouichi Sakurai · 6 authors

No abstract is available for this record.

Alfredo De Santis, Giuseppe Persiano

No abstract is available for this record.

Markus Jakobsson, Moti Yung

No abstract is available for this record.

Jacques Stern

The present paper investigates the possibility of designing zero-knowledge identification schemes based on hard problems from coding theory. Zero-knowledge proofs were introduced by Goldwasser, Micali, and Rackoff (1985). Their practical significance was soon demonstrated in the work of Fiat and Shamir [1986], who turned zero-knowledge proofs of quadratic residuosity into efficient means of establishing user identities. In the present paper, we propose a new identification scheme, based on error-correcting codes, which is zero-knowledge and seems of practical value. Furthermore, we describe several variants, including one which has an identity-based character. The security of our schemes depends on the hardness of finding a word of given syndrome and prescribed (small) weight with respect to some randomly generated binary linear error-correcting code. This is, of course, not the first attempt to design a cryptographic scheme using tools from coding theory. The difference is that identification protocols do not follow the public key paradigm based on trap-door functions and described in the seminal Diffie-Hellman paper [1976]. Rather, they only require one-way functions, which opens the way to using, in a rather direct manner, simple combinatorial problems of the kind provided by coding theory. The resulting schemes compare favorably to their number-theoretic analogs.

Shai Halevi, Silvio Micali

No abstract is available for this record.

Tatsuaki Okamoto

No abstract is available for this record.

Ronald Cramer, Ivan Damgård

We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that x 2 L with error probability less than 2 \\Gammak using communication corresponding to O(jxj c )+O(k) bit commitments, where c is a constant depending only on L. We also present a 4-move perfect zero knowledge interactive argument for any NP-language L. On input x 2 L, the communication complexity is O(jxj c ) \\Delta max(k; l) bits, where l is the security parameter for the prover 1 . The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: our protocols allows proving/arguing satisfiability of a Boo...

Oded Goldreich, Ariel Kahan

No abstract is available for this record.

Yung‐Hsiang Chen, Tzonelih Hwang

No abstract is available for this record.

Joan Boyar, Gilles Brassard, René Peralta

The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment.>

Tzong‐Chen Wu, Tzong‐Sun Wu

No abstract is available for this record.

Jau-Liang Chen, Tzonelih Hwang

No abstract is available for this record.

Dror Lapidot, Adi Shamir

No abstract is available for this record.