zbMATH — the first resource for mathematics

On the amortized complexity of zero-knowledge protocols. (English) Zbl 1252.94056
Halevi, Shai (ed.), Advances in cryptology – CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 177-191 (2009).
Summary: 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, and proofs of plaintext knowledge for various types of homomorphic encryptions schemes. The generality of our method stems from a somewhat surprising application of black-box secret-sharing schemes.
For the entire collection see [Zbl 1173.94004].

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI