zbMATH — the first resource for mathematics

On probabilistic versus deterministic provers in the definition of proofs of knowledge. (English) Zbl 1343.94042
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 114-123 (2011).
Summary: This article points out a gap between two natural formulations of the concept of a proof of knowledge, and shows that in all natural cases (e.g., NP-statements) this gap can be bridged. The aforementioned formulations differ by whether they refer to (all possible) probabilistic or deterministic prover strategies. Unlike in the rest of cryptography, in the current context, the obvious transformation of probabilistic strategies to deterministic strategies does not seem to suffice per se. The source of trouble is “bad interaction” between the expectation operator and other operators, which appear in the definition of a proof of knowledge (reviewed here).
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
PDF BibTeX Cite
Full Text: DOI
[1] Bellare, M., Goldreich, O.: On Defining Proofs of Knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993) · Zbl 0823.94016
[2] Goldreich, O.: Foundation of Cryptography – Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016
[3] Goldreich, O.: Foundation of Cryptography – Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011
[4] Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing 18, 186–208 (1989); Preliminary Version in 17th STOC (1985) · Zbl 0677.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.