Digital content distribution systems will enable business models in the near future that cannot be predicted today. In this paper, we identify a new security problem that can be crucial to this enablement. The problem arises from the conflicting privacy and integrity goals of middlemen in digital distribution chains. Our solution is a novel system design that incorporates obfuscated digital contracts, semi-trusted contract certifiers, and zero-knowledge proofs of arithmetic relations. Our implementation and timing experiments demonstrate that our solution is practical and efficient.
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:
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.
<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>
We show how to transform any interactive proof system which is statistical zero-knowledge with respect to the honest-verifier, into a proof systemwhich is statistical zero-knowledgewith respect to any verifier. This is done by limiting the behavior of potentially cheating verifiers, without using computational assumptions or even referring to the complexity of such verifier strategies. (Previous transformations have either relied on computational assumptions or were applicable only to constant-round public-coin proof systems.) Our transformation also applies to public-coin (aka Arthur-Merlin) computational zero-knowledge proofs: We transform any ArthurMerlin proof system which is computational zero-knowledge with respect to the honest-verifier, into an Arthur-Merlin proof system which is computational zero-knowledge with respect to any probabilistic polynomial-time verifier. A crucial ingredient in our analysis is a new lemma regarding 2-universal hashing functions. 1 Introduction Zer...
Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto . In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (α, β) timing constraint : for any two processors P 1 and P 2 , if P 1 measures α elapsed time on its local clock and P 2 measures β elapsed time on its local clock, and P 2 starts after P 1 does, then P 2 will finish after P 1 does. We show that if the adversary is constrained by an (α, β) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP . We also address the more specific problem of Deniable Authentication , for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing , that is, in the standard model.
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.
<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>
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.