Blockchain Papers

Joan Boyar, Ivan Damgård, René Peralta

No abstract is available for this record.

David Pointcheval

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.

Khanh Quoc Nguyen, Feng Bao, Yi Mu, Vijay Varadharajan

No abstract is available for this record.

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>

Rosario Gennaro, Daniele Micciancio, Tal Rabin

We present efficient zero-knowledge proof systems for quasi-safe prime products and other related languages. Quasi-safe primes are a relaxation of safe primes, a class of prime numbers useful in many cryptographic applications. Our proof systems achieve higher security and better efficiency than all previously known ones. In particular, all our proof systems are perfect or statistical zero-knowledge, meaning that even a computationally unbounded adversary cannot extract any information from the proofs. Moreover, our proof systems are extremely efficient because they do not use general reductions to NP-complete problems, can be easily parallelized preserving zero-knowledge, and are non-interactive for computationally unbounded provers. The prover can also be efficiently implemented given some trapdoor information and using very little interaction. We demonstrate the applicability of quasi-safe primes by showing how they can be effectively used in the context of RSA based undeniable signatures to enforce the use of "good" public keys, i.e., keys such that if a signer can convince a recipient of the validity of a signature, then he won't be able to subsequently deny the same signature in case of a dispute.

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.

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...

Stefano D’Amiano, Giovanni Di Crescenzo

No abstract is available for this record.

Giovanni Di Crescenco, Giuseppe Persiano

No abstract is available for this record.

Yvo Desmedt, Mike Burmester

No abstract is available for this record.

Neal Koblitz

No abstract is available for this record.

Joan Boyar, Katalin Friedl, Carsten Lund

No abstract is available for this record.

Kazuo Ohta, Tatsuaki Okamoto

No abstract is available for this record.

Jørgen Brandt, Ivan Damgård, Peter Landrock, Torben Pedersen

No abstract is available for this record.

Joan Boyar, Stuart A. Kurtz, Mark W. Krentel

No abstract is available for this record.

Moni Naor, Moti Yung

We show how to construct a public-key cryptosystem (as originally defined by DiNe and Hellman) secure against chosen ciphertezt attacks, given a public-key cryptosystern secure against passive eavesdropping and a noninteractive zero-knowledge proof system in the shared string model. No such secure cryptosystems were known before. A concrete implementation can be based on quadratic residuosity intractability.

Mike Burmester, Yvo Desmedt

The proof of soundness for many zero-knowledge schemes has been given in an incomplete way. We discuss the consequences.

Kentaro Kizaki

No abstract is available for this record.

Gustavus J. Simmons

No abstract is available for this record.

Manuel Blum, Paul Feldman, Silvio Micali

We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

Johannes Sedlmeir, Steffen Schwalm

Zero knowledge protocols provide a way of proving that a statement is true without revealing anything other than the correctness of the claim. Zero knowledge protocols have practical applications in cryptography and are used in many applications. While some applications only exist on a specification level, a direction of research has produced real-world applications. Zero knowledge protocols, also referred to as zero knowledge proofs, are a type of protocol in which one party, called the prover, tries to convince the other party, called the verifier, that a given statement is true. Sometimes the statement is that the prover possesses a particular piece of information. This is a special case of zero knowledge protocol called a zero-knowledge proof of knowledge. Formally, a zero-knowledge proof is a type of interactive proof.