On UC Non-interactive, Proactive, Threshold ECDSA

A presentation of the scheme, and a bit more

Introduction to threshold schemes

An (m, n)-threshold signature scheme is a digital signature scheme where any m or more signers from a group of n signers can produce signatures on behalf of the group. This signature can be later verified with a public group key, which is generated after combining the public keys of the participants. In general, a threshold signature does not reveal the actual group members that have cooperated to produce it.

The goal of a threshold signature scheme is to enforce control over the signing capability (by setting m > 1), to eliminate single points of failure (by setting n > 1), or both.

Each group of signers can be managed by a trusted group authority, which oversees joining and leaving the group. Many groups can choose to be managed by the same trusted group authority, or a group can choose to fully distribute the group management among its members such that every member is involved in all management operations.

Any subset of m (or more) out of n members of a group G can produce a signature. To do so, each member contributes a partial signature to a designated combiner, and the combiner derives the intended threshold signature from the partial signatures.

Everyone who has access to the public group key of group G can verify the threshold signature. The designated combiner can be a real entity such as the trusted group authority, or it can be a virtual entity whose operations are computed in a distributed fashion among all group members. A threshold signature scheme is robust if the designated combiner can verify the validity of each partial signature before accepting it as an input to a threshold signature.

Universally composable security

In general, the fact that a protocol is secure concerning some security notion does not necessarily imply that the protocol stays secure concerning that notion when composed with other (possibly secure) protocols. Therefore secure composition becomes a very important notion, and it is in this scenario that universal composability (UC) becomes central.

If a protocol is proven secure under the UC framework, that protocol behaves analogously to some high-level secure-by-construction “ideal functionality”. An ideal functionality F is a trusted machine that performs the desired protocol task directly, without involving any cryptography. For example, a functionality FCOM for commitments would take a value m from the sender in the commit phase and notify the recipient that some value has been committed (without revealing m).

The most important fact about UC is that if that UC-secure protocol is used within a larger protocol, and one wants to reason about the larger one, one can replace the smaller protocol with its ideal functionality and keep reasoning about the rest; this makes UC-secure protocols the gold standard: UC-secure protocols are secure composed with others.

On UC non-interactive, proactive, threshold ECDSA

In (Canetti, Makriyannis, and Peled 2020), the authors propose a threshold ECDSA suitable for any number of signatories and any threshold. The main strong points of this proposal are:

1. Execution is in up to 4 rounds, in contrast to other proposals such as (Gennaro and Goldfeder 2018) or (Castagnos et al. 2019), which require up to 9 rounds.
2. Furthermore, the proposal can execute 3 rounds in an offline preprocessing stage which takes place before the message is signed.
3. The protocol can resist adaptive corruption of signatories and includes a key-refreshing stage in this direction.

In an adaptive corrupted signatories situation, one faces the problem of having several malicious signatories that change with time. To avoid it, the proposal follows a usual strategy of other threshold schemes and divides time into epochs; in each epoch, all involved parties take part in a key-refreshment stage and update their states.

The scheme remains unforgeable as long as at most m - 1 signatories are compromised in any period that starts at the beginning of one key refreshment and ends at the end of the next key refreshment. Nevertheless, the main advantage of this proposal is that, under some assumptions, it UC-realizes the ideal threshold signature functionality.

The main drawbacks of this proposal are the following:

1. It involves both the Paillier cryptosystem and Schnorr NIZK which can make the proposal expensive in terms of computations or memory resources.
2. In the presigning stage, the participants of the signing process are predetermined.

One observes that other proposals could be a good alternative since they show better results in terms of efficiency, such as FROST (Komlo and Goldberg) or Pettit’s proposal (Pettit 2021), but none of these proposals is backed by such strong security.

This algorithm presents several strong points that deserve to be kept in mind, in particular:

