Paper 2023/545

Improved Universal Thresholdizer from Iterative Shamir Secret Sharing

Jung Hee Cheon, Seoul National University, Crypto Lab Inc.
Wonhee Cho, Seoul National University
Jiseung Kim, Jeonbuk National University

The universal thresholdizer, introduced at CRYPTO'18, is a cryptographic scheme that transforms any cryptosystem into a threshold variant, thereby enhancing its applicability in threshold cryptography. It enables black-box construction of one-round threshold signature schemes based on the Learning with Errors problem, and similarly, facilitates one-round threshold ciphertext-attack secure public key encryption when integrated with non-threshold schemes. Current constructions of universal thresholdizer are fundamentally built upon linear secret sharing schemes. One approach employs Shamir's secret sharing, which lacks compactness and results in ciphertext sizes of $O(N \log N)$, and another approach uses $\{0,1\}$-linear secret sharing scheme ($\{0,1\}$-LSSS), which is compact but induces high communication costs due to requiring $O(N^{5.3})$ secret shares. In this work, we introduce a communication-efficient universal thresholdizer by revising the linear secret sharing scheme. We propose a specialized linear secret sharing scheme, called TreeSSS, which reduces the number of required secret shares $O(N^{3+o(1)})$ while maintaining the compactness of the universal thresholdizer. TreeSSS can also serve as a subroutine for constructing lattice based $t$-out-of-$N$ threshold cryptographic primitives such as threshold fully homomorphic encryptions and threshold signatures. In this context, TreeSSS offers the advantage of lower communication overhead due to the reduced number of secret shares involved.

Available format(s)
Public-key cryptography
Publication info
Threshold CryptographySecret SharingFully Homomorphic EncryptionUniversal ThresholdizerShamir Secret Sharing
Contact author(s)
jhcheon @ snu ac kr
wony0404 @ snu ac kr
jiseungkim @ jbnu ac kr
2023-10-07: last of 4 revisions
2023-04-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Wonhee Cho and Jiseung Kim},
      title = {Improved Universal Thresholdizer from Iterative Shamir Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/545},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.