Efficient threshold cryptosystems
Stanisław Jarecki, Shafi Goldwasser · DSpace@MIT (Massachusetts Institute of Technology) · 2001
A threshold signature or decryption scheme is a distributed implementation of a cryptosys-tem, in which the secret key is secret-shared among a group of servers. These servers can then sign or decrypt messages by following a distributed protocol. The goal of a threshold scheme is to protect the secret key in a highly fault-tolerant way. Namely, the key remains secret, and correct signatures or decryptions are always computed, even if the adversary corrupts less than a fixed threshold of the participating servers. We show that threshold schemes can be constructed by putting together several simple distributed protocols that implement arithmetic operations, like multiplication or exponen-tiation, in a threshold setting. We exemplify this approach with two discrete-log based threshold schemes, a threshold DSS signature scheme and a threshold Cramer-Shoup cryp-tosystem. Our methodology leads to threshold schemes which are more efficient than those implied by general secure multi-party computation protocols. Our schemes take a constant number of communication rounds, and the computation cost per server grows by a factor linear in the number of the participating servers compared to the cost of the underlying