Topics in Cryptography Shafi Goldwasser and Moni Naor

Topics in Cryptography - Spring 2009

Instructors: Shafi Goldwasser and Moni Naor

Grader: Gil Segev

When: Tuesdays 16:00--18:00 Note: first meeting March 24th
Where: Ziskind 1
First meeting: March 24th

DESCRIPTION:

In recent years, we are witnessing a surge of new cryptographic ideas applied to old cryptographic problems such as security against chosen cipher text attack, protection against side channel attacks, and software protection. In addition we see the emergence of new areas of investigation such as game theory and cryptography. In this course we aim to cover these recent developments. Topics covered will include:

Program Obfuscation

Theory of protection against side channel attacks and key leakage.
Game Theory and Cryptography
New methods for obtaining schemes secure against chosen ciphertext attacks
Homomorphic encryption and applications

PREREQUISITES: Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level and to have taken a previous course in cryptography.

REQUIREMENTS: Students are expected to read papers, prepare homework.

Handouts and Homework

Lecture 1 (March 24th) - on Obfuscation: Notes on Obfuscation: Definition and first Impossibility, Scribe Notes for Lecture 1
Lecture 2 (March 31st) - on Obfuscation: Scribe Notes for Lecture 2
Lecture 4 (April 21st)- on Chosen Ciphertext Attacks Slides for Lecture 4
Lecture 5 (May 5th)- Achieving Chosen Ciphertext security Slides for Lecture 5
Lecture 6 (May 19)- Achieving Chosen Ciphertext security - Correlated Products and IBE. Deniable Ring Authentication Slides for Lecture 6
Lecture 7 (May 26)- side channels Slides for Lecture 7
Lecture 8 (June 2)- side channels Slides for Lecture 8
Lecture 9-10 (June 9, 16)- lattice based crypto Slides for Lecture 9 and 10

Bibliography

Obfuscation
- Boaz Barak, Can We Obfuscate Programs? (General explanation of the meaning of the results)
- B. Barak, O. Goldreich R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan and K. Yang, On the (Im)possibility of Obfuscating Programs, CRYPTO 2001
- Ran Canetti, Towards realizing random oracles: Hash functions that hide all partial information, Crypto 1997
- Shafi Goldwasser and Yael Tauman Kalai, On the Impossibility of Obfuscation with Auxiliary Inputs, FOCS 2005.
- Susan Hohenberger, Guy Rothblum, Abhi Shelat and Vinod Vaikuntanathan, Securely Obfuscating Re-Encryption. TCC 2007
- Shafi Goldwasser, Yael Tauman Kalai and Guy Rothblum, One-Time Programs

Chosen Ciphertext Protection
- Yehuda Lindell, A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions .
- Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack .
- Ronald Cramer and Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption , Eurocrypt 2002.
- D. Boneh, R. Canetti, S. Halevi, and J. Katz, Chosen-Ciphertext Security from Identity-Based Encryption.

Dennis Hofheinz and Eike Kiltz. Practical Chosen Ciphertext Secure Encryption from Factoring , Eurocrypt 2009.
Eike Kiltz and Krzysztof Pietrzak and Martijn Stam and Moti Yung, A New Randomness Extraction Paradigm for Hybrid Encryption. Eurocrypt 2009.
Chris Peikert and Brent Waters, Lossy Trapdoor Functions and Their Applications , STOC 2008.
Alon Rosen and Gil Segev, Chosen Ciphertext Security via Correlated Products , TCC 2009.
Moni Naor, Deniable Ring Authentication, Crypto 2002.

Combatting Side Channels and key leakage:
Attacks:

Paul Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems , Crypto 1996.

Dan Boneh and David Brumley, Remote timing attacks are practical, USENIX 2003. slides

Paul Kocher, Joshua Jaffe and Benjamin Jun, Differential Power Analysis , Crypto 1999.

Dan Boneh, Richard DeMillo, and Richard Lipton, On the importance of checking cryptographic protocols for faults. Journal of Cryptology, 2001, pp. 101-119, 2001.

Dag Arne Osvik, Adi Shamir, Eran Tromer, Cache attacks and countermeasures: the case of AES, Proc. CT-RSA 2006. slides

J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten, Lest We Remember: Cold Boot Attacks on Encryption Keys, Usenix Security 2008.

website

Protection:

Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai, Exposure-Resilient Functions and All-or-Nothing Transforms . Eurocrypt 2000.
Silvio Micali and Leonid Reyzin, Physically Observable Cryptography, Theory of Cryptography Conference, TCC 2004.
Yuval Ishai, Amit Sahai, David Wagner: Private Circuits: Securing Hardware against Probing Attacks. CRYPTO 2003: 463-481
Yuval Ishai, Manoj Prabhakaran, Amit Sahai and David Wagner: Private Circuits II: Keeping Secrets in Tamperable Circuits. EUROCRYPT 2006.
R. Canetti, D. Eiger, S. Goldwasser, D. Y. Lim, How to Protect Yourself without Perfect Shredding, ICALP 2008.
Oded Goldreich and Rafi Ostrovsky, Software Protection and Simulation on Oblivious RAMs, Journal of the ACM 1996.
Stefan Dziembowski and Krzysztof Pietrzak, Leakage-Resilient Cryptography , FOCS 2008.
Krzysztof Pietrzak, A Leakage-Resilient Mode of Operation, Eurocrypt 2009.
Adi Akavia, Shafi Goldwasser and Vinod Vaikuntanathan, Simultaneous Hardcore Bits and Cryptography Against Memory Attacks, TCC 2009
Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett, On Cryptography with Auxiliary Input, STOC 2009.
Moni Naor and Gil Segev, Public-Key Cryptosystems Resilient to Key Leakage, Crypto 2009.
Jonathan Katz Signature Schemes with Bounded Leakage Resilience

Lattice Based Cryptography

Daniele Micciancio Oded Regev, Lattice-based Cryptography (A Survey)

Homomorphic Encryption

Craig Gentry, On Homomorphic Encryption over Circuits of Arbitrary Depth, STOC 2009.
Dan Boneh, E. Goh, and Kobbi Nissim, Evaluating 2-DNF Formulas on Ciphertexts , TCC 2005.

Game Theory and Cryptography:

Jonathan Katz, Bridging Cryptography and Game Theory: Recent Results and Future Directions, 5th Theory of Cryptography Conference (TCC 2008).
Rational Cryptographic Protocols, Ecrypt Report, Revision 1.0, March 2007.
Yevgeniy Dodis and Tal Rabin, Cryptography and Game Theory, in Algorithmic Game Theory.
Joe Halpern and Rafael Pass, Game Theory with Costly Computation