SUBQUADRATIC ZERO-KNOWLEDGE

We improve on the communication complexity of zero-knowledge proof sys tems. Let C be a Boolean circuit of size n. Previous zero-knowledge pr oof systems for the satisfiability of C require the use of Omega(kn) b it commitments in order to achieve a probability of undetected cheatin g below 2(-k). In the case k = n, the communication complexity of thes e protocols is therefore Omega(n(2)) bit commitments. In this paper, w e present a zero-knowledge proof system for achieving the same goal wi th only O(n(1+epsilon n) + k root n(1+epsilon n)) bit commitments, whe re epsilon(n) goes to zero as n goes to infinity. In the case k = n, t his is O(n root n(1+epsilon n)). Moreover, only O(k) commitments need ever be opened, which is interesting if it is substantially less expen sive to commit to a bit than to open a commitment.