Blockchain Papers

Tzafrir Cohen, Joe Kilian, Erez Petrank

No abstract is available for this record.

Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano · 5 authors

. Non-Interactive Zero Knowledge (NIZK), introduced by Blum, Feldman, and Micali in 1988, is a fundamental cryptographic primitive which has attracted considerable attention in the last decade and has been used throughout modern cryptography in several essential ways. For example, NIZK plays a central role in building provably secure public-key cryptosystems based on general complexity-theoretic assumptions that achieve security against chosen ciphertext attacks. In essence, in a multi-party setting, given a fixed common random string of polynomial size which is visible to all parties, NIZK allows an arbitrary polynomial number of Provers to send messages to polynomially many Verifiers, where each message constitutes an NIZK proof for an arbitrary polynomial-size NP statement. In this paper, we take a closer look at NIZK in the multi-party setting. First, we consider non-malleable NIZK, and generalizing and substantially strengthening the results of Sahai, we give the first construction of NIZK which remains non-malleable after polynomially-many NIZK proofs. Second, we turn to the definition of standard NIZK itself, and propose a strengthening of it. In particular, one of the concerns in the technical definition of NIZK (as well as non-malleable NIZK) is that the so-called "simulator" of the Zero-Knowledge property is allowed to pick a different "common random string" from the one that Provers must actually use to prove NIZK statements in real executions. In this paper, we propose a new definition for NIZK that eliminates this shortcoming, and where Provers and the simulator use the same common random string. Furthermore, we show that both standard and non-malleable NIZK (as well as NIZK Proofs of Knowledge) can be constructed achieving this stronger definition. We call...

Joan Boyar, Ivan Damgård, René Peralta

No abstract is available for this record.

Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape. All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting. Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting. Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct:

Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung

Article On zero-knowledge proofs (extended abstract): "from membership to decision" Share on Authors: Giovanni Di Crescenzo Telcordia Technologies Inc., 445 South Street, Morristown, NJ Telcordia Technologies Inc., 445 South Street, Morristown, NJView Profile , Kouichi Sakurai Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, Japan Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, JapanView Profile , Moti Yung CertCo, New York, NY CertCo, New York, NYView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 255–264https://doi.org/10.1145/335305.335336Online:01 May 2000Publication History 3citation509DownloadsMetricsTotal Citations3Total Downloads509Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Christian Cachin, Jan Camenisch

No abstract is available for this record.

Joe Kilian, Erez Petrank

A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment; Kilian, Petrank and Rackoff have shown that any 4 rounds zero-knowledge interactive proof (for a non-trivial language) is not concurrent zero-knowledge. On the other hand, Richardson and Kilian have shown that there exists a concurrent zero-knowledge argument for all languages in NP, but it requires a polynomial number of rounds. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a drastically improved complexity: our proof requires only a poly-logarithmic, specifically, ω(log 2 k) number of rounds. Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge proof that is robust for asynchronous composition. 1

Guillaume Poupard, Jacques Stern

No abstract is available for this record.

Alon Rosen

No abstract is available for this record.

Ivan Damgård

No abstract is available for this record.

Giovanni Di Crescenzo

No abstract is available for this record.

Danny Gutfreund, Michael Ben-Or

No abstract is available for this record.

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano

No abstract is available for this record.

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

No abstract is available for this record.

Wen‐Chung Kuo, Chi‐Sung Laih, Min-Jea Gau

Measurements of total cholesterol in the field by means of the Reflotron dry-chemistry system (capillary blood) were compared to total cholesterol obtained by a standardized conventional wet-chemistry method in a clinico-chemical laboratory (serum). A total of 1200 people participated in the study. Two identical Reflotron machines were used. In the first period of the study an excellent agreement was found between Reflotron measurements of a reference serum provided by the manufacturer (mean, 4.99 mmol/l; CV, 1.8%) and the stated value (4.97 mmol/l). In the rest of the study higher values and greater variation were found with the Reflotron (mean, 5.32 mmol/l; CV 5.2%). Clearly the Reflotron measurements in the latter period of study were not reliable. In the period with stable instruments most of the values obtained at the two Reflotron machines differed from each other by less than 10%, with a mean difference of 0.08 mmol/l. Reflotron (both machines) and wet-chemistry measurements agreed well for the first 500 participants in the study (mean difference, Reflotron-wet-chemistry, -0.008 mmol/l; 95% confidence interval, -0.035 to 0.019 mmol/l; correlation, 0.967). In this period most Reflotron values differed from wet-chemistry values by less than 9% below to 9% above. With the next 200 participants the Reflotron gave on average slightly higher values than wet-chemistry measurements. The coefficients of variation for measurement variation were higher for Reflotron that for wet-chemistry even in the period with stable instruments. In all parts of the study period a lower HDL-cholesterol level was associated with larger differences between total cholesterol determined by Reflotron and wet-chemistry.

J. Mohajeri

No abstract is available for this record.

Markus Jakobsson, Claus-Peter Schnorr

We study the notion of meta-proofs, which, as the name indicates, are proofs about proofs. We employ the notion of meta-proofs to produce a highly efficient oblivous proof of correct exponentiation. It is minimum-knowledge independently of whether the input is valid or not, a property that does not hold for many other protocols (that are zero-knowledge only for valid inputs.) This has direct security implications to multiparty protocols, where the protocols we demonstrate — one interactive and one non-interactive — can be employed to obtain protocol robustness at a low cost. As a result of potential independent interest, we show how to turn any standard discrete log signature scheme into a scheme for proving equality of discrete logarithms. We demonstrate our method using the Schnorr signature scheme.

Alfredo De Santis, Giuseppe Persiano, Giovanni Di Crescenzo

No abstract is available for this record.

Oded Goldreich, Amit Sahai, Salil Vadhan

No abstract is available for this record.

Giovanni Di Crescenzo, Rafail Ostrovsky

No abstract is available for this record.

Uriel Feige, Dror Lapidot, Adi Shamir

In this paper we show how to construct noninteractive zero knowledge proofs for any NP statement under general (rather than number theoretic) assumptions, and how to enable polynomially many provers to give polynomially many such proofs based on a single random string. Our constructions can be used in cryptographic applications in which the prover is restricted to polynomial time.

Uriel Feige, Joe Kilian

We present a new technique, inspired by zero-knowledge proof systems, for proving lower bounds on approximating the chromatic number of a graph. To illustrate this technique we present simple reductions from max-3-coloring and max-3-sat, showing that it is hard to approximate the chromatic number within /spl Omega/(N/sup /spl delta//), for some /spl delta/>0. We then apply our technique in conjunction with the probabilistically checkable proofs of Bellare, Goldreich and Sudan (1995), and of Hastad (1996), and show that it is hard to approximate the chromatic number to within /spl Omega/(N/sup 1-/spl epsiv//) for any E>0, assuming NP/spl sub/ ZPP. Here, ZPP denotes the class of languages decidable by a random expected polynomial-time algorithm that makes no errors. Our result matches (up to low order terms) the known gap for approximating the size of the largest independent set. Previous 0(N/sup /spl delta//) gaps for approximating the chromatic number (such as those by Lund and Yannakakis (1994), and by Furer (1995)) did not match the gap for independent set, and do not extend beyond /spl Omega/(N/sup 1/2-/spl epsiv//).

Jan Camenisch, Markus Michels

<p>This paper presents the first efficient statistical zero-knowledge protocols to prove statements such as:<br />A committed number is a pseudo-prime.<br />A committed (or revealed) number is the product of two safe primes, i.e., primes p and q such that (p - 1)=2 and (q - 1)=2 are primes as well.<br />A given value is of large order modulo a composite number that consists of two safe prime factors.</p><p>So far, no methods other than inefficient circuit-based proofs are known for proving such properties. Proving the second property is for instance necessary in many recent cryptographic schemes that rely on both the hardness of computing discrete logarithms and of difficulty computing roots modulo a composite.<br />The main building blocks of our protocols are statistical zero-knowledge proofs that are of independent interest. Mainly, we show how to prove the correct computation of a modular addition, a modular multiplication, or a modular exponentiation, where all values including the modulus are committed but not<br />publicly known. Apart from the validity of the computation, no other information about the modulus (e.g., a generator which order equals the modulus) or any other operand is given. Our technique can be generalized to prove in zeroknowledge<br />that any multivariate polynomial equation modulo a certain modulus is satisfied, where only commitments to the variables of the polynomial and a commitment to the modulus must be known. This improves previous results,<br />where the modulus is publicly known.<br />We show how a prover can use these building blocks to convince a verifier that a committed number is prime. This finally leads to efficient protocols for proving that a committed (or revealed) number is the product of two safe primes. As a consequence, it can be shown that a given value is of large order modulo a<br />given number that is a product of two safe primes.</p><p> </p><p>Keywords. RSA-based protocols, zero-knowledge proofs of knowledge, primality tests.</p>

Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung

No abstract is available for this record.