Paper 2019/908
Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security
Benoît Libert and Khoa Nguyen and Alain Passelègue and Radu Titiu
Abstract
The Naor-Yung paradigm is a well-known technique that constructs IND-CCA2-secure encryption schemes by means of non-interactive zero-knowledge proofs satisfying a notion of simulation-soundness. Until recently, it was an open problem to instantiate it under the sole Learning-With-Errors (LWE) assumption without relying on random oracles. While the recent results of Canetti et al. (STOC'19) and Peikert-Shiehian (Crypto'19) provide a solution to this problem by applying the Fiat-Shamir transform in the standard model, the resulting constructions are extremely inefficient as they proceed via a reduction to an NP-complete problem. In this paper, we give a direct, non-generic method for instantiating Naor-Yung under the LWE assumption outside the random oracle model. Specifically, we give a direct construction of an unbounded simulation-sound NIZK argument system for the LWE relation. For a carefully chosen modulus, this relation makes it possible to express the equality of plaintexts encrypted under different keys in the dual Regev cryptosystem. As an application, we obtain an LWE-based public-key encryption scheme for which we can prove key-dependent message (KDM-CCA2) security under chosen-ciphertext attacks in the standard model.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- LWEstandard modelNaor-YungKDM-CCA securityNIZK proofssimulation-soundness
- Contact author(s)
- benoit libert @ ens-lyon fr,khoantt @ ntu edu sg,alain passelegue @ inria fr,radu titiu @ gmail com
- History
- 2021-05-25: last of 8 revisions
- 2019-08-08: received
- See all versions
- Short URL
- https://ia.cr/2019/908
- License
-
CC BY