Paper 2019/908

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

Benoît Libert, Khoa Nguyen, 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 {\it 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in Asiacrypt 2020
Keywords
LWEstandard modelNaor-YungKDM-CCA2 securityNIZK argumentssimulation-soundnesstight security
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

BibTeX

@misc{cryptoeprint:2019/908,
      author = {Benoît Libert and Khoa Nguyen and Alain Passelègue and Radu Titiu},
      title = {Simulation-Sound Arguments for LWE and Applications to KDM-CCA2 Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/908},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/908}},
      url = {https://eprint.iacr.org/2019/908}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.