Minimum resource zero knowledge proofs
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 474-479
- https://doi.org/10.1109/sfcs.1989.63521
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/.Keywords
This publication has 6 references indexed in Scilit:
- Non-Interactive Oblivious Transfer and ApplicationsPublished by Springer Nature ,2001
- Pseudo-random generation from one-way functionsPublished by Association for Computing Machinery (ACM) ,1989
- A randomized protocol for signing contractsCommunications of the ACM, 1985
- The knowledge complexity of interactive proof-systemsPublished by Association for Computing Machinery (ACM) ,1985
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982