[CFRG] How to construct a hybrid signature combiner?

[Simon Josefsson <[e-mail]>]

All,

Prompted by discussions in the OpenPGP WG etc, it would help to
establish one hybrid signature construct that combine one traditional
signature scheme (e.g., EdDSA) and one post-quantum signature scheme
(e.g., robust SPHINCS+) into one instantiated hybrid signature scheme.
It should be a single identified algorithm that could be dropped into
any place we use, e.g., Ed25519 today.

Some people dislike hybrid signature schemes, dismissing them as
unnecessary, but without any concrete hybrid signature scheme to compare
with, it feels like comparing apples with imaginary oranges and
dismissing the latter because we already have apples.

For hybrid KEM, we know how to create optimized hybrids (X-Wing) and how
to safely create generic instances using Chempat --
https://datatracker.ietf.org/doc/html/draft-josefsson-chempat-00 --
however understanding the requirements took some time.

What to recommend for hybrid signature schemes?

Let's start with an example: OpenPGP consider a composite signature
scheme using ML-DSA + EdDSA like this:

  6.2.3. Signature Generation

  To sign a message M with ML-DSA + EdDSA the following sequence of
  operations has to be performed:

  1. Generate dataDigest according to [I-D.ietf-openpgp-crypto-refresh]
  Section 5.2.4

  2. Create the EdDSA signature over dataDigest with EdDSA.Sign() from
  Section 6.1.1

  3. Create the ML-DSA signature over dataDigest with ML-DSA.Sign() from
  Section 6.1.3

  4. Encode the EdDSA and ML-DSA signatures according to the packet
  structure given in Section 6.3.1.

  6.2.4. Signature Verification

  To verify a ML-DSA + EdDSA signature the following sequence of
  operations has to be performed:

  1. Verify the EdDSA signature with EdDSA.Verify() from Section 6.1.1

  2. Verify the ML-DSA signature with ML-DSA.Verify() from Section 6.1.3

  As specified in Section 4.3 an implementation MUST validate both
  signatures, i.e. EdDSA/ECDSA and ML-DSA, successfully to state that a
  composite ML-DSA + ECC signature is valid.

https://datatracker.ietf.org/doc/html/draft-ietf-openpgp-pqc#name-signature-generation

This is a naive approach.  I'm not saying it is bad, but it opens up for
questions.  Should verification fail early if one signature fails, or
should both signatures be verified and the return be A AND B?  There are
interesting oracles in here.

You could equally well consider a scheme like this:

s1 := EdDSA(m)
s2 := ML-DSA(s1||m)
return s1 || s2

However this doesn't bind public keys.  Do we need to bind public keys
to avoid some attacks?

Some properties of hybrid signature schemes are discussed here:

https://datatracker.ietf.org/doc/html/draft-ietf-pquip-pqt-hybrid-terminology-02#name-properties

The Simultaneous Verification property seems nice and strong, but is it
sufficient to generally offer good composability of two arbitrary
algorithms?

Finally:

What properties should a good generic hybrid signature combiner have?

Can we describe one example?

Can we give some examples of bad hybrid signature schemes, to better
understand the failure modes of signature combiners?

/Simon