zbMATH — the first resource for mathematics

IND-CCA secure cryptography based on a variant of the LPN problem. (English) Zbl 1292.94056
Wang, Xiaoyun (ed.) et al., Advances in cryptology – ASIACRYPT 2012. 18th international conference on the theory and application of cryptology and information security, Beijing, China, December 2–6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-34960-7/pbk). Lecture Notes in Computer Science 7658, 485-503 (2012).
Summary: 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 A. Rosen and G. Segev [TCC 2009, Lect. Notes Comput. Sci. 5444, 419–436 (2009; Zbl 1213.94130)]. 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.
For the entire collection see [Zbl 1258.94006].

94A60 Cryptography
Full Text: DOI