Paper 2023/1728
Simulation-Secure Threshold PKE from LWE with Polynomial Modulus
Abstract
In LWE based cryptosystems, using small (polynomially large) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs "simulation security": the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Rényi divergence based analyses that are sufficient for game-based but not simulation security. In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially large modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Contact author(s)
-
daniele @ cs ucsd edu
asuhl @ ucsd edu - History
- 2023-11-13: approved
- 2023-11-08: received
- See all versions
- Short URL
- https://ia.cr/2023/1728
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1728,
author = {Daniele Micciancio and Adam Suhl},
title = {Simulation-Secure Threshold PKE from LWE with Polynomial Modulus},
howpublished = {Cryptology ePrint Archive, Paper 2023/1728},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1728}},
url = {https://eprint.iacr.org/2023/1728}
}
