# 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.