Oddly Shaped Pegs

An inquiry into the Nature and Causes of Stuff

FOCS ’09 crypto accepts

leave a comment »

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:

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 1/\sqrt{2}\approx 0.707 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.


Written by adamdsmith

July 2, 2009 at 9:33 pm

Posted in Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: