Instructor: Poorvi Vora

Text: None. See this website for references.

Schedule: Wed., 7:10 - 9:40 pm, Rome 201.

Course Content: Elliptic Curve Cryptography. Provably secure PRNGS. Zero-knowledge proofs. Cryptanalysis. Voting.

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

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

Course Outline

Planned Schedule

6 September 2007
Lecture 1: Cryptography over groups: review algebra, Diffie-Hellman, El Gamal, efficient exponentiation over groups, digital signatures.
HW 1 assigned.
References
Wenbo Mao, Modern Cryptography, pp. 139-152.
Blake et al, Elliptic Curves in Cryptography, pp. 1-10

13 September 2007
Lecture 2: Elliptic Curve Cryptography: elliptic curve algebra
References
Wenbo Mao, Modern Cryptography, pp. 166-173.
Neal Koblitz, A Course in Number Theory and Cryptography. pp. 179-182.
Neal Koblitz, Algebraic Aspects of Cryptography. pp. 132-133, 134-136.
Certicom Tutorial
George Barwood FAQ
FIPS 186-2 Digital Signature Standard (DSS)

20 September 2007
Lecture 3: Information theory of secrecy: perfect secrecy, unicity distance. Computational theory of secrecy for PRGs: definitions
HW 2 assigned.
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", Third Edition, 2006.
3. Goldwasser and Bellare, Lecture Notes on Crypto, section 3.1.

27 September 2007
Lecture 4: Existence of PRNGs.
References
1. Goldwasser and Bellare, Lecture Notes on Crypto, section 3.2
2. A. C. Yao. Theory and Applications of Trapdoor Functions. Proceedings of the 23rd FOCS, IEEE, 1982, pp. 80-91. FIX
3. Yehuda Lindell's lecture notes on hard-core predicates
Student Presentation On: Shamir Secret Sharing. Reference for Presentation Adi Shamir, How to Share a Secret, CACM, 22:11 1979. Also see: Doug Stinson, "Cryptography: Theory and Practice", Third Edition, 2006, pp. 481-486

4 October 2007
Lecture 5: Next-bit Tests.
References
1. Goldwasser and Bellare, Lecture Notes on Crypto, section 3.3
2. A. C. Yao. Theory and Applications of Trapdoor Functions. Proceedings of the 23rd FOCS, IEEE, 1982, pp. 80-91. FIX
Student Presentation On: Computational Secret Sharing. Reference for Presentation: Hugo Krawczyk. Secret sharing made short. In Advances in Cryptology: Proceedings of Crypto '93, pages 136-143. Springer-Verlag, 1993

11 October 2007
Lecture 6: Zero-knowledge Proofs and Bit Commitments.
HW 3 assigned.
References
1. Goldwasser and Bellare, Lecture Notes on Crypto, sections 11.1.3, 11.2
2. Oded Goldreich. Zero knowledge Twenty Years after its Invention. Part I.
3. Gaurav Jain. Zero Knowledge Proof Systems - A Survey

18 October 2007
Lecture 7: Student Presentations On: Anonymity Primitives and Audit.
References for Presentation:
1. Moni Naor and Adi Shamir, Visual Cryptography. Eurocrypt 94. Simple explanation by Stinson.
2. David Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, CACM, 24:2 1981.
3. Jakobsson, Juels and Rivest, Making Mix Nets Robust For Electronic Voting By Randomized Partial Checking, USENIX 2002.
4. David Chaum, The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, JoC, 1:1 1988.
5. Michael K. Reiter and Aviel D. Rubin, Crowds: Anonymity for Web transactions, TISSEC, 1:1 1998.

25 October 2007
Lecture 8: Student Presentations On: Voting, Anonymity and Group Signatures
References for Presentation:
1.Claudia Diaz, Stefaan Seys, Joris Claessens, and Bart Preneel, Towards measuring anonymity, PET 2002, LNCS 2482.
2. David Chaum, Blind signatures for untraceable payments, Crypto'82 pp. 199-203.
3. Benaloh, J. Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret. CRYPTO `86. LNCS vol. 263, pp. 251--260.
4. G. Ateniese and G. Tsudik. Group Signatures a la carte. ACM SODA 99.

1 November 2007
Lecture 9: Student Presentations On: End-to-end voting.
References for Presentation:
1. 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. Also, Chaum, van de Graaf, Ryan and Vora, Secret Ballot Elections with Unconditional Integrity.
2. David Chaum, Peter Y. A. Ryan, S. A. Schneider. A Practical, Voter-verifiable Election Scheme. CS-TR: 880. School of Computing Science, Newcastle University, Dec 2004
3. Ben Hosp and Stefan Popoveniuc. An Introduction to Punchscan.
4. Ronald L. Rivest and Warren D. Smith. ThreeVotingProtocols: ThreeBallot, VAV, and Twin. EVT'07

8 November 2007
Lecture 10: Student Presentations On: Statistical Cryptanalysis and Audio Cryptography + catch-up.
References for Presentation:
1. Roberto Araújo, Ricardo Felipe Custódio, Jeroen van de Graaf. A Verifiable Voting Protocol based on Farnel. WOTE '07.
2. Yvo Desmedt, Shuang Hou, Jean-Jacques Quisquater. Audio and Optical Cryptography. Asiacrypt 98
3. Thomas Jakobsen. Cryptanalysis of Block Ciphers with Probabilistic Non-Linear Relations of Low Degree. Crypto'98
4. Lars Knudsen and David Wagner. Integral Cryptanalysis (Extended abstract). FSE 2002.

15 November 2007
Lecture 11: Catch-Up
References:
1. Joshua Mason, Kathryn Watkins, Jason Eisner, and Adam Stubblefield. A Natural-Language Approach to Automated Cryptanalysis of Two-Time Pads. CCS 2006.
2. Eric Filiol. Plaintext-dependent Repetition Codes Cryptanalysis of Block Ciphers - The AES Case. IACR eprint archive, 8th January 2003.
3. Darakhshan J. Mir and Poorvi L. Vora. Related-Key Statistical Cryptanalysis. In review. Also available as Report 2007/227 in the cryptology eprint archive.
4. N. Papanikolaou. An Introduction to Quantum Cryptography. ACM Crossroads Magazine, Issue 11.3 (Spring 2005).

22 November 2005
No lecture. Thanksgiving.

29 November 2005
Lecture 12: Student Presentations On: SHA-1
References for Presentation:
1. Shai Halevi, Hugo Krawczyk. Strengthening Digital Signatures via Randomized Hashing. NIST Cryptographic Hash Workshop, October 2005.
2. Shai Halevi, Hugo Krawczyk. Update on Randomized Hashing. Second Cryptographic Hash Workshop, August 2006.
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.
5. William Stallings. The Whirlpool Secure Hash Function. Cryptologia, 30:55–67, 2006

6 December 2007
Lecture 13: TBD
1. David Wagner. Towards a unifying view of block cipher cryptanalysis. Fast Software Encryption 2004, invited paper, February 7, 2004.