Welcome to the resource topic for 2023/545
Title:
Improved Universal Thresholdizer from Threshold Fully Homomorphic Encryption
Authors: Jung Hee Cheon, Wonhee Cho, Jiseung Kim
Abstract:The Universal Thresholdizer (CRYPTO’18) is a cryptographic scheme that facilitates the transformation of any cryptosystem into a threshold cryptosystem, making it a versatile tool for threshold cryptography. For instance, this primitive enables the black-box construction of a one-round threshold signature scheme based on the Learning with Error problem, as well as a one-round threshold chosen ciphertext attack-secure public key encryption, by being combined with non-threshold schemes.
The compiler is constructed in a modular fashion and includes a compact threshold fully homomorphic encryption, a non-interactive zero-knowledge proof with preprocessing, and a non-interactive commitment.
An instantiation of the Universal Thresholdizer can be achieved through the construction of a compact threshold fully homomorphic encryption. Currently, there are two threshold fully homomorphic encryptions based on linear secret sharing, with one using Shamir’s secret sharing and the other using the \{0,1\}-linear secret sharing scheme (\{0,1\}-LSSS). The former fails to achieve compactness as the size of its ciphertext is O(N\log N), where N is the number of participants in the distributed system. Meanwhile, the latter provides compactness, with a ciphertext size of O(\log N), but requires O(N^{4.3}) share keys on each party, leading to high communication costs.
In this paper, we propose a communication-efficient Universal Thresholdizer by revisiting the threshold fully homomorphic encryption. Our scheme reduces the number of share keys required on each party to O(N^{2+o(1)}) while preserving the ciphertext size of O(\log N). To achieve this, we introduce a new linear secret sharing scheme called TreeSSS, which requires a smaller number of shared keys and satisfies compactness. As a result, the Threshold Fully Homomorphic Encryption underlying our linear secret sharing scheme has fewer shared keys during the setup algorithm and reduced communication costs during the partial decryption algorithm. Moreover, the construction of a Universal Thresholdizer can be achieved through the use of TreeSSS, as it reduces the number of shared keys compared to previous constructions. Additionally, TreeSSS may be of independent interest, as it improves the efficiency in terms of communication costs when used to replace \{0,1\}-LSSS.
ePrint: https://eprint.iacr.org/2023/545
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 .