Paper 2019/908
Simulation-Sound Proofs 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 proof system for the LWE relation. In turn, 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