1. It is based on elliptic curves, which makes it suitable for blockchain solutions such as Bitcoin.
2. It performs the signatures in 4 rounds in an interactive mode, and in 1 round if non-interactive since 3 of these rounds can be made offline.
3. The scheme refreshes keys automatically, which makes it resistant to adaptive corruption of signatories. As pointed out before, since the scheme is proactive, time is divided into epochs and, in each of these epochs, users run a key-refreshment algorithm and update their states.
4. It is secure under the universal composability framework.

It is known that other solutions, although not based on elliptic curves, have very nice properties: FROST, for instance, also performs the signature in 1 round with a preprocessing stage, but it is not as robust as the Canetti proposal. Nevertheless, there is a variation of FROST, ICE-FROST (González et al. 2021), that makes it more robust against malicious signatories by including mechanisms for the detection and exclusion of this kind of participant.

Another strong competing protocol is (Stinson and Strobl 2001): it is robust against malicious signatories, in the sense that it does not abort when a malicious signatory is detected, is parallel-secure and performs the signature also in 4 rounds. The main drawback is that it is not UC secure, but one has to ask oneself if this security requirement is too high, or if it could be sacrificed in favour of efficiency.

Although Canetti’s proposal is interesting for several reasons (low number of rounds, key-refreshing mechanisms and UC security) when compared to Schnorr-based threshold schemes, the conclusion is that it is not especially superior to proposals such as FROST, or the improved ICE-FROST: it has great advantages, particularly in terms of security, but the aforementioned solutions seem to be more efficient, at the cost of reducing a bit the security, without becoming insecure.

It is important to note that there is a lack of performance testing and comparison of the several available threshold solutions. Most of the surveys revolve around theoretical aspects and leave behind efficiency, resource requirements and timing tests. A GitHub repo collects four proposals in Rust that could be interesting to explore.

Abortion identification

In 2021 (Canetti et al. 2021) combines the techniques developed in their threshold proposal with the algorithm introduced in (Gennaro and Goldfeder 2020) to include an abortions identification protocol, meaning that the proposal is able to identify parties in the signature process who were unable to obtain a valid signature, or (at least) on of the signatories who failed in the process or those who deliberately deviated from the protocol.

The protocol consists of the 4 phases below:

1. Generation of (shared) keys. This algorithm is run once.
2. Key-refreshing of secret-key shares together with the generation of auxiliary information required for the signatures, including Paillier keys and parameters for Pedersen commitments.
3. Preprocessing of signature. This stage is performed before knowing the message to sign.
4. Computation and communication of the signature are shared once the signature has been performed.

The new protocol comes in two flavours where the main difference is located in the identification process to detect malicious participants:

1. One of the processes is not especially efficient, since it has a cost that is quadratic in the number of participants. Nevertheless, it gets pre-signing in 3 rounds.
2. The other variation is more efficient than (1), since it has a cost linear in the number of participants, but requires 3 extra rounds in the presigning stage, raising the number of rounds of the complete scheme to 10.

The authors highlight that their protocol also supports offline and fully online signatures. The main difference between them is that on the online version the parties run (sequentially) the pre-signing and signing phases every time a new signature is requested for some message known to all parties.

For the offline mode of operation, the pre-signing phase is run ahead of time, before the message is known.

In both modes of operation, the key generation is executed upon activation, and the auxiliary info and key-refresh phase are executed according to the key-refresh schedule.

A note on secure random number generation

When talking about ECDSA digital signature schemes, it is usual to end up with a reminder of how important it is to use a proper random number generator (an RNG henceforth). Before we get into the details of ECDSA concerns, let us recall what is for a random number generator to be insecure. Essentially, the lack of security of an RNG comes from four sources, namely:

1. It produces a predictable output due to a lack of entropy in the seed. As a result, an attacker can guess or even predict the output bits of the generator.
2. It resets the outputs, in other words, the RNG outputs the same bit-stream each time, for example, the system restarts. This is particularly concerning in threshold signature schemes, such as FROST, which force an abort each time a malicious user is detected.
3. If one has several devices involving the same RNG, it may be that it produces the same bits in several devices (they share an output). A user will not notice this flaw until an attacker appears with the public key. As before, this is a serious problem for threshold signatures.
4. It may not be uniform or unbiased, so the RNG may produce strings of repeated bits, such as a bunch of concatenated zeroes.

