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.