IACR News item: 09 May 2015
Ronald Cramer, Ivan Damgård, Marcel Keller
ePrint Reportzero-knowledge protocols for a large class of problems where
previously the best known solution was a simple cut-and-choose style
protocol, i.e., where the size of a proof for problem instance $x$ and
error probability $2^{-n}$ was $O(|x| n)$ bits. By using our technique
to prove $n$ instances simultaneously, we can bring down the proof
size per instance to $O(|x| + n)$ bits for the same error probability
while using no computational assumptions. Examples where our technique
applies include proofs for quadratic residuosity, proofs of subgroup
membership and knowledge of discrete logarithms in groups of unknown
order, interval proofs of the latter, and proofs of plaintext
knowledge for various types of homomorphic encryption schemes. We
first propose our protocols as $\\Sigma$-protocols and extend them
later to zero-knowledge proofs of knowledge.
Additional news items may be found on the IACR news page.