Overview

A threshold signature is a protocol for computing a digital signature in such a way that a number of participants each hold a part of the private signing key, and can cooperate to produce a signature on a message without any of the parties learning the full private key. This means that operations such as key generation and signing are implemented as secure multi-party protocols (MPC) and require communication between the participants.

A threshold key (a private key shared among the participants) is identified by a keyId. The keyId is known to all participants, and authentication is done per keyId.

The protocol currently used by the TDSA library is an honest majority protocol that remains secure (keeps the private key hidden and prevents signature forgeries) as long as less than half the participants are malicious.

Participants

There are two types of participants in the protocols.

TDSA Client Participant

Only one of the participants can be a client, but it is possible to have no clients at all. Being a client means two things:

1. The client only knows about a subset of all keyIds in the system, and can only use keyIds he created himself.
2. Normally there is no way for a client to receives messages directly, only in response to a message sent by the client.

This means that if there is a client participant in the setup, all operations are initiated by this participant. Clients are implemented using the Sepior TDSA library for either Java (also Android) or iOS.

TDSA Server Participant

The server participants are different from clients in two ways:

1. A server participant can always receive messages from clients or other servers.
2. A server participant knows about all keyIds in the system, meaning that if a server is authenticated it can use all keyIds.

The server participants are normally implemented with the TDSA service which is a server component that wraps a TDSA library with a REST interface, and also provides endpoints for the client and other servers to send messages that make up the MPC protocols.

Key generation process

This process of generating a threshold key is initiated by the client (or one of the servers if there are no clients) who calls a local method keyInit() and gets a keyId and a keyRequest back. The keyRequest is sent (out of band) to all other participants, who checks that they want to accept generating a key for that particular user. If they do then they call registerKeyRequest(keyRequest) and informs the user.

Now the user has a valid keyId, but that keyId is empty, i.e. it contains no key material for signing. The client can now call keyGen(keyId) which starts a MPC protocol that results in all participants having key material for a signing key shared between them.

NB: Before using the key for signing or giving out the corresponding public key the key should be safely backed up (see below),

Backup and restore process

After key generation the client should ensure that the key has been backed up. The are two generally different cases of this:

1. Protecting against the client losing his device
2. Protecting against any one of the other participants becomes unavailable. E.g. one of the servers crashes completely to never reappear again or refuses two participate in sign operations.

Before using the key in any way, the client should

1. Invoke backup() and store the retrieved backup in a secure place (*). This is a backup of his own key share.
2. Invoke getRecoveryInfo() and get "recovery info" for all other participants. Invoke checkRecoveryInfos(...) to make sure that all participants have given correct recovery info. Store all recovery infos in a secure place (**)

Recovering lost keys

1. Case: Client loses his device. The client must invoke restore(..) with the backup retrieved from (**)
2. Case: One or more servers have crashed and it is not possible to restore them to their former state. The client contacts the ERS with the obtained RecoveryInfo's from (*)

Sign process

The client must generate some presignatures before he can sign a message. This is done by calling presigGen(keyId, count) which starts an MPC protocol that generates presignatures.

Once there are presignatures available, a client can call sign(keyId, message). This is a local operation that consumes one presignature and returns a partial signature. The client can now send this partial signature to one of the server participants (out of band). That participant can call sign(keyId, message, partial signature) and gets another partial signature back. This continues until we reach the last participant who outputs a full signature instead of a partial signature.

The signing operation is now complete.