Minimum Resource Zero-Knowledge Proofs (Extended Abstract)

Several resources relating to zero-knowledge protocols are considered. They are the number of envelopes used in the protocol, the number of oblivious transfer protocols executed during the protocol, and the total amount of communication required by the protocol. 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, on the basis of the existence of any one-way function, so that the probability of accepting a false theorem is less than 1/2/sup k/. >

Authors

• Joe Kilian
• Silvio Micali
• Rafail Ostrovsky

Keywords

• Protocols
• Costs
• Polynomials
• Cryptography
• Security
• Concrete
• Aggregates
• Stages Of Process
• Error Probability
• Implicit Function
• Preprocessing Stage
• Random Choice
• Interaction Length
• Security Parameter
• Non-deterministic Polynomial-time
• Knapsack Problem
• Random String
• Protocol Execution
• One-way Function
• Zero-knowledge Proof