International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 09 May 2015

Ronald Cramer, Ivan Damgård, Marcel Keller
ePrint Report ePrint Report
We propose a general technique that allows improving the complexity of

zero-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.

Expand

Additional news items may be found on the IACR news page.