Paper 2024/239

Simulation-Secure Threshold PKE from Standard (Ring-)LWE

Hiroki Okada, KDDI Research (Japan), University of Tokyo
Tsuyoshi Takagi, University of Tokyo

Threshold public key encryption (ThPKE) is PKE that can be decrypted by collecting “partial decryptions” from t (≤ N) out of N parties. ThPKE based on the learning with errors problem (LWE) is particularly important because it can be extended to threshold fully homomorphic encryption (ThFHE). ThPKE and ThFHE are fundamental tools for constructing multiparty computation (MPC) protocols: In 2023, NIST initiated a project (NIST IR 8214C) to establish guidelines for implementing threshold cryptosystems. Because MPC often requires simulation-security (SS), ThPKE schemes that satisfy SS (SS-ThPKE) are also important. Recently, Micciancio and Suhl (ePrint 2023/1728) presented an efficient SS-ThPKE scheme based on LWE with a polynomial modulus. However, the scheme requires the use of a nonstandard problem called “known-norm LWE” for the security proof because the norm ∥e∥ of the error of the public key is leaked from the partial decryptions. This leads to the following two challenges: 1) The construction based on LWE relies on a nontight reduction from known- norm LWE to LWE. 2) No construction based on (standard) Ring-LWE has been presented. In this paper, we address both of these challenges: we propose an efficient SS-ThPKE scheme whose security is (directly) reduced from standard LWE/Ring-LWE with a polynomial modulus. The core technique of our construction is what we call “error sharing”: We distribute shares of a small error ζ via secret sharing, and use them to prevent leakage of ∥e∥ from partial decryptions.

Available format(s)
Public-key cryptography
Publication info
PKEThreshold SchemesSecret SharingFHELatticeLWE
Contact author(s)
ir-okada @ kddi com
takagi @ mist i u-tokyo ac jp
2024-05-26: revised
2024-02-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hiroki Okada and Tsuyoshi Takagi},
      title = {Simulation-Secure Threshold {PKE} from Standard (Ring-){LWE}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/239},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.