Subquadratic zero-knowledge
Joan Boyar, Gilles Brassard, René Peralta · Journal of the ACM · 1995
We improve on the communication complexity of zero-knowledge proof systems.Let ~ be a 13001eancircuit of size n.Previous zero-knowledge proof systems for the satisfiability of % require the use of Q(kn) bit commitments in order to achieve a probability of undetected cheating below 2 'k.In the case k = n, the communication complexity of these protocols is therefore Q(nz) bit commitments.In this paper, we present a zero-knowledge proof system for achieving the same goal with only O(nl' 'X + k&l+ 'n ) bit commitments, where s. goes to zero as n goes to infinity.