Linear zero-knowledge---a note on efficient zero-knowledge proofs and arguments
Ronald Cramer, Ivan Damgård · 1997
We present a 4-move zero-knowledge proof system [21] for any NP language L, which allows showing that z E L with error probability y less than 2-k using com-Email: ivan~dainri.aau.dk ~BMic ReSear& in Computer Science, Center of the Danish National Research Foundation 1The meaning of 1 is that if the prover is unable tO SO1vean instance of a hard problem of size 1 before the protocol is finished, he can cheat with probability at most Z-k able.Thus, if we use k = n, the number of commitments required for the proof is linear in n.Finally, we present an application of our results that results in a protocol for oblivious transfer requiring O(1) commitments of size O(k) bits for a maximal cheating probability y of 2-k.Corresponding results for multipart y computations follow from this.'Here c1 is any positive constant and cz = 0(1/cl).