Subject: Re: [saag] [Cfrg] Recommendations Regarding Deterministic Signatures

From: Akira Takahashi <[email-masked]>
Date: Fri, 13 Dec 2019 03:00:01 +0000

On 11/27/19 12:13 PM, John Mattsson wrote:

My current view is that best practice seems to be to use deterministic algorithms (deterministic ECDSA or EdDSA) with "additional randomness" / "noise" like in XEdDSA. This also mitigates attacks on theoretical use cases where deterministically signing the same message twice leaks information.

We would like to draw your attention to our recent result related to such "hedged" constructions that derive the randomness by hashing the secret key, message, and a nonce:

    D. F. Aranha, C. Orlandi, A. Takahashi, G. Zaverucha. Security of Hedged Fiat–Shamir Signatures under Fault Attacks. 2019. https://eprint.iacr.org/2019/956.pdf

We analyzed the fault resilience of hedged Fiat-Shamir type signatures within the provable security methodology and formally confirmed that the countermeasure does thwart several recent attacks targeted at the deterministic ones.
Our result also directly applies to XEdDSA.

Best regards,
Diego, Claudio, Akira, and Greg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 20 Dec 2019 13:09:04 -0500

The objections to the deterministic signature approach raised in that NIST
paper could be avoided by applying the Kocher blinding approach whose
patent has recently expired as I point out in another message.

However, there is also NIST interest in threshold cryptography and while
{Ed/X}{25519/448} support threshold key generation and threshold decryption
and threshold key agreement, RFC8032 does not appear to be viable as a good
threshold signature scheme. (It is possible to do multi-signatures of
course and I have a defective threshold scheme that might make sense in a
TPM environment)

I will be submitting an Internet Draft describing threshold key generation
and threshold decryption by the end of the year (the code runs) and I
should have a threshold key agreement draft shortly after. It would be
really nice if we had a threshold signature scheme to complete the set (get
that 20% matched set armor rating).

In particular, I believe that we need a threshold signature scheme that is
non-interactive. This is because I need to be able to explain the scheme to
a layperson who does not understand the signature scheme. For example: The
Alice+Bob aggregate signature is secure because it is constructed a
signature contribution from Alice and a signature contribution from Bob,
both of which are secure signatures in their own right and both of which
have the same exact construction with respect to Alice and Bob's public key
as the aggregate signature does to the aggregate key.

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 20 Dec 2019 10:21:12 -0800

> as the aggregate signature does to the aggregate key.

There's already draft-irtf-cfrg-bls-signature work which supports
offline/non-interactive aggregation. BLS trivially supports threshold
signatures (although I don't see much mention of that in that draft).

https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/

Aside from a pairings-based scheme like BLS, I don't believe it's possible
to support offline/non-interactive aggregation using (EC)DLP security
alone, but I could be mistaken.

--
Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 20 Dec 2019 14:53:16 -0500

Does this scheme work? It was brought up on the NIST list.

https://eprint.iacr.org/2018/068

It would require some changes to RFC8032. But if it is secure (and I have
not read it deeply enough to even start on an opinion) and we could modify
it to use the Ed448 curve it would be a win. The signatures are not
deterministic and they are not RFC8032 compliant but if we could do
something that would pass RFC8032 validation, even better.

On Fri, Dec 20, 2019 at 1:21 PM Tony Arcieri <[email-masked]> wrote:

> On Fri, Dec 20, 2019 at 10:09 AM Phillip Hallam-Baker <
> [email-masked]> wrote:
>
>> In particular, I believe that we need a threshold signature scheme that
>> is non-interactive. This is because I need to be able to explain the scheme
>> to a layperson who does not understand the signature scheme. For example:
>> The Alice+Bob aggregate signature is secure because it is constructed a

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 20 Dec 2019 11:57:34 -0800

> https://eprint.iacr.org/2018/068

MuSig is a 3-round interactive protocol

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 20 Dec 2019 11:59:27 -0800

> MuSig is a 3-round interactive protocol

Also note that if you're okay with a 3-round interactive protocol, you can
do the same sort of thing with Ed25519:

https://github.com/KZen-networks/multi-party-eddsa

-- 
Tony Arcieri