Description: (4 credits, 3 hours). In this course we study several topics of cryptography that have emerged recently. This year we will focus on "Zero-knowledge Interactive Proofs and two-party secure computations". Participants are expected to have a good background of cryptography (acquired through 308-547A or not).
Book in progress. Chap 2-4 are nearly final at this time. BOOK (pdf)
HW1 book problems 3.8, 3.10 and 3.11
BOOK (pdf)
DUE THURSDAY FEB 9th in class
HW2 book problems 4.2, 4.4, 4.11, and 3.8A
BOOK (pdf)
DUE TUESDAY FEB 28th in class
Topic 0: Number Theory Material (pdf)
Topic 0: Interactive Zero-Knowledge Proofs and other Two-Party Cryptographic Protocols
Topic 1: Interactive Proofs vs Arthur-Merlin Games
Topic 1: IP vs AM -- Useful Papers
Topic 2: Proofs of Knowledge -- blackboard presentations.
Topic 2: Proofs of Knowledge -- Useful Papers
Topic 3: Zero-Knowledge -- blackboard presentations.
Topic 4: Bit Commitment and BC with equality -- blackboard presentations.
Topic 4: BC and BC with equality -- Useful Papers
Topic 5: ZK power of BC -- blackboard presentations.
Topic 5: ZK power of BC -- Useful Papers
BELOW THIS LINE ******* NOT YET REVISED
Topic 6: Interactive Arguments = Computationally Sound IP -- blackboard presentations.
Topic 6: Arguments -- Useful Papers
Topic 7: BCs from one-way permutations -- blackboard presentations. mostly hand waving inspired by NOVY
Topic 7: BCs from one-way permutations (Nguyen, Ong and Vadhan) not covered with that level of details
Topic 7: BCs from one-way permutations -- Useful Papers
Topic 8: Computationally Concealing BCs from one-way functions -- blackboard presentations.
Topic 8: PRBG from one-way functions (Hastad, Impagliazzo, Levin, Luby) updated 23 Mar 2010 11h00
Topic 8: Computationally Concealing BCs from one-way functions -- Useful Papers
Topic 10: Introduction to Oblivious Transfer and two-party computations -- blackboard presentations.
Topic 11: One-out-of-two Oblivious Transfer based on the Quadratic Residuosity assumption -- blackboard presentations.
Topic 12: One-out-of-two Oblivious Transfer based on any (enhanced) Trapdoor One-Way permutation -- blackboard presentations.
Topic 13: On the power of One-out-of-two Oblivious Transfer (Honest but curious) -- blackboard presentations.
Topic 9: Computationally Binding BCs from one-way functions -- blackboard presentations.
Topic 9: Computationally Binding BCs from one-way functions -- (Haiftner and Reingold)
Topic 9: Computationally Binding BCs from one-way functions -- Useful Papers (Check paper HR06B.pdf)
Topic 14: Security definition of One-out-of-two Oblivious Transfer -- blackboard presentations.
Topic 15: Committed One-out-of-two Oblivious Transfer and application to two-party computations -- blackboard presentations.
Topic 16: Fairness in two-party computations -- blackboard presentations.
Useful books:
-
Oded Goldreich,
Foundations of Cryptography: Basic Tools.
Cambridge University Press.
-
Mike Luby,
Pseudorandomness and Cryptographic Applications
Princeton University Press, 1996.
-
Gilles Brassard,
Modern Cryptology
Springer-Verlag, lecture notes in Computer Science, Vol. 325, 1988.
Cryptologie Contemporaine
Masson, 1993.
-
Doug Stinson
Cryptography - Theory and Practice (third edition)
Taylor and Francis, Publisher.
Errata to 3rd Edition
-
Eric Bach and Jeffrey Shallit,
Algorithmic Number Theory, Volume I: Efficient Algorithms
MIT Press, 1996
-
Micheal Sipser,
Introduction to the Theory of Computation
PWS Publishing, 1997.
-
Gilles Brassard et Paul Bratley,
Fundamentals of Algorithmics
Prentice-Hall, 1996.
-
Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest,
Introduction to Algorithms
MIT Press, 1990.