[Resource Topic] 2023/1728: Simulation-Secure Threshold PKE from LWE with Polynomial Modulus

Welcome to the resource topic for 2023/1728

Simulation-Secure Threshold PKE from LWE with Polynomial Modulus

Authors: Daniele Micciancio, Adam Suhl


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.

ePrint: https://eprint.iacr.org/2023/1728

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .