zbMATH — the first resource for mathematics

On security preserving reductions – revised terminology. (English) Zbl 1343.94054
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, 540-546 (2011).
Summary: Many of the results in Modern Cryptography are actually transformations of a basic computational phenomenon (i.e., a basic primitive, tool or assumption) to a more complex phenomenon (i.e., a higher level primitive or application). The transformation is explicit and is always accompanied by an explicit reduction of the violation of the security of the complex phenomenon to the violation of the simpler one. A key aspect is the efficiency of the reduction. We discuss and slightly modify the hierarchy of reductions originally suggested by Leonid Levin.
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
PDF BibTeX Cite
Full Text: DOI
[1] Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SICOMP 13, 850–864 (1982); Preliminary version in 23rd FOCS (1982) · Zbl 0547.68046
[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] Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. JACM 33(4), 792–807 (1986) · Zbl 0596.65002
[5] Goldreich, O., Impagliazzo, R., Levin, L.A., Venkatesan, R., Zuckerman, D.: Security Preserving Amplification of Hardness. In: 31st FOCS, pp. 318–326 (1990)
[6] Goldreich, O., Levin, L.A.: Hard-core Predicates for any One-Way Function. In: 21st STOC, pp. 25–32 (1989)
[7] Goldwasser, S., Micali, S.: Probabilistic Encryption. JCSS 28(2), 270–299 (1984); Preliminary version in 14th STOC (1982) · Zbl 0563.94013
[8] Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SICOMP 18, 186–208 (1989); Preliminary version in 17th STOC (1985) Earlier versions date to 1982 · Zbl 0677.68062
[9] Goldwasser, S., Micali, S., Rivest, R.L.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. In: SICOMP, pp. 281–308 (April 1988) · Zbl 0644.94012
[10] Levin, L.A.: One-Way Function and Pseudorandom Generators. Combinatorica 7, 357–363 (1987) · Zbl 0641.68061
[11] Levin, L.A.: Randomness and Non-determinism. J. Symb. Logic 58(3), 1102–1103 (1993)
[12] Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, Princeton (1996) · Zbl 0849.94017
[13] Yao, A.C.: Theory and Application of Trapdoor Functions. In: 23rd FOCS, pp. 80–91 (1982)
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.