COMS E6261: Advanced
Cryptography
Spring 2008: The Black-Box Complexity of Cryptographic Primitives
Lecture Topics
- Lecture 1: Introduction, what are black box constructions and
separations, overview of importance and applications. Semi-Honest
Oblivious transfer from eTDP. Approach to malicious OT from
Semi-Honest OT using zero knowledge (non-black-box).
- Lectre 2: Cryptographic Background: Secure Multi-Party
Computation.
- Lecture 3 readings:
Semi-Honest
to Malicious Oblivious Transfer - The Black-Box Way. I. Haitner. To
Appear in TCC 2008. (presented by Ariel).
Black-Box
Constructions for Secure Computation. Ishai, Kushilevitz, Lindell,
Petrank. STOC 06. (In particular, this shows a black-box
construction of malicious OT from homomorphic encryption and from
eTDP. This implies black-box secure computation from the same primitives)
Constant-Round Multiparty Computation Using a Black-Box
Psuedorandom Generator. Damgard Ishai. Crypto 2005.
(This is a black box construction of a weaker primitive - secure
computation with honest majority from a weaker primitive
(pseudorandom generator).
- Lecture 4 readings:
Construction of a Non-Malleable Encryption Scheme From Any Semantically Secure One. (Crypto 06)
R. Pass, A. Shelat and V. Vaikuntanathan.
(To be presented by Seung Geol.)
Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. (FOCS 99)
Amit Sahai.
Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions. (Journal of Cryptology 06)
Yehuda Lindell.
Relations among notions of non-malleability for encryption. (asiacrypt 2007)
R. Pass, A. Shelat and V. Vaikuntanathan.
- Lecture 5 readings:
Merkle Puzzles are Optimal
Mohammad Mahmoody-Ghidary and Boaz Barak.
Limits on the provable consequences of one-way permutations (STOC 89)
R. Impagliazzo and S. Rudich
Notions of Reducibility between Cryptographic Primitives.(TCC 04)
Omer Reingold, Luca Trevisan, and Salil Vadhan
- Lecture 6 (with special speaker Dana Dachman-Soled):
Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One(TCC 2008)
Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, Hoeteck Wee
- Lecture 7 (with guest speaker Chris Peikert):
Lossy Trapdoor Functions and Their Applications (STOC 2008)
Chris Peikert
- Lecture 8:
Please see the following note from Tal. The reading choices for next week is the first list.