Paper 2023/1728

Simulation-Secure Threshold PKE from LWE with Polynomial Modulus

Daniele Micciancio, University of California, San Diego
Adam Suhl, University of California, San Diego

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.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
daniele @ cs ucsd edu
asuhl @ ucsd edu
2023-11-13: approved
2023-11-08: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.