Since 2014
Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?
|
|
| Creator |
Cramer, Ronald
Damgård, Ivan B. |
|
| Description |
We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, acircuit of size O(n), and error probability 2^−n, our protocols require communication of O(n^2) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge)interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communicationof Omega(n^3 log n) bits.Variations of the technique behind these protocols lead to other interesting applications.We first look at the Boolean Circuit Satisfiability problem and give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^−n in which there is an interactive preprocessing phase requiring communication of O(n^2)bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.As a second application, we show that Shamirs (Shens) interactive proof system for the (IP-complete) QBF problem can be transformed to a zero-knowledge proofsystem with the same asymptotic communication complexity and number of rounds. The security of our protocols can be based on any one-way group homomorphism with a particular set of properties. We give examples of special assumptions sufficient for this, including: the RSA assumption, hardness of discrete log in a prime order group, and polynomial security of Die-Hellman encryption. We note that the constants involved in our asymptotic complexities are small enough for our protocols to be practical with realistic choices of parameters.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-01-27
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18953
10.7146/brics.v4i27.18953 |
|
| Source |
BRICS Report Series; No 27 (1997): RS-27 Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free?
BRICS Report Series; Nr. 27 (1997): RS-27 Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18953/16592
|
|