Abstract
We deal with computational assumptions needed in order to design secure cryptographic schemes. We suggest a classification of such assumptions based on the complexity of falsifying them (in case they happen not to be true) by creating a challenge (competition) to their validity. As an outcome of this classification we propose several open problems regarding cryptographic tasks that currently do not have a good challenge of that sort. The most outstanding one is the design of an efficient block ciphers.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ajtai, M.: Generating Hard Instances of Lattice Problems. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 99–108 (1996)
Ajtai, M., Dwork, C.: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 284–293 (1997)
Anderson, R.: Security Engineering: A guide to Building Dependeable Distributed Systems. Wiley, Chichester (2001)
Barak, B.: How to Go Beyond The Black-Box Simulation Barrier. In: Proc. of the 42nd IEEE Symposium on the Foundation of Computer Science (2001)
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols Authors. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures - HOw to Sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
Goldwasser, S., Bellare, M.: Lecture Notes on Cryptography (1996), available http://philby.ucsd.edu/cryptolib/BOOKS/gb.html
Boneh, D., Franklin, M.: Identity Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Chaum, D.: Blind signatures for untraceable payments. In: Advances in Cryptology – Proceedings of Crypto 1982, pp. 199–203. Plenum Press, NewYork (1983)
Chaum, D., Fiat, A., Naor, M.: Untraceable Electronic Cash. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 319–327. Springer, Heidelberg (1990)
Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 360–363. Springer, Heidelberg (2001)
Cramer, R., Shoup, V.: Signature Schemes Based on the Strong RSA Assumption. In: ACM Conference on Computer and Communications Security, pp. 46–51 (1999)
Diffie, W.: The First Ten Years of Public Key Cryptography. In: Simmons, G.J. (ed.) Contemporary Cryptography The Science of Information Integrity, IEEE Press, Los Alamitos (1992)
Dolev, D., Dwork, C., Naor, M.: Non-malleable Cryptography. Siam J. on Computing 30, 391–437 (2000)
Dwork, C., Lotspiech, J., Naor, M.: Digital Signets: Self-Enforcing Protection of Digital Information. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 489–498 (1996)
Dwork, C., Naor, M.: Pricing via Processing, Or, Combatting Junk Mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993)
Dwork, C., Naor, M.: Zaps and their Applications. In: Proceedings of the IEEE 41st Annual Symposium on the Foundations of Computer Science, pp. 283–293 (2000)
Dwork, C., Stockmeyer, L.:
Gennaro, R., Halevi, S., Rabin, T.: Secure Hash-and-Sign Signatures Without the Random Oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139 Springer, Heidelberg (1999)
Goldreich, O., Goldwasser, S., Micali, S.: How to Construct Random Functions. JACM 33(4), 792–807 (1986)
Goldwasser, S., Micali, S., Rivest, R.: A secure digital signature scheme. SIAM J. on Computing 17, 281–308 (1988)
Goldreich, O.: On the foundations of modern cryptography. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 46–74. Springer, Heidelberg (1997), http://www.wisdom.weizmann.ac.il/~oded/foc.html
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM J. Computing 28(4), 1364–1396 (1999)
Hada, S., Tanaka, T.: On the Existence of 3-Round Zero-Knowledge Protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 408–423. Springer, Heidelberg (1998)
Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-Way Permutations. In: STOC 1988 (1988)
Juels, A., Luby, M., Ostrovsky, R.: Security of Blind Digital Signatures. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 150–164. Springer, Heidelberg (1997)
Kerckhoffs, A.: La Cryptographie Militaire, Journal des Sciences Militaires, pp. 5–38 (1883), Available at http://www.cl.cam.ac.uk/usres/fapp2/kerckhoffs/
Luby, M., Rackoff, C.: How to construct pseudorandom permutations and pseudorandom functions. SIAM J. Computing 17, 373–386 (1988)
Naor, M.: Deniable ring authentication. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 481–498. Springer, Heidelberg (2002)
Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: Proceedings of the IEEE 38th Symposium on the Foundations of Computer Science, October 1997, pp. 458–467 (1997)
Naor, M., Reingold, O.: On the Construction of Pseudo-Random Permutations: Luby- Rackoff Revisited. Journal of Cryptology 12, 29–66 (1999)
Naor, M., Reingold, O.: From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 267–282. Springer, Heidelberg (1998)
Naor, M., Reingold, O., Rosen, A.: Pseudo-Random Functions and Factoring. Siam J. on Computing 31(5), 1383–1404 (2002)
Pinkas, B.: Fair Secure Two-Party. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 87–105. Springer, Heidelberg (2003)
Pointcheval, D., Stern, J.: Security Arguments for Digital Signatures and Blind Signatures. J. of Cryptology 13(3), 361–396 (2000)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signature and public key cryptosystems. Communications of the ACM 21, 120–126 (1978)
Rivest, R.L., Shamir, A., Tauman, Y.: How to Leak A Secret. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001)
Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Naor, M. (2003). On Cryptographic Assumptions and Challenges. In: Boneh, D. (eds) Advances in Cryptology - CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-45146-4_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40674-7
Online ISBN: 978-3-540-45146-4
eBook Packages: Springer Book Archive