Blockchain Papers

Tatsuaki Okamoto

No abstract is available for this record.

Joan Feigenbaum, Rafail Ostrovsky

No abstract is available for this record.

Mihir Bellare, Phillip Rogaway

We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol PR for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.

Cynthia Dwork, Larry Stockmeyer

The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition.

Cynthia Dwork, Larry Stockmeyer

An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.

Mike Burmester, Yvo Desmedt

No abstract is available for this record.

Joan Boyar, Faith E. Fich, Kim S. Larsen

<p>Let A and B be n x n matrices the entries of which are affine combinations of the variables a_1,... ,a_m,b_1,. .. ,b_m over GF(2). Suppose that, for each i, 1<= i <= m, the term a_i b_i is an element of the product matrix C = A € B. What is the maximum value that <em> m </em> can have as a function of <em> n </em>? This question arises from a recent technique for improving the communication complexity of zero-knowledge proofs.</p><p>The obvious upper bound of n^2 is improved to n^2 sqrt[3] 3 + O(n). Tighter bounds are obtained for smaller values of n. The bounds for n = 2, n = 3, and n = 4 are tight.</p>

Mike Burmester

No abstract is available for this record.

Toshiya Itoh, Tomomi Hosokawa

Abstract In modern cryptologic theory, the design of cryptographic protocols is often based on the assumed difficulty of number theoretic problems. Especially, in order to prove the security of a cryptographic protocol based upon the assumed difficulty of a problem, a very important role is played by the legitimacy (as concerns the security of the cryptographic protocol) of that cryptographic assumption. Recently, Kurosawa, Ogata, and Tsujii proposed a new cryptographic assumption, the Chosen Discrete Logarithm Assumption (CDLA), and showed that any language in NP has a four‐move, zero‐knowledge interactive proof (ZKIP) under the CDLA. In this paper, we define the modified CDLA and consider its legitimacy. Our principal result (that the modified CDLA is not a legitimate cryptographic assumption) follows from a theoretical analysis of expected polynomial‐time algorithms and the concrete construction of an algorithm based on the Artin conjecture.

David Chaum, Eugène van Heijst, Birgit Pfitzmann

No abstract is available for this record.

Mihir Bellare, Erez Petrank

We look at the question of how powerful a prover must be to give a zero-knowledge proof.We present the first unconditional bounds on the complexity of a statistical ZK prover.The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle.Previously this was only known given the existence of one-way permutations. Extendingthese techniques to protocols of knowledge complexity k(n) >0, we derive bounds on the time complexity of languages of "small" knowledge complexity.Underlying these results is a technique for efficiently generating an "almost" random element of a set S E P.Namely, we construct a probabilistic machine with an NP oracle which, on input 1" and 6 > 0 runs in time polynomial in n and lg 6-1, and outputs a random string from a distribution within distance 6 of the uniform distribution on S n {O, l}~.

Alfredo De Santis, Giuseppe Persiano, Moti Yung

No abstract is available for this record.

Alfredo De Santis, Giuseppe Persiano

No abstract is available for this record.

Alfredo De Santis, Giuseppe Persiano

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he “knows” the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. In this paper, we investigate the concept of a zero-knowledge proof of knowledge in the noninteractive model of [5, 61. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zeroknowledge proofs of knowledge is a delicate task. The main results of the paper are the following e We present formal definitions for the concept of non-interactive zero-knowledge proofs

Alfredo De Santis, Giuseppe Persiano

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zero-knowledge proofs of knowledge is a delicate task.>

Joe Kilian

In this note, we present new zero-knowledge interactive proofs and arguments for languages in NP. To show that x ε L, with an error probability of at most 2-k, our zero-knowledge proof system requires O(|x|c1)+O(lgc2|x|)k ideal bit commitments, where c1 and c2 depend only on L. This construction is the first in the ideal bit commitment model that achieves large values of k more efficiently than by running k independent iterations of the base interactive proof system. Under suitable complexity assumptions, we exhibit zero knowledge arguments that require O(lgc|x|kl bits of communication, where c depends only on L, and l is the security parameter for the prover. This is the first construction in which the total amount of communication can be less than that needed to transmit the NP witness. Our protocols are based on efficiently checkable proofs for NP[4].

Josep Domingo‐Ferrer

No abstract is available for this record.

Manuel Blum, Alfredo De Santis, Silvio Micali, Giuseppe Persiano

This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.

William Aiello, Johan Håstad

No abstract is available for this record.

Oded Goldreich, Silvio Micali, Avi Wigderson

In this paper the generality and wide applicability of Zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff is demonstrated. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages in NP fl CONP. Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula, in particular, without yielding neither a

Kaoru Kurosawa, Tatsuaki Okamoto

No abstract is available for this record.

William Aiello, Johan Håstad

No abstract is available for this record.

Mike Burmester, Yvo Desmedt

No abstract is available for this record.

Alfredo De Santis, Moti Yung

No abstract is available for this record.