Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)

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

Authors

• Uriel Feige
• Dror Lapidot
• Adi Shamir

Keywords

• Polynomials
• Cryptography
• Cryptographic protocols
• Writing
• Proposals
• Random String
• Zero-knowledge Proof
• Proof Of Knowledge
• Zero Knowledge
• Bulletproofs
• Non-interactive Zero-knowledge
• Permutation
• Conceptual Knowledge
• Random Permutations
• Head And Tail
• Original Protocol
• General Assumption
• Preprocessing Stage
• Sound Properties
• Exponential Time
• Encryption Scheme
• Number Theory
• Random Bits
• Proof Sketch
• Hamiltonian Path
• Signature Scheme
• Probabilistic Polynomial Time
• Single Statement
• One-way Function
• Black Box