Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / LWE, standard model, Naor-Yung, KDM-CCA security, NIZK proofs, simulation-soundness