Dwork, Cynthia; Shaltiel, Ronen; Smith, Adam; Trevisan, Luca 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 \textit{C. Dwork} et al., Lect. Notes Comput. Sci. 2951, 101--120 (2004; Zbl 1197.94185) Full Text: DOI