Loading...
Please wait, while we are loading the content...
Linear zero-knowledge -- a note on efficient zero-knowledge proofs and arguments (1997).
| Content Provider | CiteSeerX |
|---|---|
| Author | Cramer, Ronald Damgård, Ivan |
| Abstract | We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that x 2 L with error probability less than 2 \Gammak using communication corresponding to O(jxj c )+O(k) bit commitments, where c is a constant depending only on L. We also present a 4-move perfect zero knowledge interactive argument for any NP-language L. On input x 2 L, the communication complexity is O(jxj c ) \Delta max(k; l) bits, where l is the security parameter for the prover 1 . The protocols can be based on any bit commitment scheme with a particular set of properties. We suggest efficient implementations based on discrete logarithms or factoring. As a function of the security parameters, our protocols have the smallest known asymptotic communication complexity among general proofs or arguments for NP. Moreover, the constants involved are small enough for the protocols to be practical in a realistic situation: our protocols allows proving/arguing satisfiability of a Boo... |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Efficient Zero-knowledge Proof Linear Zero-knowledge Note Security Parameter Efficient Implementation Np Language Bit Commitment Knowledge Interactive Argument General Proof Particular Set Communication Complexity Delta Max Asymptotic Communication Complexity 4-move Perfect Bit Commitment Scheme 4-move Zero-knowledge Proof System Realistic Situation Discrete Logarithm Error Probability |
| Content Type | Text |
