Re: [Cfrg] Adoption of threshold drafts by RG

[Chelsea Komlo <[e-mail]>]

Hi Phillip,


Here is a summary of how the Drivers attack [1] can be performed, and the implications for schemes that are insecure.


Let the threshold be t=2, and assume one signer is malicious. Let the number of victim's commitments that the attacker can learn *before* selecting their own commitment be k >= 2 (such as by opening many simultaneous signing connections).


After performing O(k*b*2^{1/lg(k)}) local computations (where b is the bitlength of the order of the group), the adversary can compute a valid forged signature. They do so by first completing the k signing executions, sending the victim k messages to sign of the adversary's choosing, along with their own commitments. From the victim's responses, the adversary can derive a partial forged signature for the victim over a message that the victim has never seen. The adversary then simply provides their own partial signature to complete what is a valid forged joint signature.


For a scheme defined over a group order of bitlength 256, an adversary that is allowed to make up to 3 concurrent signing operations reduces the security of the scheme to ~95 bits of security. Allowing up to 7 concurrent signing operations reduces the security to 75 bits, etc.


With that said, even if you did integrate a FROST-like approach into your scheme, after a quick look, there are parts of your design that remain insecure. For example, the stateless computation of the final share [2] would remain insecure against the Drijvers attack as the final signer is not required to commit to their nonce before seeing all other signers' commitments.


We would however like schemes that are designed for specific use cases to build upon FROST as needed. Because of the interest here and as expressed previously on this list, I would like to ask the chairs to consider moving our draft for FROST [3] forward.


Chelsea


[1] https://eprint.iacr.org/2018/417.pdf
[2] https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html#section-3.3
[3] https://www.ietf.org/id/draft-komlo-frost-00.txt