Foundations of Cryptography

CS60088, Spring 2018, LTP: 3-1-0

Syllabus (Tentative)

• Introduction to Cryptography
• Perfect secrecy -- definition, equivalent definitions, one-time pads, limitations of perfect secrecy, Shannon's theorem
• Computational secrecy -- motivating the need for computational secrecy, formalising security under different threat models, reductionist arguments and hardness assumptions
• Symmetric Encryption from psedorandom generators, pseudorandom functions and permutations
• Introduction to one-way functions, constructing one-way functions from assumptions such as RSA, Discrete logarithm, hard-core predicates, construction of pseudorandom objects from one-way functions
• Message authentication codes (MACs), hash functions and their security definitions, provably secure constructions
• Practical Constructions of symmetric encryption, MACs and hash functions
• Public key encryption
• Digital signatures
• Protocols

References

• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, Chapman and Hall/CRC Press, 2007.
• Shafi Goldwasser and Mihir Bellare, Lecture Notes on Cryptography, 2008 (available here).
• Oded Goldreich, The Foundations of Cryptography, Volume 1 and Volume 2, Cambridge University Press, 2001 and 2004.
• Wenbo Mao, Modern Cryptography: Theory and Practice, first edition, Pearson Education, 2004.

Evaluation

Tests/Exams

Presentation

• effectively summarising main contributions of the paper (and related works),
• depth of understanding,
• clarity of presentation,
• relevance of the paper to the course, and
• insights/criticisms/comments of your own, if any.

1. Werner Alexi, Benny Chor, Oded Goldreich, Claus P. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM Journal on Computing, Vol. 17, Iss. 2.
2. Manuel Blum, Silvio Micali. How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. SIAM Journal on Computing, Vol. 13, Iss. 4.
3. Mihir Bellare and Philip Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. First Conf. on Computer and Communications Security, pp. 62 73, 1993
4. M. Naor and M. Yung, "Public-key cryptosystems provably secure against chosen ciphertext attacks", in 22nd ACM Symposium on the Theory of Computing, pp. 427-437, 1990.
5. M Luby, C Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 1988 - SIAM
6. D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 1997 - Springer
7. Chris Peikert and Alon Rosen. "Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices." Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2006.
8. Dan Boneh and Matt Franklin. "Identity-based encryption from the Weil pairing." Annual international cryptology conference. Springer, Berlin, Heidelberg, 2001.
9. David Pointcheval and Jacques Stern. "Security proofs for signature schemes." International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1996.
10. Mihir Bellare and Oded Goldreich. "On defining proofs of knowledge." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992.
11. Moni Naor and Omer Reingold. "Number-theoretic constructions of efficient pseudo-random functions." Journal of the ACM (JACM) 51.2 (2004): 231-262.
12. Danny Dolev, Cynthia Dwork and Moni Naor. "Nonmalleable cryptography." SIAM review 45.4 (2003): 727-784.
13. Antoine Joux. "Multicollisions in iterated hash functions. Application to cascaded constructions." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2004.
14. K. Kurosawa and Y. Desmedt. A new paradigm of hybrid encryption scheme. In CRYPTO 2004, LNCS 3152, pages 426--442. Springer-Verlag, 2004.
15. David Cash, Eike Kiltz, and Victor Shoup. "The twin Diffie-Hellman problem and applications." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2008.
16. Dan Boneh, Ben Lynn and Hovav Shacham. "Short signatures from the Weil pairing." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2001.
17. Eiichiro Fujisaki and Tatsuaki Okamoto. "Secure integration of asymmetric and symmetric encryption schemes." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1999.

Tutorials