Efficient threshold cryptosystems

A threshold signature or decryption scheme is a distributed implementation of a cryptosystem, 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 exponentiation, 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 cryptosystem. 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 secret-key operation. We consider three adversarial models of increasing strength. We first present distributed protocols for constructing threshold cryptosystems secure in the static adversarial model, where the players are corrupted before the protocol starts. Then, under the assumption that the servers can reliably erase their local data, we show how to modify these protocols to extend the security of threshold schemes to an adaptive adversarial model,

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2001

Author dc:creator

• Jarecki, StanisÅ aw (StanisÅ aw Michal), 1971-

Advisor dc:contributor.advisor

• Shafi Goldwasser.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/8370

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/8370