Improved Universal Thresholdizer from Iterative Shamir Secret Sharing

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 secret sharing, which lacks compactness and results in ciphertext sizes of O(NlogN), where N is the number of parties involved in the threshold system, and another approach uses the {0,1}-linear secret sharing scheme ({0,1}-LSSS), which is compact but induces high communication costs due to requiring O(N5.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 to O(N3+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.