# Multiple non-interactive zero knowledge proofs based on a single random string

@article{Feige1990MultipleNZ, title={Multiple non-interactive zero knowledge proofs based on a single random string}, author={Uriel Feige and Dror Lapidot and Adi Shamir}, journal={Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science}, year={1990}, pages={308-317 vol.1} }

The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomially many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions. The constructions can be used in cryptographic applications in which the prover is restricted to polynomial time, and they are much simpler than earlier (and less capable… Expand

#### Topics from this paper

#### 248 Citations

Non-Interactive Zero Knowledge

- Mathematics
- 1990

Abstract : We investigate the possibility of disposing of interaction between Prover and Verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, we… Expand

Publicly Verifiable Non-Interactive Zero-Knowledge Proofs

- Mathematics, Computer Science
- CRYPTO
- 1990

In this paper we construct the first publicly verifiable non-interactive zero-knowledge proof for any NP statement under the general assumption that one way permutations exist. If the prover is… Expand

Randomness-eecient Non-interactive Zero Knowledge

- 2007

The model of Non-Interactive Zero-Knowledge allows to obtain minimal interaction between prover and veriier in a zero-knowledge proof if a public random string is available to both parties. In this… Expand

Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP

- Mathematics, Computer Science
- ICALP
- 1999

We show that any language L in NP has a noninteractive zero-knowledge proof system which uses Θ(log(1/s) + nƐ) random bits, where s is the soundness error, n the length of the input and Ɛ can be any… Expand

Communication Efficient Zero-Knowledge Proofs of Knowledge (With Applications to Electronic Cash)

- Mathematics, Computer Science
- STACS
- 1992

We show that, after a constant-round preprocessing stage, it is possible to give any polynomial number of Non-Interactive Zero-Knowledge Proofs of Knowledge for any NP language. Our proof-system is… Expand

Non-interactive Zero Knowledge Proofs in the Random Oracle Model

- Computer Science, Mathematics
- C2SI
- 2019

The Fiat-Shamir transform is a well known and widely used technique to convert any constant-round public-coin honest-verifier zero- knowledge proof or argument system in a non-interactive zero-knowledge (NIZK) argument system. Expand

The power of preprocessing in zero-knowledge proofs of knowledge

- Mathematics, Computer Science
- Journal of Cryptology
- 2004

We show that, after a constant-round preprocessing stage, it is possible for a prover to prove knowledge of a witness for any polynomial-time relation without any further interaction. The number of… Expand

A Gentle Introduction to SNARKs

- 2019

Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are non-interactive systems with short proofs (i.e., independent of the size of the witness) that enable verifying NP… Expand

Simulation-Sound Non-Interactive Zero Knowledge

- Computer Science
- 2000

This paper construct simulation-so und NIZK proofs for any NPcomplete language which remain secure even after the adversary has seen any number of simulated proofs of its chosing. Expand

Short Non-Interactive Cryptographic Proofs

- Mathematics, Computer Science
- Journal of Cryptology
- 2015

It is shown how to produce short proofs of theorems such that a distrusting Verifier can be convinced that the theorem is true yet obtains no information about the proof itself, and is called ``discreet. Expand

#### References

SHOWING 1-10 OF 18 REFERENCES

Non-Interactive Zero Knowledge

- Mathematics
- 1990

Abstract : We investigate the possibility of disposing of interaction between Prover and Verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, we… Expand

Publicly Verifiable Non-Interactive Zero-Knowledge Proofs

- Mathematics, Computer Science
- CRYPTO
- 1990

In this paper we construct the first publicly verifiable non-interactive zero-knowledge proof for any NP statement under the general assumption that one way permutations exist. If the prover is… Expand

Non-Interactive Zero-Knowledge with Preprocessing

- Mathematics, Computer Science
- CRYPTO
- 1988

It is proved that the existence of any secure probabilistic encryption scheme is enough for Non-Interactive Zero-Knowledge in a modified model and the ability to prove a randomly chosen theorem allows to subsequently prove noninteractively and in Zero- knowledge any smaller size theorem whose proof is discovered. Expand

Proofs that yield nothing but their validity and a methodology of cryptographic protocol design

- Computer Science
- 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
- 1986

This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge. Expand

Non-interactive zero-knowledge and its applications

- Mathematics, Computer Science
- STOC '88
- 1988

It is shown that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string, and this result is used to construct the first public-key cryptosystem secure against chosen ciphertext attack. Expand

New Paradigms for Digital Signatures and Message Authentication Based on Non-Interative Zero Knowledge Proofs

- Computer Science
- CRYPTO
- 1989

Noninteractive zero knowledge proofs in a network which have the property that anyone in the network can individually check correctness while the proof is zero knowledge to any sufficiently small coalition are shown. Expand

Minimum resource zero knowledge proofs

- Mathematics, Computer Science
- 30th Annual Symposium on Foundations of Computer Science
- 1989

It is shown that after a preprocessing stage consisting of O(k) executions of oblivious transfer, any polynomial number of NP-theorems of any polysize can be proved noninteractively and in zero knowledge. Expand

Non-Interactive Zero-Knowledge Proof Systems

- Mathematics, Computer Science
- CRYPTO
- 1987

The result is strengthened by showing that Non-Interactive Zero-Knowledge Proof Systems exist based on the weaker and well-known assumption that quadratic residuosity is hard. Expand

How to generate cryptographically strong sequences of pseudo random bits

- Mathematics, Computer Science
- 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)
- 1982

A general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits is presented. Expand

Bit Commitment Using Pseudo-Randomness

- Computer Science
- CRYPTO
- 1989

We show how a pseudo-random generator can provide a bit commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the… Expand