[proceedings version]

Abstract

Locally testable codes (LTCs) are error-correcting codes for which membership in the code can be tested by probing few symbols of a purported codeword. Motivated by applications in cryptography, we initiate the study of zero knowledge locally testable codes (ZK-LTCs). ZK-LTCs are LTCs which admit a randomized encoding function, such that even a malicious tester which reads a large number of codeword symbols learns essentially nothing about the encoded message.

We obtain ZK-LTCs with good parameters by applying general transformations to standard LTCs. We also obtain LTCs and ZK-LTCs which are stable in the sense that they limit the influence of adaptively corrupted symbols on the output of the testing procedure.

Finally, we apply stable ZK-LTCs for obtaining protocols for verifiable secret sharing (VSS) in which the communication complexity required for verifying a shared secret is sublinear in the secrecy threshold. We also obtain the first statistically secure VSS protocols and distributed coin-flipping protocols which use n servers, tolerate a constant fraction of corrupted servers, and have error that vanishes almost exponentially with n using only O(n) bits of communication. These improve over previous VSS and coin-flipping protocols from the literature, which require nearly quadratic communication to achieve similar guarantees.