Title: Limitations of Public Key Encryption from Noisy Codewords
Speaker: Noga Ron-Zewi, IAS
Date: Wednesday, November 12, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Several well-studied public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting a noisy linear encoding. These schemes are limited in that they either require the underlying field to grow polynomially with the security parameter, or alternatively they can work over the binary field but have a low noise entropy that gives rise to sub-exponential attacks. Motivated by the goal of achieving efficient public key cryptography, we study the possibility of obtaining improved security over the binary field by using different noise distributions.
For this, we first propose a unified framework that captures all three encryption schemes mentioned above and allows for arbitrary choices of the underlying field and noise distributions.
We then show, using a simple argument that relies on agnostic learning of parities (Kalai, Mansour and Verbin, STOC 2008), that any instance of the unified framework over the binary field can be attacked in time exp(n/log(n)) where n is the ciphertext size. Combining this attack with Regev's security proof (STOC 2005) we obtain an algorithm that solves the learning parity with noise (LPN) problem in time exp(n/loglog(n)) using only n^{1+\epsilon} samples, reproducing the result of Lyubashevsky (Random 2005) and Kopparty and Saraf (STOC 2010) in a conceptually different way.
Our main result shows a new connection between additive combinatorics and public key encryption by showing that the ``approximate duality conjecture" from additive combinatorics (Ben-Sasson and R., STOC 2011) improves the running time of the above attack to exp(sqrt(n)) where n is the maximum of the ciphertext size and the public key size. On the positive side, counter examples to the above conjecture may lead to candidate distributions over the binary field with improved security guarantees.
Joint work with Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgard and Yuval Ishai.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/