Blockchain Papers

Dror Lapidot, Adi Shamir

No abstract is available for this record.

Yvo Desmedt, Giovanni Di Crescenzo, Mike Burmester

No abstract is available for this record.

Joe Kilian

No abstract is available for this record.

Javad Mohajeri

No abstract is available for this record.

Giovanni Di Crescenzo

No abstract is available for this record.

Claude Crépeau, Jeroen van de Graaf, Alain Tapp

No abstract is available for this record.

Lidong Chen, Ivan Damgård, Torben Pryds Pedersen

No abstract is available for this record.

David Chaum

No abstract is available for this record.

Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson

No abstract is available for this record.

Oded Goldreich

A proof is whatever convinces me. Shimon Even (1935–2004) The glory attached to the creativity involved in finding proofs makes us forget that it is the less glorified process of verification that gives proofs their value. Conceptually speaking, proofs are secondary to the verification process, whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure presumes the notion of computation and furthermore the notion of efficient computation. This implicit stipulation is made explicit in the definition of NP , where efficient computation is associated with deterministic polynomial-time algorithms. However, as argued next, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In this chapter, we shall study three types of probabilistic proof systems, called interactive proofs, zero-knowledge proofs , and probabilistic checkable proofs . In each of these three cases, we shall present fascinating results that cannot be obtained when considering the analogous deterministic proof systems. Summary: The association of efficient procedures with deterministic polynomial-time procedures is the basis for viewing NP-proof systems as the canonical formulation of proof systems (with efficient verification procedures). Allowing probabilistic verification procedures and, moreover, ruling by statistical evidence gives rise to various types of probabilistic proof systems. Indeed, these probabilistic proof systems carry a probability of error (which is explicitly bounded and can be reduced by successive applications of the proof system), yet they offer various advantages over the traditional (deterministic and errorless) proof systems. […]

Alfredo De Santis, Giovanni Di Crescenzo, Guiseppe Persiano

No abstract is available for this record.

Giovanni Di Crescenco, Giuseppe Persiano

No abstract is available for this record.

Giovanni Di Crescenzo

No abstract is available for this record.

Hyungong Shin

In cryptography, the notion of zero-knowledge is important. It is also related to complexity theory. In this paper we briefly survey the zero-knowledge proofs in the literature. 1987 Maathematics Subject Classification: 69D56, 69E30, 69F21, Keywords and phrases: interactive proofs, zero-kniwledge, cryptography, complexity theiry.

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano

No abstract is available for this record.

Joan Boyar, Carsten Lund, René Peralta

No abstract is available for this record.

Oded Goldreich, Eyal Kushilevitz

No abstract is available for this record.

Oded Goldreich

No abstract is available for this record.

Toshiya Itoh, Kouichi Sakurai, Hiroki Shizuya

No abstract is available for this record.

Yvo Desmedt, Mike Burmester

No abstract is available for this record.

Toshiya Itoh, Kouichi Sakurai

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.

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.