分野別セミナー

In 2003 Alekhnovich (FOCS 2003) introduced a novel variant of the learning parity with noise problem and showed that it implies IND-CPA secure public-key cryptography. In this talk we show how to construct a public-key encryption-scheme based on this assumption which is IND-CCA secure in the standard model. Our main technical tool to achieve this is a novel all-but-one simulation technique based on the correlated products approach of Rosen and Segev (TCC 2009). The IND-CCA1 secure scheme presented is asymptotically optimal with respect to ciphertext-expansion. We will also discuss the transformation into an IND-CCA2 secure scheme using a technique of Dolev, Dwork and Naor (STOC 1991). We will further discuss possible perspectives of making LPN-based encryption-schemes more practical.