Paper Info
Title
IND-CCA secure cryptography based on a variant of the LPN problem
Abstract
In 2003 Michael 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 paper we introduce the first 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). Our IND-CCA1 secure scheme is asymptotically optimal with respect to ciphertext-expansion. To achieve IND-CCA2 security we use a technique of Dolev, Dwork and Naor (STOC 1991) based on one-time-signatures. For practical purposes, the efficiency of the IND-CCA2 scheme can be substantially improved by the use of additional assumptions to allow for more efficient signature schemes. Our results make Alekhnovich's variant of the learning parity with noise problem a promising candidate to achieve post quantum cryptography.
Year
DOI
Venue
2012
10.1007/978-3-642-34961-4_30
ASIACRYPT
Keywords
Field
DocType
lpn problem,public-key cryptography,novel all-but-one simulation technique,michael alekhnovich,noise problem,ind-cca secure cryptography,ind-cca2 scheme,ind-cca1 secure scheme,post quantum cryptography,ind-cca2 security,efficient signature scheme,novel variant
Post-quantum cryptography,Computer science,Cryptography,Theoretical computer science,Asymptotically optimal algorithm
Conference
Citations 
PageRank 
References 
10
0.48
30
Authors
3
Name
Order
Citations
PageRank
Nico Döttling116412.96
Jörn Müller-Quade236138.34
Anderson C. A. Nascimento326629.84