Instructor: Poorvi Vora

Text: None. See this website for references.

Schedule: Wed., 7:10 - 9:40 pm, Philips 108.

Course Content: Elliptic Curve Cryptography. Computational theory of secrecy. Secret sharing. Zero-knowledge proofs. Cryptanalysis. Voting.

Grading: Class participation, 3 HWs, paper presentations and evaluations, and a final project paper.

Prerequisites: both CS 284 (intro graduate crypto) and CS 212 (graduate algorithms) or exposure to algebra and mathematical proofs.

Course Outline

Planned Schedule

31 August 2005
Lecture 1: Elliptic Curve Algebra. HW 1
References
Wenbo Mao, Modern Cryptography, pp. 139-152 and 166-173.
Certicom Tutorial
George Barwood FAQ
http://world.std.com/~dpj/elliptic.html (Link currently broken)

7 September 2005
Lecture 2: Elliptic Curve Cryptography. Digital Signatures Efficient Exponentiation
References
Wenbo Mao, Modern Cryptography, pp. 171.
Neal Koblitz, A Course in Number Theory and Cryptography. pp. 179-182.
Neal Koblitz, Algebraic Aspects of Cryptography. pp. 132-133, 134-136.
FIPS 186-2 Digital Signature Standard (DSS)

14 September 2005
Lecture 3: (Information) Theory of Secrecy. Entropy, Perfect Secrecy. Information Theory of Secrecy
References
1. Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, vol.28-4, page 656--715, 1949.
2. Doug Stinson, Chapter 2, "Cryptography: Theory and Practice", Second Edition, 2002.

21 September 2005
Lecture 4: Entropy and Unicity Distance. HW 2.
References
1. Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, vol.28-4, page 656--715, 1949.
2. Doug Stinson, Chapter 2, "Cryptography: Theory and Practice", Second Edition, 2002.

28 September 2005
Lecture 5: Unicity Distance. (Computational) Theory of Secrecy: Definitions.
References
1. Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, vol.28-4, page 656--715, 1949.
2. Doug Stinson, Chapter 2, "Cryptography: Theory and Practice", Second Edition, 2002.
3. Goldwasser and Bellare, Lecture Notes on Crypto, sections 3.1-3.3.
Student Presentation On: Shamir Secret Sharing. Slides for Presentation
Reference for Presentation
1. Adi Shamir, How to Share a Secret, CACM, 22:11 1979.

5 October 2005
Lecture 6: Hard-core predicates. Existence of PRNGs.
References
1. Goldwasser and Bellare, Lecture Notes on Crypto, sections 3.1-3.3
2. A. C. Yao. Theory and Applications of Trapdoor Functions. Proceedings of the 23rd FOCS, IEEE, 1982, 80–91.
3. Yehuda Lindell's lecture notes on hard-core predicates
Student Presentation On: Computational Secret Sharing.
Reference for Presentation
1. Hugo Krawczyk. Secret sharing made short. In Advances in Cryptology: Proceedings of Crypto '93, pages 136-143. Springer-Verlag, 1993

12 October 2005
Lecture 7: Next-bit Prediction and Security against Statistical Attacks. Bit Prediction.
References
Goldwasser and Bellare, Lecture Notes on Crypto, sections 3.1-3.3, 11.1
Student Presentation On: Visual Cryptography. Slides for presentation.
Reference for Presentation
1. Moni Naor and Adi Shamir, Visual Cryptography. Eurocrypt 94. Simple explanation by Stinson.

19 October 2005
Lecture 8: Student Presentations On: Anonymity Primitives, Measurement and Audit. Chaum MIX, Juels-Rivest Randomized Partial Checking of MIXes, Crowds. Dining Cryptographers, Anonymity Set. Serjantov-Diaz Info-theoretic Anonymity. Chaum Blind Signature. Measures. Visual Crypto.
References for Presentation:
1. David Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, CACM, 24:2 1981.
2. Jakobsson, Juels and Rivest, Making Mix Nets Robust For Electronic Voting By Randomized Partial Checking, USENIX 2002.
3. David Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, JoC, 1:1 1988.
4. Michael K. Reiter and Aviel D. Rubin, Crowds: Anonymity for Web transactions, TISSEC, 1:1 1998.
5. Andrei Serjantov and George Danezis, Towards an Information Theoretic Metric for Anonymity, PET 2002, LNCS 2482.
6. (Not presented) Claudia Diaz, Stefaan Seys, Joris Claessens, and Bart Preneel, Towards measuring anonymity, PET 2002, LNCS 2482.
7. David Chaum, Blind signatures for untraceable payments, Crypto'82 pp. 199-203.