All these problems are not independent of each other, meaning that a resetting RNG may become predictable for an attacker after forcing several repetitions of the protocol. In a threshold scheme, if an attacker controls more than one user, it can realize that the RNG produces shared outputs, and this makes the RNG predictable again.

The main problem with ECDSA signatures is that each scheme includes a random nonce which must be unique and never be repeated. Failing this fact may lead an attacker to be able to obtain the secret key used to sign a message if it can get two different signatures.

The best way to avoid problems when using ECDSA is to derive nonces deterministically from the message and some secret data. If done properly, this is an approach that gets rid of any need for randomness in this kind of scheme. The main solution that uses this approach is Bernstein’s EdDSA (Bernstein et al. 2012), which offers a complex but efficient signature scheme that could be a good replacement for ECDSA. The main problem is that the algorithm uses Edwards elliptic curves which are not compatible with some existing ECDSA implementations. Concerning the second approach, Pornin’s proposal is a modification of ECDSA schemes involving HMACs to derive nonces which is compatible with other DSA schemes involving elliptic curves. Still, it was presented as a draft a few years ago.

Classification and comparison

We end this report with a classification of some of the main threshold signature schemes in terms of “implementation complexity”, which will be measured in terms of the rounds required, without distinction between offline and online.

This classification is merely illustrative and relies on the idea that the more rounds are involved in the mechanism, the higher the probability of finding human errors in the code. We are not talking about computational complexity, but a rather practical term. Having said this, the classification follows:

References

1. Bernstein, Daniel J., Niels Duif, Tania Lange, Peter Schwabe, and Bo-Yin Yang. 2012. “High-speed high-security signatures.” Journal of Cryptographic Engineering 2:77–89.
2. Canetti, Ran, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. 2021. “UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts.” Cryptology ePrint Archive, no. Paper 2021/060.
3. Canetti, Ran, Nikolaos Makriyannis, and Udi Peled. 2020. “UC Non-Interactive, Proactive, Threshold ECDSA.” Cryptology ePrint Archive Paper 2020/492.
4. Castagnos, Guilhem, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. 2019. “Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations.” Advances in Cryptology — CRYPTO 2019–39th Annual International Cryptology Conference, 191–221.
5. Gennaro, Rosario, and Steven Goldfeder. 2018. “Fast multiparty threshold ECDSA with fast trustless setup.” Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 1179–1194.
6. Gennaro, Rosario, and Steven Goldfeder. 2020. “One Round Threshold ECDSA with Identifiable Abort.” Cryptology ePrint Archive, no. Paper 2020/540.
7. Gennaro, Rosario, and Steven Goldfeder. 2020. “One Round Threshold ECDSA with Identifiable Abort.” Cryptology ePrint Archive Paper 2020/540.
8. González, Alonso, Hamy Ratoanina, Robin Salen, Setareh Sharifian, and Vladimir Soukharev. 2021. “Identifiable Cheating Entity Flexible Round-Optimized Schnorr Threshold (ICE FROST) Signature Protocol.” Cryptology ePrint Archive Paper 2021/1658.
9. Komlo, Chelsea, and Ian Goldberg. 2020. “FROST: Flexible Round-Optimized Schnorr Threshold Signatures.” Cryptology ePrint Archive Report 2020/852.
10. Pettit, Michaella. 2021. “Efficient Threshold-Optimal ECDSA.” Cryptology ePrint Archive Report 2021/1386.
11. Stinson, Douglas R., and Reto Strobl. 2001. “Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates.” Lecture Notes in Computer Science 2119.

The header image was adapted from a photo by Anne Nygård on Unsplash.