zbMATH — the first resource for mathematics

Strong proofs of knowledge. (English) Zbl 1343.94051
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, 54-58 (2011).
Summary: The concept of proofs-of-knowledge, introduced in the seminal paper of S. Goldwasser et al. [SIAM J. Comput. 18, No. 1, 186–208 (1989; Zbl 0677.68062)], plays a central role in various cryptographic applications. An adequate formulation, which enables modular applications of proofs of knowledge inside other protocols, was presented by M. Bellare and O. Goldreich [Lect. Notes Comput. Sci. 740, 390–420 (1993; Zbl 0823.94016)]. However, this formulation depends in an essential way on the notion of expected (rather than worst-case) running-time. Here we present a seemingly more restricted notion that maintains the main feature of the prior definition while referring only to machines that run in strict probabilistic polynomial-time (rather than to expected polynomial-time).
For the entire collection see [Zbl 1220.68005].
94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Barak, B., Lindell, Y.: Strict Polynomial-Time in Simulation and Extraction. SIAM J. on Comput. 33(4), 783–818 (2004) · Zbl 1060.94014
[2] Barak, B., Lindell, Y., Vadhan, S.: Lower Bounds for Non-Black-Box Zero-Knowledge. J. of Comp. and Sys. Sci. 72(2), 321–391 (2006) · Zbl 1094.68024
[3] 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
[4] Feige, U., Fiat, A., Shamir, A.: Zero-Knowledge Proofs of Identity. J. of Crpto. 1, 77–94 (1988) · Zbl 0659.94006
[5] Feige, U., Shamir, A.: Zero Knowledge Proofs of Knowledge in Two Rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, Heidelberg (1990) · Zbl 0722.68045
[6] Goldreich, O.: Secure Multi-Party Computation. Unpublished manuscript (1998), Superseded by (8, Chap. 7), http://www.wisdom.weizmann.ac.il/?oded/foc.html
[7] Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016
[8] Goldreich, O.: Foundation of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011
[9] Goldreich, O.: On Expected Probabilistic Polynomial-Time Adversaries – A suggestion for restricted definitions and their benefits. J. of Crypto. 23(1), 1–36 (2010) · Zbl 1196.94052
[10] Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. J. of the ACM 38(1), 691–729 (1991); Preliminary Version in 27th FOCS (1986) · Zbl 0799.68101
[11] Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. on Comput. 18, 186–208 (1989); Preliminary Version in 27th FOCS (1986) · Zbl 0677.68062
[12] Lindell, Y.: Constant-Round Zero-Knowledge Proofs of Knowledge. ECCC, TR11-003 (January 2011)
[13] Tompa, M., Woll, H.: Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information. University of California (San Diego), Computer Science and Engineering Department, Technical Report Number CS92-244 (June 1992); Preliminary version in 28th FOCS, pp. 472–482 (1987)
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.