Public Key Cryptography (Spring 2007) course
Instructor: Adi Shamir
Teaching assistant: Ya'akov
Hoch
Administrative
- Exercises should be submitted in class two weeks after receiving them.
- There will be no classes during Passover (April 2 and April 9)
- The exam will take place on Monday, July 9th
- Exercises submitted by Wednesday will be graded
and returned in my mailbox
Resources
Most resources are available [online].
The links denoted by 
require a username and password (given in
class).
If none of the above is given and you obtain the paper by other means, please
e-mail a copy to the TA, so the TA will prepare additional copies for the
library.
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]
- Bruce Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, 1996
- Victor Shoup, A computational introduction to number theory and algebra. [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]
- Many recent crypto papers can be found in IACR ePrint.
- A CD containing the proceedings of Crypto, Eurocrypt and Asiacrypt is available from the library.
Exercises
Exercise 5 (due May 21)
Exercise 6 (due May 28)
Exercise 8 (due June 11)
Exercise 9 (due June 18)
Lecture 1: Introduction and Knapsacks
- W.Diffie and M.E.Hellman, New directions in cryptography, IEEE Transactions on Information Theory, IT-22, 6, pp.644-654, 1976, [online]
- J. Ellis's account of Public Key Cryptography The Story of Non-Secret Encryption
- Ralph C. Merkle, Secure
communications over insecure channels, Communications of the ACM, vol.
21 no. 4, pp. 294-299, 1978. [online]
- 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. [online]
Lecture 2: Knapsacks (Continued)
- Adi Shamir, On the cryptocomplexity of knapsack systems, proceedings of 11th ACM symposium on Theory of Computing, ACM, 1979. [online]
- Adi Shamir, A
Polynomial-time algorithm for breaking the basic Merkle-Hellman
cryptosystem,
proceedings of Crypto '82 , pp. 279-288, Plenum Press, 1983. [online]
IEEE Transactions on Information Theory, IT-30, pp. 699-704, 1984 [online] - Leonard M. Adleman, On
breaking generalized knapsack public key cryptosystems, proceedings of
15th ACM Symposium on Theory of Computing, ACM, 1983. [online]
- E. F. Brickell, Breaking
Iterated Knapsacks, proceedings of Crypto '84, LNCS 196, pp. 342-358,
Springer-Verlag, 1985. [online]
- H.W. Lenstra, Integer Programming with a Fixed Number of Variables, Mathematics of Operations Research, Vol 8, no. 4, November 1983. [online]
Lecture 3: Lattices and their applications
- Lecture slides: GGH, NTRU1, NTRU2
- M. Ajtai, C. Dwork, A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence, proceedings of STOC 1997 [online]
- O. Goldreich, S. Goldwasser and S. Halevi, Public-Key Cryptosystems from Lattice Problems, proceedings of CRYPTO'97, 112-131, 1997 [online]
- D. Coppersmith, A. Shamir, Lattice attacks on NTRU, proceedings of EUROCRYPT 97, 52--61, 1997 [online]
- D. Micciancio, Lattices in Cryptography and Cryptanalysis, course lecture notes, 1999 [online]
- Alexander May, Cryptanalisis of NTRU, preprint, 1997 [online]
- J. H. Silverman, Dimension-Reduced Lattices, Zero-Forced Lattices, and the NTRU Public Key Cryptosystem, technical report, NTRU Cryptosystems Inc., 1999, [online]
- J. Proos, Imperfect Decryption and an Attack on the NTRU Encryption Scheme, preprint [online]
Lecture 4: Computational number theory
- Resources on computational number theory are listed above.
Lecture 5, 6: Discrete log, properties and variants of RSA
- Avital Schrift, Adi Shamir, The Discrete Log is Very Discreet, proceedings of 22nd ACM Symposium on Theory of Computing, ACM, 1990 [online]
- Avital Schrift, Adi Shamir, The Discrete Log is Very Discreet (slides by Adi Shamir) [online] (1.7MB)
- Michael Ben-Or, Benny Chor, Adi Shamir, On the Cryptographic Security of Single RSA Bits, proceedings of 15th ACM Symposium on Theory of Computing, ACM, 421-430,1983 [online]
- R.L. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, Vol.21, Nr.2, 1978, S.120-126 [online]
- D. Ruinskiy, A. Shamir, B. Tsaban, Length-Based Cryptanalysis: The Case of Thompson’s Group [online]
Lecture 7: RSA variants and factoring algorithms
- Carl Pomerance, A Tale of Two Sieves, Notices of the AMS, Dec. 1996, 1473--1485, 1996 [online]
- Arjen K. Lenstra, Integer Factoring, Designs, Codes and Cryptography, vol. 19(1), 101--128 , 2000 [online]
- Matthew E. Briggs, An Introduction to the General Number Field Sieve, M.Sc. thesis, Virginia Polytechnic Institute and State University, [online]
Lecture 8: Twirl and Twinkle
- Lecture slides [TWIRL] [Hardware assisted factoring]
Lecture 9: DSS, Online/Offline signatures, Ring signatures
- Digital Signature Standard (DSS) [online]
- R. Rivest, A. Shamir, Y. Tauman, How to Leak a Secret, presentation slides by Adi Shamir [online] (4.6MB)
- R. Rivest, A. Shamir, Y. Tauman, How to Leak a Secret, proceedings of Asiacrypt 2001, 552--565, 2001 [online]
- A. Shamir, Y. Tauman, Improved Online/Offline Signature Schemes, presentation slides by Adi Shamir [online] (2.4MB)
- A. Shamir, Y. Yauman, Improved Online/Offline Signature Schemes, proceedings of Crypto 2001, 355--367, 2001 [online]
Lecture 10: Multivariate cryptographic schemes and Zero knowledge protocols
- H. Ong, Claus-Peter Schnorr, Adi Shamir, Efficient Signature Schemes Based on Polynomial Equations, proceedings of Crypto 1984, 37-46, 1985, [online]
- J. Pollard, An efficient
solution of the congruence
x2 + ky 2= m (mod n) , Letter to Adi Shamir [online] - Jeffrey Shallit, An exposition of Pollard's algorithm for quadratic congruences, technical report 84-006, University of Chicago, 1984 [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]
- S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, proceedings of STOC '85, 291--304, 1985 [online]
- Fiat, A. Shamir, How to
Prove Yourself: Practical Solutions to Identification and Signature
Problems, proceedings of Crypto '86, 186--194, 1986 [online]
- Vivien Dubois, Pierre-Alain Fouque, Adi Shamir, and Jacques Stern, Practical Cryptanalysis of SFLASH, to appear in Crypto '07 [online]
Oil and Vinegar, HFE
Special thanks to Eran Tromer for organizing most of the material on this page