FOCS ’09 crypto accepts

The FOCS 2009 accepted papers are posted, with abstracts. See the chair’s comments here, and other topic-specific discussions here, here and here. Despite some excellent submissions not making it in, there are still some (few!) crypto papers, all of which look interesting. In no particular order: 

• Steven Myers and abhi shelat. One bit encryption is complete
• Yi Deng, Vipul Goyal and Amit Sahai. Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. Extracting Correlations
• Yael Tauman Kalai, Xin Li and Anup Rao. 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness

Quantum crypto papers:

• Anne Broadbent, Joseph Fitzsimons and Elham Kashefi. Universal Blind Quantum Computation
• André Chailloux and Iordanis Kerenidis. Optimal quantum strong coin flipping

Not exactly crypto, but highly relevant:

• Iftach Haitner. A Parallel Repetition Theorem for Any Interactive Argument
• Falk Unger. A Probabilistic Inequality with Applications to Threshold Direct Product Theorems

Scanning over the FOCS abstracts is hard because of information overload. I will try to read all of the papers on the list above (maybe I’ll even attend the conference) but for now two stand out because they resolve problems I have thought about:

First, Steve and abhi’s surprising paper (not yet available online), which gives a black-box construction of many-bit CCA-secure encryption from 1-bit CCA-secure encryption. This question is tied to very basic notions of authenticity and secrecy in cryptography. For CPA-secure encryption (that is, encryption secure against passive attacks), increasing the message length is straightforward: Goldwasser and Micali showed that encrypting each bit separately works (a classic example of a “hybrid” argument). However, for schemes that must resist active attacks, such as chosen-ciphertext attacks (CCA), bit-by-bit encryption fails miserably. Prior to this paper, there existed (limited) impossibility results, but no evidence that a black-box construction was possible.

Second, André and Iordanis’ paper on optimal strong quantum coin flipping. Information-theoretically secure quantum coin flipping was proved to be impossible in the late 90’s by Mayers and Lo and Chau, using the same techniques that rule out information-theoretically secure oblivious transfer and bit commitment. That result only rules out protocols that produce a very good biased coin (with bias 1/2+o(1)). However, protocols were constantly being proposed (and occasionally broken) which  produced weakly biased coins. This new paper gives a protocol matching Kitaev’s lower bound of on the minimal bias. This is not of critical importance in practice, but it does elucidate one of the key phenomena which distinguish quantum from classical cryptographic protocols.