You are looking at a specific version 20190808:064258 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.