Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security - Archive ouverte HAL Access content directly
Conference Papers Year :

Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security

(1, 2, 3) , (4) , (2, 3) , (5, 2, 3)


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 which, for carefully chosen parameters, makes it possible to express the equality of plaintexts encrypted under different keys in Regev's cryptosystem. We also give a variant of our argument that provides tight security. As an application, we obtain an LWE-based public-key encryption scheme for which we can prove (tight) key-dependent message security under chosen-ciphertext attacks in the standard model.
Fichier principal
Vignette du fichier
kdm-NIZK.pdf (1.03 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02993617 , version 1 (06-11-2020)


  • HAL Id : hal-02993617 , version 1


Benoît Libert, Khoa Nguyen, Alain Passelègue, Radu Titiu. Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security. Asiacrypt 2020 - 26th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2020, Virtual, South Korea. pp.1-67. ⟨hal-02993617⟩
45 View
234 Download


Gmail Facebook Twitter LinkedIn More