26 October 2005
Lecture 9: Student Presentations On: Homomorphic Encryption and Voting. Benaloh. Chaum Receipt Voting.
References for Presentation: Broken Links fixed, Oct. 20
1. (Presented on 2 November) Cohen, J. and Fischer, M. A Robust and Verifiable Cryptographically Secure Election Scheme. FOCS 1985. pp. 372--382.
2. (Not presented) Benaloh, J. and Yung, M. Distributing the Power of a Government to Enhance the Privacy of Voters. PoDC 1986. pp. 52--62.
3. Benaloh, J. Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret. CRYPTO `86. LNCS vol. 263, pp. 251--260.
4. Benaloh, J. and Tuinstra, D. Receipt-Free Secret-Ballot Elections. STOC 1994. pp. 544--553.
5. David Chaum. Secret-Ballot Receipts: True Voter-Verifiable Elections. IEEE Security and Privacy, vol. 2, no. 1, pp. 38-47. An explanation, by Poorvi Vora.
References not for Presentation:
6. Zuzana Rjaskova. Electronic Voting Schemes. MSc thesis, 2003
7. Warren D. Smith. Cryptography meets voting

2 November 2005
Lecture 10: Student Presentations On: Homomorphic Encryption and Electronic Cash: antidouble spending, off-line.
References for Presentation:
1. Cohen, J. and Fischer, M. A Robust and Verifiable Cryptographically Secure Election Scheme. FOCS 1985. pp. 372--382.
2. Benaloh, J. and Tuinstra, D. Receipt-Free Secret-Ballot Elections. STOC 1994. pp. 544--553.
3. David Chaum, Amos Fiat and Moni Naor. Untraceable Electronic Cash. Crypto 1988
4. (To be presented on 9 November) Markus Jakobsson, Moti Yung. Revokable and Versatile Electronic Money. ACM CCS 1996.
5. (Not presented) Markus Jakobsson. Electronic payments: where do we go from here?. Invited talk, CQRE '99. No presentation, only discussion.

9 November 2005
Lecture 11: Instructor Lecture on Coding Theory and Statistical Models. Student Presentations On: Electronic Cash and Statistical Cryptanalysis. Wagner Block Cipher Model. Filiol Channel Model.
References for Student Presentations:
1. Markus Jakobsson, Moti Yung. Revokable and Versatile Electronic Money. ACM CCS 1996.
2. Sylvio Micali and Ronald L. Rivest. Micropayments Revisited. Proceedings of the Cryptographer's Track at the RSA Conference 2002, Bart Preneel (ed.), Springer Verlag CT-RSA 2002, LNCS 2271, pages 149--163. Rivest's slides are on his website. This is the basis of the Peppercoin Micropayment System, www.peppercoin.com.
3. Eric Filiol. Plaintext-dependent Repetition Codes Cryptanalysis of Block Ciphers - The AES Case. IACR eprint archive, 8th January 2003.

16 November 2005
Lecture 12: Student Presentations On: Statistical Cryptanalysis. SHA-1 Attacks.
References for Presentation:
1. V. Chepyshov, T. Johansson, B. Smeets. A simple algorithm for fast correlation attacks on stream ciphers. LNCS, (FSE'2000).
2. David Wagner. Towards a unifying view of block cipher cryptanalysis. Fast Software Encryption 2004, invited paper, February 7, 2004.
3. John Kelsey and Tadoyoshi Kohno. Herding Hash Functions and the Nostradamus Attack. NIST Cryptographic Hash Workshop, October 2005.
4. Steven Bellovin and Eric Rescorla. Deploying a New Hash Algorithm.

23 November 2005
No lecture. Thanksgiving.

30 November 2005
Lecture 13: Zero-Knowledge.
Student Presentations On: SHA-1 Attacks.
References for Presentation:
1. Shai Halevi, Hugo Krawczyk. Strengthening Digital Signatures via Randomized Hashing. NIST Cryptographic Hash Workshop, October 2005.
2. Norbert Pramstaller, Christian Rechberger, Vincent Rijmen. Impact of Rotations on SHA-1 and Related Hash Functions..