Public Key Cryptography (Spring 2003) course
Instructor: Adi Shamir
Teaching assistant: Eran
Tromer
The link given in class is http://dl.tromer.org/PKC2003.
The password is as given there.
Resources
Most resources are available [online],
though some of the links can be accessed only from within the institute
firewall or here (ask me
for
the password).
For some papers there is a reserved [photocopy] at
the library - request it from the librarian.
General
- Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, Handbook of Applied Cryptography,
CRC Press, 1996 [online]
- Bruce Schneier, Applied
Cryptography, 2nd edition, John Wiley & Sons, 1996
Lecture 1: Genesis of public key cryptography
- W.Diffie and M.E.Hellman, New
directions in cryptography, IEEE Transactions on Information
Theory, IT-22, 6, pp.644-654, 1976, [online]
- R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures
and public-key cryptosystems, Communications
of the ACM, vol. 21(2), pp.120-126, 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 [photocopy]
- Adi Shamir, On the
cryptocomplexity of knapsack systems, proceedings of 11th ACM
symposium on Theory of Computing, ACM, 1979 [online]
Lecture 2: Knapsacks
- 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 [photocopy]
- 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
- E. F. Brickell, Breaking
Iterated Knapsacks, proceedings of Crypto '84, LNCS 196, pp.
342-358, Springer-Verlag, 1985 [online]
Lecture 3: Knapsacks (cont.), computational number theory
- David Wagner, A Generalized
Birthday Problem (extended abstract), proceedings of Crypto
2002,
LNCS 2442, pp. 288-304, Springer-Verlag, 2002, [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]
Lecture 4: Computational number theory (cont.)
- Manindra Agrawal, Nitin Saxena, Neeraj Kayal, PRIMES is in P (revised) [online]
- Web page concerning above, with links to clearer expositions and
further analysis: [online]
Lecture 5: Computational number theory (cont.)
- Solving polynomial equations modulo prime powers [online: ps pdf]
Lecture 6: Factoring, discerte logs
- 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)
Lecture 7: Sieve-based factoring algorithms
- Lecture slides [online: screen
print]
- 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]
- A.K. Lenstra, H.W. Lenstra, Jr., The
Development of the Number Field Sieve, Springer-Verlag, 1993
(anthology of papers on NFS) [available from
Eran]
- Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen,
Peter L. Montgomery, Brian Murphy, Herman te Riele, Karen Aardal, Jeff
Gilchrist, Gérard Guillerm, Paul Leyland, Jöel Merchand,
François Morain, Alec Muffett, Chris and Craig Putman, Pail
Zimmerman, Factorization of a 512-bit
RSA Modulus, proceedings of Eurocypt 2000 [online]
Lecture 8: More properties of RSA and discrete logs
- 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]
- Amos Fiat, Batch RSA,
proceedings of Crypto 1989, 175-185, 1989 [online]
Lecture 9: RSA and Rabin - efficiency, security, variants.
- Dan Boneh, Glenn Durfee, Cryptanalysis
of RSA with Private Key d Less than N0.292,
proceedings of Eurocrypt 1999, 1-11, 1999 [online]
- Adi Shamir, RSA for Paranoids,
RSA Laboratories' CryptoBytes, vol. 1(3), 1,3-4, 1995 [online]
- Adi Shamir, Memory Efficient
Variants of Public-Key Schemes for Smart Card Applications,
proceedings of Eurocrypt 1994, 445-449, 1994 [online]
- E. F. Brickell, J. M. DeLaurentis, An Attack on a Signature Scheme Proposed by
Okamoto and Shiraishi, proceedings of Crypto 1985, 28--, 1996 [online]
Lecture 10: Multivariate cryptographic schemes
- H. Ong, Claus-Peter Schnorr, Adi Shamir, Efficient Signature Schemes Based on
Polynomial Equations, proceedings of Crypto 1984, 37-46, 1985, [online]
- C. P. Schnorr, J. Pollard, An
efficient solution of the congruence x2 + ky2 = m
(mod n), IEEE Transactions on Information Theory, vol.
33(5), 702-709, 1987 [photocopy]
- 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]
Lecture 11: DSA, zero-knowledge proofs
- DSA and related signature schemes are discussed in pages 451-462
in Handbook of Applied Cryptography
[online]
- For an in-depth discussion of zero-knowledge proofs, see:
- Oded Goldreich, Foundations of Cryptography - Basic Tools,
Cambridge Unviersity Press, 2001
- Oded Goldreich, Foundations
of Cryptography (Fragments of a Book) [online]
(there is no need to use the full formalism in the homework exercise).
Lecture 11:
- S. Goldwasser, S. Micali, C. Rackoff, The Knowledge
Complexity of Interactive Proof Systems, proceedings of
STOC '85, 291--304, 1985
- A. Fiat, A. Shamir, How to
Prove Yourself: Practical Solutions to Identification and Signature
Problems, proceedings of Crypto '86, 186--194, 1986 [online]
- D. Pointcheval, J. Stern, Security
Proofs for Signature Schemes, proceedings of Eurocrypt '96,
387--398, 1996 [online]
Lecture 12: Lattices and their applications
- Lecture slides [online]
(2.3MB)
- D. Micciancio, S. Goldwasser, Complexity of
Lattice Problems: A
Cryptographic Perspective, Kluwer, 2002 [available from
Eran]
- D. Micciancio, Lattices
in Cryptography and Cryptanalysis, course lecture notes, 1999 [online]
- Frieze, On the Lagarias-Odlyzko
algorithm for the subset sum problem, SIAM Journal on computing,
15(2):536-539, 1986 [photocopy]
- M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C.P.
Schnorr, J. Stern, Improved
Low-Density Subset Sum Algorithms, proceedings of Eurocrypt 1991,
54--67, 1991 [online]
- C. P. Shnorr, Factoring Integers and Computing Discrete
Logarithms via Diophantine Approximation, proceedings of Eurocrypt '91,
171--181, 1991 [online]
Lecture 13: Lattice-based cryptosystems
- Lecture slides [online]
(470KB)
- J. Hoffstein, J. Pipher, J. H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem,
proceedings of ANTS III, 267--288, 1998 [online]
- D. Coppersmith, A. Shamir, Lattice attacks on NTRU,
proceedings
of EUROCRYPT 97, 52--61, 1997 [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]
- O. Goldreich, S. Goldwasser and S. Halevi, Public-Key Cryptosystems from Lattice
Problems, proceedings of CRYPTO'97, 112-131, 1997 [online]
- M. Ajtai, C. Dwork, A Public-Key Cryptosystem with
Worst-Case/Average-Case Equivalence,
proceedings of STOC 1997 [online]
Lecture 14: Special signature constructions
- 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]