Jörg Rothe
Skip Abstract Section
Abstract
In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing key components of protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol, one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.
- Agrawal, M., Kayal, N., and Saxena, N. 2002. PRIMES is in P. Unpublished manuscript.]]Google Scholar
- Ajtai, M. 1996. Generating hard instances of lattice problems. In Proceedings of the 28th ACM Symposium on Theory of Computing. ACM, New York, pp. 99--108.]] Google Scholar
- Ajtai, M. 1998. The shortest vector problem in L2 is NP-hard for randomized reductions. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, New York, pp. 10--19. Full version available on-line as ECCC TR97-047 at ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1997/TR97-047/index.html.]] Google Scholar
- Ajtai, M. and Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the 29th ACM Symposium on Theory of Computing. ACM, New York, pp. 284--293.]] Google Scholar
- Allender, E. 1985. Invertible functions. Ph.D. dissertation, Georgia Institute of Technology.]]Google Scholar
- Allender, E. 1986. The complexity of sparse sets in P. In Proceedings of the 1st Structure in Complexity Theory Conference. Lecture Notes in Computer Science, vol. 223. Springer-Verlag, New York, pp. 1--11.]] Google Scholar
- Babai, L. 1985. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on Theory of Computing (Apr.). ACM, New York, pp. 421--429.]] Google Scholar
- Babai, L. and Moran, S. 1988. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 2, 254--276.]] Google Scholar
- Balcázar, J., Díaz, J., and Gabarró, J. 1990. Structural Complexity II. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, New York.]] Google Scholar
- Balcázar, J., Díaz, J., and Gabarró, J. 1995. Structural Complexity I. EATCS Monographs on Theoretical Computer Science. 2nd edition, Springer-Verlag, New York.]]Google Scholar
- Bauer, F. 2000. Decrypted Secrets: Methods and Maxims of Cryptology. Springer-Verlag, second edition.]] Google Scholar
- Berman, L. 1977. Polynomial Reducibilities and Complete Sets. Ph.D. dissertation, Cornell Univ., Ithaca, N.Y.]] Google Scholar
- Beutelspacher, A. 1994. Cryptology. Spectrum series. Mathematical Association of America.]] Google Scholar
- Beutelspacher, A., Schwenk, J., and Wolfenstetter, K. 2001. Moderne Verfahren der Kryptographie. 4th ed. Vieweg. (in German.)]]Google Scholar
- Beygelzimer, A., Hemaspaandra, L., Homan, C., and Rothe, J. 1999. One-way functions in worst-case cryptography: Algebraic and security properties are on the house. SIGACT News 30, 4 (Dec.), 25--40.]] Google Scholar
- Boneh, D. 1999. Twenty years of attacks on the RSA cryptosystem. Notices AMS 46, 2 (Feb.), 203--213.]]Google Scholar
- Boneh, D. and Durfee, G. 2000. Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. Inf. Theory IT-46.]]Google Scholar
- Bovet, D. and Crescenzi, P. 1993. Introduction to the Theory of Complexity. Prentice-Hall, Englewood Cliffs, N.J.]] Google Scholar
- Brassard, G. and Crepeau, C. 1989. Sorting out zero-knowledge. In Advances in Cryptology---EUROCRYPT 89. Lecture Notes in Computer Science, vol. 434. Springer-Verlag, New York, pp. 181--191.]] Google Scholar
- Buchmann, J. 2001. Introduction to Cryptography. Undergraduate Texts in Mathematics. Springer-Verlag, New York.]] Google Scholar
- Burmester, M. and Desmedt, Y. 1989. Remarks on the soundness of proofs. Elec. Lett., 25, 1509--1511.]]Google Scholar
- Burmester, M., Desmedt, Y., and Beth, T. 1992. Efficient zero-knowledge identification schemes for smart cards. Comput J. 35, 1 (Feb.), 21--29.]] Google Scholar
- Burmester, M., Desmedt, Y., Piper, F., and Walker, M. 1989. A general zero-knowledge scheme. In Advances in Cryptology---EUROCRYPT 89. Lecture Notes in Computer Science, vol. 434. Springer-Verlag, New York, pp. 122--133.]] Google Scholar
- Cai, J. 1999. Some recent progress on the complexity of lattice problems. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (May). IEEE Computer Society Press, Los Alamitos, Calif., pp. 158--179.]] Google Scholar
- Cohen, M. and Hashkes, J. 1991. A system for controlling access to broadcast transmissions. European Patent Application 0 428252 A2. May.]]Google Scholar
- Coppersmith, D. 1997. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Crypt. 10, 4, 233--260.]]Google Scholar
- Diffie, W. and Hellman, M. 1976. New directions in cryptography. IEEE Trans. Inf. Theory IT-22, 6, 644--654.]]Google Scholar
- ElGamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory IT-31, 4, 469--472.]]Google Scholar
- Feige, U., Fiat, A., and Shamir, A. 1988. Zero-knowledge proofs of identity. J. Crypt. 1, 2, 77--94.]] Google Scholar
- Feigenbaum, J. 1992. Overview of interactive proof systems and zero-knowledge. In Contemporary Cryptology: The Science of Information Integrity, G. Simmons, ed. IEEE Computer Society Press, Los Alamitos, Calif., pp. 423--439.]]Google Scholar
- Fiat, A. and Shamir, A. 1986. How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology---CRYPTO '86. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, New York, pp. 186--194.]] Google Scholar
- Gill, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 4, 675--695.]]Google Scholar
- Goldreich, O. 1988. Randomness, interactive proofs, and zero-knowledge---A survey. In The Universal Turing Machine: A Half-Century Survey, R. Herken, Ed. Oxford University Press, Oxford, England, pp. 377--405.]] Google Scholar
- Goldreich, O. 1997. A taxonomy of proof systems. In Complexity Theory Retrospective II, L. Hemaspaandra and A. Selman, Eds. Springer-Verlag, New York, pp. 109--134.]] Google Scholar
- Goldreich, O. 1999. Modern cryptography, probabilistic proofs, and pseudorandomness. Algorithms and Combinatorics, vol. 17. Springer-Verlag, New York.]] Google Scholar
- Goldreich, O. 2001. Foundations of Cryptography. Cambridge University Press, Cambridge, England.]] Google Scholar
- Goldreich, O., Mansour, Y., and Sipser, M. 1987. Interactive proof systems: Provers that never fail and random selection. In Proceedings of the 28th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 449--461.]]Google Scholar
- Goldreich, O., Micali, S., and Wigderson, A. 1986. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 174--187.]]Google Scholar
- Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 3 (July), 691--729.]] Google Scholar
- Goldwasser, S. 1989. Interactive proof systems. In Computational Complexity Theory, J. Hartmanis, Ed. AMS Short Course Lecture Notes: Introductory Survey Lectures. Proceedings of Symposia in Applied Mathematics, vol. 38. American Mathematical Society, Providence, R.I., pp. 108--128.]]Google Scholar
- Goldwasser, S., Micali, S., and Rackoff, C. 1985. The knowledge complexity of interactive proof systems. In Proceedings of the 17th ACM Symposium on Theory of Computing (Apr.). ACM, New York, pp. 291--304.]] Google Scholar
- Goldwasser, S., Micali, S., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (Feb.), 186--208.]] Google Scholar
- Goldwasser, S. and Sipser, M. 1989. Private coins versus public coins in interactive proof systems. In Randomness and Computation, S. Micali, Ed., Advances in Computing Research, vol. 5. JAI Press, Greenwich, England, pp. 73--90.]]Google Scholar
- Grollmann, J. and Selman, A. 1988. Complexity measures for public-key cryptosystems. SIAM J. Computing 17, 2, 309--335.]] Google Scholar
- Hardy, G. and Wright, E. 1979. An Introduction to the Theory of Numbers. Clarendon Press, Oxford, England, 5th ed.]]Google Scholar
- Håstad, J. 1988. Solving simultaneous modular equations of low degree. SIAM J. Comput. 17, 2, 336--341. (Special issue on cryptography.)]] Google Scholar
- Hemaspaandra, L. and Ogihara, M. 2002. The Complexity Theory Companion. Springer-Verlag, New York.]] Google Scholar
- Hemaspaandra, L., Pasanen, K., and Rothe, J. 2001. If P ≠ NP then some strongly noninvertible functions are invertible. In Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (Aug.). Lecture Notes in Computer Science, vol. 2138. Springer-Verlag, New York, pp. 162--171.]] Google Scholar
- Hemaspaandra, L. and Rothe, J. 1999. Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory. J. Comput. Syst. Sci. 58, 3, 648--659.]] Google Scholar
- Hemaspaandra, L. and Rothe, J. 2000. Characterizing the existence of one-way permutations. Theoret. Comput. Sci. 244, 1--2, 257--261.]] Google Scholar
- Hemaspaandra, L., Rothe, J., and Wechsung, G. 1997. On sets with easy certificates and the existence of one-way permutations. In Proceedings of the 3rd Italian Conference on Algorithms and Complexity (Mar.). Lecture Notes in Computer Science, vol. 1203. Springer-Verlag, New York, pp. 264--275.]] Google Scholar
- Homan, C. 2000. Low ambiguity in strong, total, associative, one-way functions. Tech. Rep. TR-734. Dept. Computer Science, Univ. Rochester, Rochester, N.Y. Aug.]]Google Scholar
- Homan, C. and Thakur, M. 2002. One-way permutations and self-witnessing languages. In Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science, Stream 1 of the 17th IFIP World Computer Congress. Kluwer Academic Publishers, Aug.]] Google Scholar
- Kahn, D. 1967. The Codebreakers: The Story of Secret Writing. MacMillan, New York.]]Google Scholar
- Kaliski, Jr. B. and Robshaw, M. 1995. The secure use of RSA. CryptoBytes 1, 3, 7--13.]]Google Scholar
- Kleene, S. 1952. Introduction to Metamathematics. van Nostrand, New York and Toronto.]]Google Scholar
- Knuth, D. 1981. The Art of Computer Programming: Seminumerical Algorithms, vol. 2 of Computer Science and Information. Addison-Wesley, Reading, Mass.]] Google Scholar
- Ko, K. 1985. On some natural complete operators. Theoret. Comput. Sci. 37, 1, 1--30.]]Google Scholar
- Köbler, J., Schöning, U., and Torán, J. 1992. Graph isomorphism is low for PP. Computat. Complex. 2, 301--330.]]Google Scholar
- Köbler, J., Schöning, U., and Torán, J. 1993. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser.]] Google Scholar
- Kumar, R. and Sivakumar, D. 2001. Complexity of SVP---A reader's digest. SIGACT News 32, 3 (June), 40--52.]]Google Scholar
- Lenstra, Jr., H. 1987. Factoring integers with elliptic curves. Ann. Math. 126, 649--673.]]Google Scholar
- Lenstra, A. and Lenstra, Jr., H. 1993. The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer-Verlag, New York.]]Google Scholar
- Luby, M. 1996. Pseudorandomness and Cryptographic Applications. Princeton Computer Science Notes. Princeton University Press, Princeton, N.J.]] Google Scholar
- Maurer, U. and Wolf, S. 1999. The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms. SIAM J. Comput. 28, 5, 1689--1721.]] Google Scholar
- Micciancio, D. 2001. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput. 30, 6 (Mar.), 2008--2035.]] Google Scholar
- Miller, G. 1976. Riemann's hypothesis and tests for primality. J. Comput. Syst. Sci. 13, 300--317.]]Google Scholar
- Moore, J. 1992. Protocol failures in cryptosystems. In Contemporary Cryptology: The Science of Information Integrity, G. Simmons, Ed. IEEE Computer Society Press, Los Alamitos, Calif., pp. 541--558.]]Google Scholar
- National Institute of Standards and Technology (NIST). 1991. Digital signature standard (DSS). Fed. Reg. 56, 169 (Aug.).]]Google Scholar
- National Institute of Standards and Technology (NIST). 1992. The Digital Signature Standard, proposed by NIST. Commun. ACM, 35, 7 (July), 36--40.]] Google Scholar
- Nguyen, P. and Stern, J. 2001. The two faces of lattices in cryptology. In Proceedings of the International Conference on Cryptography and Lattices. Lecture Notes in Computer Science, vol. 2146. Springer-Verlag, New York, pp. 146--180.]] Google Scholar
- Papadimitriou, C.1994. Computational Complexity. Addison-Wesley, Reading Mass.]]Google Scholar
- Pomerance, C., and Sorenson, J.1995. Counting the integers factorable via cyclotomic methods. J. Alg., 19, 2 (Sept.), 250--265.]] Google Scholar
- Pollard, J.1974. Theorems on factorization and primality testing. Proc. Cambridge Philos. Soc. 76, 521--528.]]Google Scholar
- Rabi, M. and Sherman, A.1993. Associative one-way functions: A new paradigm for secret-key agreement and digital signatures. Tech. Rep. CS-TR-3183/UMIACS-TR-93-124. Dept. Computer Science, Univ. Maryland, College Park, Md.]] Google Scholar
- Rabi, M. and Sherman, A.1997. An observation on associative one-way functions in complexity theory. Inf. Proc. Lett., 64, 5, 239--244.]] Google Scholar
- Rabin, M.1980. Probabilistic algorithms for testing primality. J. Numb. Theory 12, 128--138.]]Google Scholar
- Rivest, R., Shamir, A., and Adleman, L.1978. A method for obtaining digital signature and public-key cryptosystems. Commun. ACM, 21, 2 (Feb.), 120--126.]] Google Scholar
- Rothe, J. and Hemaspaandra, L.2002. On characterizing the existence of partial one-way permutations. Inf. Proc. Lett., 82, 3 (May), 165--171.]]Google Scholar
- Salomaa, A.1996. Public-Key Cryptography. EATCS Monographs on Theoretical Computer Science, vol. 23. Springer-Verlag, New York.]]Google Scholar
- Schöning, U.1987. Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37, 312--323.]] Google Scholar
- Schneier, B.1996. Applied Cryptography: Protocols, Algorithms, and Source Code in C. J. Wiley, New York.]] Google Scholar
- Schnorr, C.1990. Efficient identification and signature schemes for smart cards. In Advances in Cryptology---CRYPTO '89. Lecture Notes in Computer Science, vol. 435. Springer-Verlag, New York, pp. 239--251.]] Google Scholar
- Selman, A.1992. A survey of one-way functions in complexity theory. Math. Syst. Theory 25, 3, 203--221.]]Google Scholar
- Shamir, A.1992. IP=PSPACE. J. ACM 39, 4, 869--877.]] Google Scholar
- Shamir, A.1995. RSA for paranoids. CryptoBytes 1, 3, 1--4.]]Google Scholar
- Shannon, C.1949. Communication theory of secrecy systems. Bell System Tech. J. 28, 4, 657--715.]]Google Scholar
- Shor, P.1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5, 1484--1509.]] Google Scholar
- Simmons, G.1979. Symmetric and asymmetric encryption. ACM Comput. Surv. 11, 4, 305--330.]] Google Scholar
- Simmons, G., and Norris, M.1977. Preliminary comments on the MIT public-key cryptosystem. Cryptologia 1, 4, 406--414.]]Google Scholar
- Singh, S.1999. The Code Book. The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Fourth Estate, London, England.]] Google Scholar
- Solovay, R. and Strassen, V.1977. A fast Monte Carlo test for primality. SIAM J. Comput. 6, 84--85. (Erratum appears in the same journal 7, 1, 118, 1978.)]]Google Scholar
- Stinson, D.1995. Cryptography Theory and Practice. CRC Press, Boca Raton, Fla.]] Google Scholar
- Valiant, L.1976. The relative complexity of checking and evaluating. Inf. Proc. Lett. 5, 1, 20--23.]]Google Scholar
- Welsh, D.1998. Codes and Cryptography. Oxford Science Publications. Clarendon Press, Oxford, England. 6th ed. (Reprinted with corrections.)]] Google Scholar
- Wiener, M.1990. Cryptanalysis of short RSA secret exponents. IEEE Trans. Inf. Theory IT-36, 3, 553--558.]]Google Scholar
Recommendations
Basing weak public-key cryptography on strong one-way functions
TCC'08: Proceedings of the 5th conference on Theory of cryptographyIn one of the pioneering papers on public-key cryptography, Ralph Merkle suggested a heuristic protocol for exchanging a secret key over an insecure channel by using an idealized private-key encryption scheme. Merkle's protocol is presumed to remain ...
One-way functions are essential for complexity based cryptography
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer ScienceIt is shown that many of the standard cryptographic tasks are equivalent to the usual definition of a one-way function. In particular, it is shown that for some of the standard cryptographic tasks any secure protocol for the task can be converted into a ...
On the Computational Complexity of Coin Flipping
FOCS '10: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer ScienceCoin flipping is one of the most fundamental tasks in cryptographic protocol design. Informally, a coin flipping protocol should guarantee both (1) Completeness: an honest execution of the protocol by both parties results in a fair coin toss, and (2) ...
Reviews
Jonathan Samuel Golan
This tutorial is made up of the contents of five lectures on cryptography, with topics chosen that focus on the relation between this area and complexity theory. It is aimed at the graduate student or professional level. The topics are chosen carefully, and introduced concisely and precisely. The first section is an introduction: the author begins with the basic purposes and terminology of cryptography, and introduces some classical symmetric cryptographic systems. At the end, he presents Shannon’s theorem on perfect security. The second section introduces RSA as an example of a public-key cryptosystem, and discusses its security and various possible methods of attack on it, as well as appropriate countermeasures. The third section introduces several cryptographic protocols, including some relatively new and unfamiliar ones, and again discusses the underlying mathematics and the security issues these entail. The fourth section talks about interactive proof systems and zero-knowledge protocols, with an emphasis on complexity theory as a tool in analyzing them. Finally, the last section talks about strongly noninvertible associative one-way functions and protocols based on them, concentrating on the recent work of Hemaspaandra and the author. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments