zbMATH — the first resource for mathematics

Proving computational ability. (English) Zbl 1343.94041
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, 6-12 (2011).
Summary: We investigate extending the notion of a proof of knowledge to a proof of the ability to perform some computational task. We provide some definitions and protocols for this purpose.
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
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] Brassard, G., Crépeau, C., Laplante, S., Léger, C.: Computationally Convincing Proofs of Knowledge. In: Jantzen, M., Choffrut, C. (eds.) STACS 1991. LNCS, vol. 480, Springer, Heidelberg (1991) · Zbl 0773.68024
[3] Feige, U., Fiat, A., Shamir, A.: Zero-Knowledge Proofs of Identity. Journal of Cryptology 1, 77–94 (1988) · Zbl 0659.94006
[4] Feige, U., Shamir, A.: Witness Indistinguishability and Witness Hiding Protocols. In: Proceedings of the Twenty Second Annual Symposium on the Theory of Computing, pp. 416–426. ACM, New York (1990)
[5] Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. on Computing 18(1), 186–208 (1989) (Preliminary Version in the 7th STOC, 1985) · Zbl 0677.68062
[6] 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 Dept. Technical Report Number CS92-244 (June 1992) (Preliminary Version in the 27th FOCS, pp. 472–482, 1987)
[7] Yung, M.: Zero-knowledge proofs of computational power. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 196–207. Springer, Heidelberg (1990)
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.