Public Key Cryptography (Spring 2005) course

Administrative

• Note that in the account details given in class, the username and password are identical.
• Exercises can be submitted in class, or in the course mailbox.
• The final exam in the course was held in room 5 of the Feinberg Graduate School at 2005-06-14 10:00-13:00.

Resources

require a subscription to some web service, but can be accessed through the Weizmann Institute web proxy. The links denoted by

General

• Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. [online]
•  Shafi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography. [online] [photocopy]
• Bruce Schneier, Applied Cryptography, 2nd edition,  John Wiley & Sons, 1996
• Victor Shoup, A computational introduction to number theory and algebra, a book in preparation. [online]
• Dana Angluin, Lecture notes on the complexity of some problems in number theory, Yale University Computer Science Department, technical report TR-243, 1982 [online] [photocopy]
• Most recent crypto papers can be found in proceedings on SpringerLink or in IACR ePrint.
• The alternative (non-official) course page maintained by Yossi Oren. [online]

Lecture 1: Introduction

• W.Diffie and M.E.Hellman, New directions in cryptography, IEEE Transactions on Information Theory, IT-22, 6, pp.644-654, 1976, [online]
• Ralph C. Merkle, Secure communications over insecure channels, Communications of the ACM, vol. 21 no. 4, pp. 294-299, 1978. [online] [online]

Lecture 2: Knapsacks

• R. C. Merkle, M. E. Hellman, Hiding information and signatures in trap door knapsacks, IEEE Transactions on Information Theory, IT-24(5),  pp. 525-530, 1978.
• Adi Shamir, On the cryptocomplexity of knapsack systems, proceedings of 11th ACM symposium on Theory of Computing, ACM, 1979. [online]
• Richard Schroeppel, Adi Shamir, A T=O(2^(n/2)), S=O(2^(n/4)) Algorithm for certain NP-Complete problems, SIAM Journal on Computing, 10(3), pp. 456-464, 1981.
• Adi Shamir, A Polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem,
  proceedings of Crypto '82 , pp. 279-288, Plenum Press, 1983. [online] [photocopy]
  IEEE Transactions on Information Theory, IT-30, pp. 699-704, 1984
• Leonard M. Adleman, On breaking generalized knapsack public key cryptosystems, proceedings of 15th ACM Symposium on Theory of Computing, ACM, 1983. [online] [online]
• E. F. Brickell, Breaking Iterated Knapsacks, proceedings of Crypto '84, LNCS 196, pp. 342-358, Springer-Verlag, 1985 [online] [online]
• David Wagner, A Generalized Birthday Problem (extended abstract), proceedings of Crypto 2002, LNCS 2442, pp. 288-304, Springer-Verlag, 2002, [online] (see also: long version [online])

Lecture 3: Incremental hashing, McEliece, computational number theory

•  R.J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report 42-44, Jet Propulsion Lab., California Institute of Technology, pp. 114- 116, 1978
• "The McEliece public-key encryption", Section 8.5 in the Handbook of Applied Cryptography. [online] (see also Helger Lipmaa's web page).
  
• Manindra Agrawal, Nitin Saxena, Neeraj Kayal, PRIMES is in P (revised) [online]
• Resources on computational number theory are listed above.

Lecture 4: Computational number theory (cont.)

• Resources on computational number theory are listed above.

Lecture 5: Discrete log, index calculus algorithms for factoring and discrete log

• A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, proceedings of 22nd ACM Symp. on Theory of Computing, 564-572, 1990. [online]
• Peter Stevenhager, The number field sieve, lecture notes. [online]
• Carl Pomerance, Smooth numbers and the quadratic sieve, lecture notes. [online]
  
• Carl Pomerance,  A Tale of Two Sieves,  Notices of the AMS, Dec. 1996, 1473--1485, 1996. [online] [online]
• Arjen K. Lenstra, Integer Factoring, Designs, Codes and Cryptography, vol. 19(1), 101--128 , 2000. [online]
• The usual resources on computational number theory, listed above.

Lecture 6: Properties and variants of RSA

• Amos Fiat, Batch RSA, proceedings of Crypto 1989, 175-185, 1989 [online] [online]
• Adi Shamir, RSA for Paranoids, RSA Laboratories' CryptoBytes, vol. 1(3), 1,3-4, 1995 [online]
• Adi Shamir, On the generation of cryptographically strong pseudo-random sequences, proceedings of the 8th Colloquium on Automata, Languages and Programming, LNCS 115, 544-550, Springer 1981, or:
  Adi Shamir, On the generation of cryptographically strong pseudorandom sequences,  ACM Transactions on Computer Systems, vol. 1, issue 1., 38-44, 1983 [online] [online]
• Adi Shamir, Memory efficient variants of public-key schemes for smart card applications, proceedings of Eurocrypt 1994, 445-449, 1994  [online] [online]

Lecture 7:  ESIGN, Paillier, Ong-Schnorr-Shamir

• E. F. Brickell, J. M. DeLaurentis, An attack on a signature scheme proposed by Okamoto and Shiraishi, proceedings of Crypto '85, 28--, 1996 [online] [online]
• H. Ong, Claus-Peter Schnorr, Adi Shamir, An efficient signature scheme based on quadratic equations, proceedings of ACM Symposium on Theory of Computing, 208-216, ACM, 1984 [online] [online]
• C. P. Schnorr, J. Pollard, An efficient solution of the congruence x² + ky² = m (mod n), IEEE Transactions on Information Theory,  vol. 33(5), 702-709, 1987
  
• Jeffrey Shallit, An exposition of Pollard's algorithm for quadratic congruences, technical report 84-006, University of Chicago, 1984 [online]
• Leonard M. Adleman, Dennis R. Estes, Kevin S. McCurley, Solving bivariate quadratic congruences in random polynomial time, Mathematics of Computation, vol. 48, no. 177, 17—28, 1987 [online] [online]
  (An alternative to Pollard-Schnorr which is less efficient but provably correct.)
• Pascal Paillier, Public-key cryptosystem based on composite degree residuosity classes, proceedings of Eurocrypt '99, LNCS 1592, 223-238, Springer-Verlag, 1999 [online]
• Ong-Schnorr-Shamir and ESIGN in Applied Cryptography.
• Note that to implement Pollard's algorithm, you'll also need the following composition formula:
  
(x₁²-ky₁²)(x₂²-ky₂²) = (x₀²-ky₀²)  where  x₀=(x₁x₂+ky₁y₁) and y₀=(x₁y₂+x₂y₁)

Lectures 8-11:

• Jacques Patarin, Hidden Fields Equations (HFE) and Isomorphisms of polynomials (IP): two new families of asymmetric algorithms, proc. Eurocrypt '96, 33-48., Springer Verlag, 1996 [online]
• Adi Shamir, On the generation of multivariate polynomials which are hard to factor, proceedings of 25th ACM Symposium on Theory of Computing, 796-804, 1993 [online] [online]   [slides (4MB)]
• Aviad Kipnis, Adi Shamir, Cryptanalysis of the oil & vinegar signature scheme, proceedings of Crypto '98, LNCS 1462, 257-, Springer-Verlag, 1998 [online] [online]   [slides (5MB)]
• Aviad Kipnis, Adi Shamir, Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, proceedings of Crypto 1999, LNCS 1666, 19-30, Springer, 1999
• Dan Boneh, Matt Franklin, Identity based encryption from the Weil pairing, SIAM J. of Computing, Vol. 32, No. 3, pp. 586-615, 2003, [online]