A uniform-complexity treatment of encryption and zero-knowledge

We provide a treatment of encryption and zero-knowledge in terms of uniform complexity measures. This treatment is appropriate for cryptographic settings modeled by probabilistic polynomial-time machines. Our uniform treatment allows the construction of secure encryption schemes and zero-knowledge proof systems (for allNP) using only uniform complexity assumptions. We show that uniform variants of the two definitions of security, presented in the pioneering work of Goldwasser and Micali, are in fact equivalent. Such a result was known before only for nonuniform formalization. Nonuniformity is implicit in all previous treatments of zero-knowledge in the sense that a zero-knowledge proof is required to “leak no knowledge” onall instances. For practical purposes, it suffices to require that it isinfeasible to find instances on which a zero-knowledge proof “leaks knowledge.” We show how to construct such zero-knowledge proof systems for every language inNP, using only a uniform complexity assumption. Properties of uniformly zero-knowledge proofs are investigated and their utility is demonstrated. This research was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities. Revision of this work was supported by Grant No. 89-00312 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.     

Practical zero-knowledge proofs: Giving hints and using deficiencies

New zero-knowledge proofs are given for some number-theoretic problems. All of the problems are in NP, but the proofs given here are much more efficient than the previously known proofs. In addition, these proofs do not require the prover to be superpolynomial in power. A probabilistic polynomial-time prover with the appropriate trapdoor knowledge is sufficient. The proofs are perfect or statistical zero-knowledge in all cases except one.This research was supported in part by NSA Grant No. MDA904-88-H-2006.In this paper it will at times be convenient to think of the verifier as being named Vic, and the prover being named Peggy. Thus, he will refer to the verifier and she will refer to the prover.     

Definitions and properties of zero-knowledge proof systems

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox-simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2].We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to RP. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.This research was partially supported by the Fund for Basic Research Administered by the Israeli Academy of Sciences and Humanities. Preliminary versions of this work have appeared in [O1] and [O2].     

Elliptic curve implementation of zero-knowledge blobs

In [2] the authors show how to construct the building blocks for perfect zero-knowledge proofs called blobs using the discrete log problem. Contrary to what they remark on p. 73 of [2], we argue that the Mordell group of an elliptic curve is more suitable than the multiplicative group of a finite field for the construction of a hard cryptographic suite of problems.     

Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer

In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this paper, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems:

A language-dependent cryptographic primitive

In this paper we provide a new cryptographic primitive that generalizes several existing zero-knowledge proofs and show that if a languageL induces the primitive, then there exists a perfect zero-knowledge proof forL. In addition, we present several kinds of languages inducing the primitive, some of which are not known to have a perfect zero-knowledge proof.     

A discrete logarithm implementation of perfect zero-knowledge blobs

Brassard and Crépeau [BCr] introduced a simple technique for producing zero-knowledge proof systems based on blobs. As is to be expected, their implementation rests on an unproven cryptographic assumption, specifically, that it is easy to generate numbers that are difficult to factor. In this paper we present an implementation of blobs based on a different cryptographic assumption, specifically, that it is easy to generate primes p over which it is difficult to compute discrete logarithms. If, in addition, we can produce a generator for Z _p ^* , this implementation then has the advantage that it leads to proof systems which are perfect zeroknowledge, rather than only almost perfect zero-knowledge.The relationship between factoring and finding discrete logarithms is not well understood, although Bach [Bac1] is an important contribution. Given our current state of number theoretic knowlege, there is no reason to prefer the cryptographic assumption required by one of these implementations over that required by the other. In any event, we introduce the notion of a product blob, whose favorable properties depend only on at least one of these assumptions holding.The first author was supported in part by NSA Grant MDA 904-84-H-00171. The second author was supported in part by NSF Grant DCR-8602562.     

A Note on Constant-Round Zero-Knowledge Proofs of Knowledge

In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all $\mathcal {NP}$ . The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO, 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all $\mathcal {NP}$ is folklore, to the best of our knowledge, since no proof of this fact has been published.     

Divertible and Subliminal-Free Zero-Knowledge Proofs for Languages

Divertible proofs are extensions of interactive proofs in which an active eavesdropper, the warden, makes the prover and the verifier untraceable. The warden is transparent to both the prover and the verifier. With subliminal-free proofs the warden controls subliminal messages. In this paper we present divertible and subliminal-free zero-knowledge proofs for various languages. We consider both graph isomorphism and Received September 1992 and revised September 1995 and May 1997     

Which Languages Have 4-Round Zero-Knowledge Proofs?

We show that if a language L has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then [`(L)] ? MA\bar{L}\in \mathsf{MA}. Assuming the polynomial hierarchy does not collapse, this means in particular that NP-complete languages do not have 4-round zero-knowledge proofs with black-box simulation.     

Some estimates pertaining to sensitivity and robust stability of input-output systems

The estimates derived in this paper strengthen the available results on sensitivity and robust stability of input-output systems. Two types of estimates are discussed: the “sensitivity type”, which establishes a bound for the output change when the system is perturbed but the input remains the same, and the “robustness type”, which gives a bound for the output change when the input changes but the perturbation does not. First, estimates for general systems over abstract extended spaces are derived; these results are then applied to (1) two frequently used control configurations, and (2) systems governed by vector integral and differential equations on the time domain [0, ∞). The applications of the estimates are illustrated by several examples. This research was supported by the National Science Foundation under Grant #DMS-9102910     

Handling Expected Polynomial-Time Strategies in Simulation-Based Security Proofs

The standard class of adversaries considered in cryptography is that of strict polynomial-time probabilistic machines. However, expected polynomial-time machines are often also considered. For example, there are many zero-knowledge protocols for which the only known simulation techniques run in expected (and not strict) polynomial time. In addition, it has been shown that expected polynomial-time simulation is essential for achieving constant-round black-box zero-knowledge protocols. This reliance on expected polynomial-time simulation introduces a number of conceptual and technical difficulties. In this paper, we develop techniques for dealing with expected polynomial-time adversaries in simulation-based security proofs. An extended abstract of this work appeared in the 2nd Theory of Cryptography Conference (TCC), 2005. This research was supported in part by Grant No. 2004240 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel. Yehuda Lindell: Some of this work was carried out while Y. Lindell was at IBM T.J. Watson.     

An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum et al. [5]. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions [11] versus those based on specific algebraic assumptions [7]. Recently, this gap was reduced to a polylogarithmic factor [17]; we further reduce the gap to a constant factor. Our proof system relies on the existence of one-way permutations (or trapdoor permutations for bounded provers). Our protocol is stated in the hidden bit model introduced by Feige et al. [11]. We show how to prove that an n -gate circuit is satisfiable, with error probability 1/n ^O(1) , using only O(n lg n) random committed bits. For this error probability, this result matches to within a constant factor the number of committed bits required by the most efficient known interactive proof systems. Received 20 November 1995 and revised 7 October 1996     

How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge

This paper studies perfect zero-knowledge proofs. Such proofs do not allow any simulation errors, and therefore techniques from the study of statistical zero-knowledge (where a small error is allowed) do not apply to them. We introduce a new error shifting technique for building perfect simulators. Using this technique we give the first complete problem for the class of problems admitting non-interactive perfect zero-knowledge (NIPZK) proofs, a hard problem for the class of problems admitting public-coin PZK proofs, and other applications.     

一种基于ECC的高效双向身份认证

椭圆曲线密码体制和零知识证明在密码学里面得到了广泛的研究和应用.文章提出了一种基于椭圆曲线密码体制的零知识证明的双向身份认证方案,该方案用椭圆曲线密码体制代替传统的公钥密码体制,并将椭圆曲线的算法加入到了零知识证明的思想里面,使得认证的安全性和准确度有了很大的提高.     

Non-interactive Timestamping in the Bounded-Storage Model

A timestamping scheme is non-interactive if a stamper can stamp a document without communicating with any other player. The only communication done is at validation time. Non-Interactive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. Non-Interactive timestamping, however, is not possible against polynomial-time adversaries that have unbounded storage at their disposal. As a result, no non-interactive timestamping schemes were constructed up to date. In this paper we show that non-interactive timestamping is possible in the bounded-storage model, i.e., if the adversary has bounded storage, and a long random string is broadcast to all players. To the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded-storage model but is impossible in the “standard cryptographic setting,” even when assuming “standard” cryptographic assumptions. We give an explicit construction that is secure against all bounded storage adversaries and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time. A preliminary version of this paper appeared in CRYPTO 2004 [24]. Tal Moran: Some of this work was done while at Tel-Aviv University. Ronen Shaltiel: Some of this work was done while at the Weizmann Institute of Science and supported by the Koshland Scholarship. This research was also supported by Grant No 2004329 from the United States-Israel Binational Science Foundation (BSF) and by ISF grant 686/07. Amnon Ta-Shma: Supported by the Binational Science Foundation, by the Israel Science Foundation, and by the EU Integrated Project QAP.     

Experimental study on a novel polarization state generator

Duetothe spoilageinduced bythe polarization-relatedeffects (PRE) in high-speed(≥10 Gb/s/channel) opti-cal fiber communication systems ,it is necessary to in-vestigate the effect of PRE on optical components andentire transmission systems .In general , PR…     

Trading Help for Interaction in Statistical Zero-Knowledge Proofs

Abstract. We define interactive and non-interactive statistical zero-knowledge proofs with (limited) help, as proofs that can be almost perfectly simulated, where the prover and the verifier share a reference string that is computed by a probabilistic polynomial-time trusted third party that receives as input the statement to be proven (i.e. the input to the protocol). We compare these models with the standard interactive and non-interactive SZK models, trying to understand when this form of help can replace the interaction between the prover and the verifier and vice versa. We show that every promise problem that has an SZK protocol with help also has one without help. As for the opposite, we show non-interactive SZK proofs with help for natural languages for which only interactive SZK proofs are known. In order to achieve that, we introduce a complete problem for the class of promise problems that have non-interactive SZK proofs with help.     

Zero-knowledge proofs of identity

In this paper we extend the notion of interactive proofs of assertions to interactive proofs of knowledge. This leads to the definition of unrestricted input zero-knowledge proofs of knowledge in which the prover demonstrates possession of knowledge without revealing any computational information whatsoever (not even the one bit revealed in zero-knowledge proofs of assertions). We show the relevance of these notions to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. We describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than RSA-based identification schemes. The advantages of thinking in terms of proofs of knowledge rather than proofs of assertions are demonstrated in two efficient variants of the scheme: unrestricted input zero-knowledge proofs of knowledge are used in the construction of a scheme which needs no directory; a version of the scheme based on parallel interactive proofs (which are not known to be zero knowledge) is proved secure by observing that the identification protocols are proofs of knowledge.     

Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces

We define a novel notion of quasi-adaptive non-interactive zero-knowledge (NIZK) proofs for probability distributions on parameterized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parameterized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give computationally sound quasi-adaptive NIZKs that are shorter and more efficient than Groth–Sahai NIZKs. For many cryptographic applications quasi-adaptive NIZKs suffice and our constructions can lead to significant efficiency improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the eXternal Diffie Hellman (XDH) assumption our proofs are even competitive with Random Oracle-based \(\Sigma \)-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining linear equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g., applications using Cramer–Shoup projective hash proofs. Our techniques also lead to the shortest known (ciphertext) fully secure identity-based encryption scheme under standard static assumptions. Further, we also get a short publicly verifiable CCA2-secure IBE scheme.