- 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.

If none of the above are given and you obtain the paper by other means, please e-mail a copy to the TA or put one in the course mailbox, so the TA will prepare additional copies for the library.

- 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]

- 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]

- 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])

- 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.

- Resources on computational number theory are listed above.

- 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.

- 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]

- 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 ^{2}+ ky^{2}= 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

- 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]**