×

List-decoding of linear functions and analysis of a two-round zero-knowledge argument. (English) Zbl 1197.94185

Naor, Moni (ed.), Theory of cryptography. First theory of cryptography conference, TCC 2004, Cambridge, MA, USA, February 19–21, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21000-8/pbk). Lecture Notes in Computer Science 2951, 101-120 (2004).
Summary: Dwork and Stockmeyer showed 2-round zero-knowledge proof systems secure against provers which are resource-bounded during the interaction. The resources considered are running time and advice (the amount of precomputed information). We re-cast this construction in the language of list-decoding. This perspective leads to the following improvements:
1. We give a new, simpler analysis of the protocol’s unconditional security in the advice-bounded case. Like the original, the new analysis is asymptotically tight.
2. When the prover is bounded in both time and advice, we substantially improve the analysis of Dwork and Stockmeyer: we prove security under a worst-case (instead of average-case) hardness assumption. Specifically, we assume that there exists \(g\in \text{DTIME}(2^s)\) such that \(g\) is hard in the worst case for MAM circuits of size \(O(2^{s(\frac{1}{2}+\gamma)})\) for some \(\gamma>0\). Here \(s\) is the input length and MAM corresponds the class of circuits which are verifiers in a 3-message interactive proof (with constant soundness error) in which the prover sends the first message. In contrast, Dwork and Stockmeyer require a function that is average-case hard for “proof auditors,” a model of computation which generalizes randomized, non-deterministic circuits.
3. Our analyses rely on new results on list-decodability of codes whose codewords are linear functions from \(\{0,1\}^{\ell}\) to \(\{0,1\}^{\ell}\). For (1), we show that the set of all linear transformations is a good list-decodable code. For (2), we give a new, non-deterministic list-decoding procedure which runs in time quasi-linear in \(\ell\).
For the entire collection see [Zbl 1048.94003].

MSC:

94A60 Cryptography
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94B35 Decoding
PDFBibTeX XMLCite
Full Text: DOI