Subject: Re: [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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 20 Dec 2019 20:02:09 +0000

As far as an RFC8032-compatible threshold signature scheme, it would appear to be fairly easy to do, as long as:

  *   You don’t mind not following the precise algorithm in RFC8032, but want something that generates signatres that is computationally indisguishable from RFC8032 signatures.
  *   You don’t mind it if the algorithm is nondetermanistic (that is, signing the same message twice, with different subsets of signers, yields different signatures).

The public keys and the verification process are completely RFC8032.

To be frank, this is simple enough that I would be rather surprised if it wasn’t already published.  However, if people are interested, I will write it up…

From: Cfrg <[email-masked]> On Behalf Of Phillip Hallam-Baker
Sent: Friday, December 20, 2019 1:09 PM
To: John Mattsson <john.mattsson=[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [Cfrg] Recommendations Regarding Deterministic Signatures

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: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 20 Dec 2019 16:19:07 -0500

On Fri, Dec 20, 2019 at 3:02 PM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> As far as an RFC8032-compatible threshold signature scheme, it would
> appear to be fairly easy to do, as long as:
>
>
>
>    - You don’t mind not following the precise algorithm in RFC8032, but
>    want something that generates signatres that is computationally
>    indisguishable from RFC8032 signatures.
>    - You don’t mind it if the algorithm is nondetermanistic (that is,
>    signing the same message twice, with different subsets of signers, yields
>    different signatures).
>
>
>
> To be frank, this is simple enough that I would be rather surprised if it
> wasn’t already published.  However, if people are interested, I will write
> it up…
>

I certainly think it would be of interest. I am not at all bothered about
strict conformance with RFC8032. If the aggregate signature will verify
correctly with legacy code, that is good enough. We would probably want to
introduce new algorithm identifiers. But we might well want to have a
nondeterministic variant of RFC8032 in any case.

The big concern that I would have is the risk that the aggregate sig
contributions might end up disclosing one of the private keys or providing
sufficient information to allow a forgery of an RFC8032 or other sig.

And then the second order concern is how to convince folk who are not deep
in crypto that the scheme is not going to break something.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 21 Dec 2019 17:37:26 -0500

OK, I think I understand it now. Will write it up.

On Fri, Dec 20, 2019 at 3:02 PM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> *From:* Cfrg <[email-masked]> *On Behalf Of * Phillip Hallam-Baker
> *Sent:* Friday, December 20, 2019 1:09 PM
> *To:* John Mattsson <john.mattsson=[email-masked]>
> *Cc:* [email-masked]; [email-masked]
> *Subject:* Re: [Cfrg] Recommendations Regarding Deterministic Signatures
>
>
>

---

From: Tony Arcieri <[email-masked]>
Date: Sat, 21 Dec 2019 14:45:33 -0800

> OK, I think I understand it now. Will write it up.

Note that the project I linked earlier already implements this sort of
scheme in an RFC8032 (verifier)-compatible manner:

I’m not saying there’s not room for improvement, just that there is already
running code.

Tony Arcieri