Hybrid Digital Signatures with Strong Unforgeability

Internet-Draft	SUF Hybrid Signature	October 2026
Prabel, et al.	Expires 1 May 2027	[Page]

Abstract

This document proposes two PQ/T (Post-Quantum/Traditional) hybrid signature constructions that achieve strong unforgeability under chosen-message attacks (SUF-CMA). The first, a black-box construction, achieves SUF-CMA security provided that the second component (typically the post-quantum one) is SUF-CMA secure; it differs from the current composite hybrid approach by binding the second (post-quantum) signature to the concatenation of the message and the first (traditional) signature. This approach ensures that hybrid signatures maintain SUF-CMA security even when the first component only provides EUF-CMA security.¶

The second, a non-black-box construction, requires the first (traditional) component to be built from the Fiat-Shamir paradigm, and binds the post-quantum signature directly into that component's challenge computation rather than treating it as an opaque sign/verify oracle. This variant is SUF-CMA secure as long as at least one of the two components is SUF-CMA secure.¶

3. Black-box Construction

The proposed construction ensures that the second (nesting) signature binds the first (nested) signature, making the overall scheme SUF-CMA as long as the (typically PQ) component is SUF-CMA secure. The hybrid signature construction is defined in the following subsections.¶

Before signing a message m, the hybrid scheme derives a message representative m' from m to address specific security concerns, and in particular to achieve non-separability, following a similar approach to [I-D.draft-ietf-lamps-pq-composite-sigs].¶

3.1. Hybrid Key Generation

Generate component keys

- Generate (pk1, sk1) for the traditional scheme.
- Generate (pk2, sk2) for the post-quantum scheme.
- The hybrid public key is `pk = (pk1 || pk2)`.

3.2. Hybrid Sign

The Hybrid.Sign algorithm consists of signing a message m' derived from m with the first component, and then signing the concatenation m' || s1 of the derived message with the first signature with the second component.¶

Generate the message representative

- Compute m' = Prefix || Label || len(ctx) || ctx || PH(m)

Generate hybrid signature

- Compute s1 = Sign_1(sk1, m')
- Compute s2 = Sign_2(sk2, m' || s1)
- Output the hybrid signature s = (s1 || s2)

In the computation of the message representative:¶

Prefix is the byte encoding of the string "SUFHybridSignature2025", which in hexadecimal is "5355464879627269645369676E617475726532303235".¶
Label: a label which is specific to the particular component algorithms being used.¶
len(ctx): a single byte representing the length of ctx.¶
ctx: the context bytes.¶
PH(m): the hash of the message to be signed.¶

3.3. Hybrid Verify

Verify hybrid signature

- Compute m' = Prefix || Label || len(ctx) || ctx || PH(m)
- Parse s as (s1, s2)
- Compute Verify_1(pk1, m', s1)
- Compute Verify_2(pk2, m' || s1, s2)
- Accept if both verifications succeed.

4. Non-black-box Construction

The proposed construction of this section ensures that the overall scheme is SUF-CMA as long as at least one component is SUF-CMA secure. The hybrid signature construction is defined in the following subsections.¶

The hybrid can be used for signature schemes that are built from the Fiat-Shamir paradigm as the first component and from any signature scheme as the second component. Hence, they use a canonical identification scheme (ID) underlying a Fiat-Shamir construction and a signature scheme (Sig_2). This applies to combining EdDSA and any post-quantum signature scheme, for example ML-DSA.¶

4.1. Hybrid Key Generation

Generate component keys

- Generate (pk1, sk1) for the (traditional) ID scheme.
- Generate (pk2, sk2) for the (post-quantum) signature scheme.
- The hybrid public key is `pk = (pk1, pk2)`.

4.2. Hybrid Sign

The Hybrid.Sign algorithm consists of applying the Fiat-Shamir paradigm for the first signature component. During the process (after the commitment has been computed), the second component is applied by signing the message and the commitment. The remainder of the Fiat-Shamir signature is computed using the second signature component instead of the message and the commitment as usual.¶

We use the following notations:¶

com: the commitment output by ID.Com.¶
st: the internal state output by ID.Com(sk1) alongside com.¶
chl: the challenge.¶
rsp: the response of the identification scheme.¶

Generate the message representative

- Compute m' = Prefix || Label || len(ctx) || ctx || pk's || PH(m)

Generate hybrid signature

- Compute (com, st) = ID.Com(sk1)
- Compute m'' = PH(1 || m' || com)
- Compute s2 = Sig.Sign_2(sk2, m'')
- Compute chl = PH(2 || s2)
- Compute rsp = ID.Rsp(sk1, com, chl, st)
- Output the hybrid signature s = (rsp || s2)

In the computation of the message representative:¶

Prefix is the byte encoding of the string "SUFHybridSignature2025", which in hexadecimal is "5355464879627269645369676E617475726532303235".¶
Label: a label which is specific to the particular component algorithms being used.¶
len(ctx): a single byte representing the length of ctx.¶
ctx: the context bytes.¶
pk's: the concatenation of pk1 and pk2.¶
PH(m): the hash of the message to be signed.¶

4.3. Hybrid Verify

Verify hybrid signature

- Compute m' = Prefix || Label || len(ctx) || ctx || pk's || PH(m)
- Parse s as (rsp || s2)
- Reject if rsp is out of bounds (for EdDSA: S >= L)
- Compute chl = PH(2 || s2)
- Compute com = ID.ExtCom(pk1, chl, rsp)
- Compute m'' = PH(1 || m' || com)
- Compute Verify_2(pk2, m'', s2)
- Accept if verification succeeds.

4.4. Security and Applicability

The hybrid is SUF-CMA if one of the underlying signatures is SUF-CMA secure. Additionally, the ID scheme must have unique responses and the second signature component (post-quantum component) must fulfill message-bound signatures (MBS) [BUFF] and random-message validity (RMV) [Jan25].¶

The first requirement (on the traditional scheme) is fulfilled by EdDSA which is built from an ID scheme with unique responses. The second requirement (on the post-quantum scheme) is fulfilled by any of NIST standards/winners, i.e. ML-DSA, SLH-DSA, Falcon (to be FN-DSA).¶

5. Why the Binding Hybrid is Required

Some deployments additionally require SUF-CMA, i.e. that no party other than the signer can produce a new valid signature, even for an already-signed message. This matters for example when signature values are themselves used as identifiers, deduplication keys, or inputs to other hashes (e.g. transaction identifiers, signed log entries). While a parallel hybrid is SUF-CMA only if both components are SUF-CMA and one is deterministic, it loses SUF-CMA in particular once a CRQC breaks the traditional component. Therefore, binding the components allows SUF-CMA to rely on a single component.¶

For the black-box construction, any successful forgery falls into one of two categories:¶

New signature on a new input:
The attacker produces a hybrid signature on an input m' || s1* that the legitimate signer never signed with the second component. The attacker would then need to forge a valid s2* over this new input. Producing such an s2* is a forgery against the PQC algorithm.¶
Different second-signature on an already-signed input:
The attacker reuses an existing (m', s1) but fabricates a distinct s2* for the same (m' || s1), yielding two valid second signatures for one message.¶

Both outcomes constitute a SUF-CMA forgery against the second component: the first case for a new message, the second for a second valid signature on an existing message. If the second component is SUF-CMA secure, neither case is computationally feasible, and the combined hybrid inherits SUF-CMA security.¶

For the non-black-box construction, the binding works in both directions: the second signature s2 is computed over the commitment com (and hence over the message), and the challenge chl, and thus the response rsp, is derived from s2. Neither component can therefore be modified independently of the other.¶

5.1. ECDSA vs EdDSA in Hybrid Constructions

Neither ECDSA (secp256r1/secp384r1) nor EdDSA (Ed25519/Ed448) is quantum-safe. However, they differ against classical adversaries:¶

ECDSA is not SUF-CMA, even classically and even with deterministic nonces [RFC6979]: given a valid signature (r, s), anyone can compute (r, n - s), and this is also a valid signature on the same message.¶
EdDSA is SUF-CMA against classical adversaries, provided that verification enforces the checks of [RFC8032], in particular 0 <= S < L. Its signing is deterministic, but this is a property of the signing algorithm only, and the verifier cannot check it. Moreover, anyone holding the private key can produce many distinct valid signatures on the same message. Once a CRQC recovers an EdDSA private key, EdDSA therefore loses SUF-CMA, just like ECDSA.¶

This has the following consequences for hybrid constructions:¶

A parallel hybrid with an ECDSA component is never SUF-CMA. A parallel hybrid with an EdDSA component can be SUF-CMA against classical adversaries, but not against a quantum adversary.¶
The black-box construction of this document achieves SUF-CMA with either ECDSA or EdDSA as the first component, as long as the PQ component is SUF-CMA.¶
The non-black-box construction applies to EdDSA, which is built from an identification scheme with unique responses, but not to ECDSA, which does not follow the Fiat-Shamir paradigm. The hybrid verification MUST enforce 0 <= S < L on the response. Otherwise, replacing S with S + L yields the same commitment and the same s2, so anyone can derive a second valid hybrid signature on the same message, and the construction is not SUF-CMA.¶

6. Security Considerations

6.1. Security Model and Motivation

Both constructions are EUF-CMA as long as at least one component is EUF-CMA secure (for the non-black-box construction, under the additional requirements of Section 4.4). This document additionally targets SUF-CMA, which constructions such as [I-D.draft-ietf-lamps-pq-composite-sigs] do not guarantee in general.¶

The black-box construction (Section 3) aims to guarantee strong unforgeability of the hybrid signature whenever the second component is SUF-CMA secure. This is in contrast to [I-D.draft-ietf-lamps-pq-composite-sigs], where SUF-CMA of the composite generally requires both components to be SUF-CMA. The non-black-box construction (Section 4) strengthens this further: because the Fiat-Shamir response is bound to the second signature with chl = PH(2 || s2), SUF-CMA of the overall construction holds if either component is SUF-CMA secure, provided that the ID scheme has unique responses (enforced by verification) and the second signature scheme is MBS and RMV.¶

6.2. SUF-CMA Security

6.2.1. Why SUF-CMA matters

While EUF-CMA security could be sufficient in several use cases, weaknesses in EUF-only schemes allow signature malleability (producing a new valid signature on an already-signed message without the private key), enabling real-world exploits such as replay of messages, double receipts, and log poisoning. Moreover, many current deployed systems implicitly assume that all digital signatures are SUF-secure.¶

For this reason, the construction ensures that if the second component is SUF-CMA, the hybrid resists such attacks, like recent standardized signature schemes (EdDSA, ML-DSA, etc.).¶

6.2.2. Security Rationale

For the black-box construction, an adversary attempting to forge (m*, s1*, s2*) must either:¶

Produce s2* on an input m'* || s1* that was never signed by the second component (because the message or s1* is new), which is infeasible if the second scheme is EUF-CMA;¶

or¶

Reuse an existing (m', s1) pair with a different s2*, which is infeasible if the second scheme is SUF-CMA.¶

Consequently, if the second component is SUF-CMA, the black-box construction is SUF-CMA regardless of the security of the first component, including when the latter only provides EUF-CMA security or is fully broken by a CRQC.¶

In contrast, if the second scheme is not SUF-CMA, the second attack is no longer excluded, and the construction is not SUF-CMA in general.¶

For the non-black-box construction, the same reasoning applies to s2. In addition, reusing an existing s2 with a different response rsp* is excluded, because s2 determines the challenge, and the ID scheme has unique responses (enforced by verification). The construction is therefore SUF-CMA as long as the PQ component is SUF-CMA. It is also SUF-CMA if the traditional component is SUF-CMA, under the requirements of Section 4.4.¶

This contrasts with classical composite hybrids (e.g. trad(M) || PQ(M)) where the PQ signature does not authenticate the output of the traditional signature, leaving possible avenues for replay or signature substitution.¶

6.3. Non-Separability

[RFC9955] defines both notions of Weak Non-Separability (WNS) and Strong Non-Separability (SNS).¶

The black-box hybrid construction in this document achieves WNS because the Prefix of the message representative m' is evidence that a verifier may be able to identify, preventing the validation of a component signature which would have been removed from the hybrid signature.¶

However, SNS is not achieved, as s1 stripped from a hybrid signature s = (s1 || s2) is a valid component signature of the message m' and s2 is a valid component signature of the message m' || s1.¶

For the non-black-box construction, the two components behave differently. The PQ signature s2 can be stripped from the hybrid signature and is a valid component signature on m'' = PH(1 || m' || com), so SNS is not achieved for the PQ component. However, presenting s2 as a signature on a chosen message would require inverting PH. Conversely, the traditional component cannot be separated: rsp alone is not an EdDSA signature, and turning (com, rsp) into a valid EdDSA signature on some message M would require the EdDSA challenge H(com || pk1 || M) to match chl = PH(2 || s2), which is infeasible for a secure hash function. Informally, the non-black-box construction therefore achieves SNS for the traditional component, but not for the PQ component.¶

Appendix A. Comparison of Security Properties

This appendix compares the security properties of the two constructions of this document with those of [I-D.draft-devevey-cfrg-silithium]:¶

Black-box construction (Section 3): s1 = Sign_1(sk1, m') and s2 = Sign_2(sk2, m' || s1).¶
Non-black-box construction (Section 4): the traditional component follows the Fiat-Shamir paradigm (e.g. EdDSA), rsp = ID.Rsp(sk1, com, chl, st) and s2 = Sig.Sign_2(sk2, m'').¶
Silithium, as specified in [I-D.draft-devevey-cfrg-silithium]: EC-Schnorr combined with ML-DSA, with ML-DSA signing the message with the context string R || P, and the EC-Schnorr challenge c extracted from the ML-DSA signature.¶

In the table below, "T" refers to the traditional component and "PQ" to the post-quantum component. A cell "PQ" (resp. "T") means that the property holds if the PQ (resp. traditional) component provides it. "PQ or T" means that the property holds as long as at least one component provides it. "PQ and T" means that both components must provide it. Against a quantum adversary, the traditional component provides no security, so a cell "PQ or T" reduces to "PQ". When a security property relies on several properties of a component, these properties are given in parentheses.¶

A.1. Summary

Table 1
Property	Black-box	Non-black-box	Silithium
Specification	Section 3	Section 4	[I-D.draft-devevey-cfrg-silithium]
EUF-CMA	PQ or T	PQ or T	PQ or T
SUF-CMA	PQ	PQ or T	PQ
SNS of the T component	No	Yes	Yes
SNS of the PQ component	No	No	No
Exclusive Ownership (EO)	PQ* and T	PQ* (EO and MBS)	PQ* (EO and MBS)
Message-Bound Signatures (MBS)	PQ* or T	PQ*	PQ*
Traditional component	Any	Fiat-Shamir with unique responses (e.g. EdDSA)	EC-Schnorr
Components used as black boxes	T and PQ	PQ	None
Signature size	size(s1) + size(s2)	size(rsp) + size(s2)	size(rsp) + size(s2)

* This requirement on the PQ component is met statistically by ML-DSA, independently of the PQ hardness assumption.¶

A.2. Existential Unforgeability (EUF-CMA)

Each construction is EUF-CMA as long as at least one component is EUF-CMA.¶

If the PQ component is EUF-CMA, in all three constructions, the PQ signature of a forgery on a new message is computed over an input that depends on this message (m' || s1 for the black-box construction, m'' for the non-black-box construction, and the message itself for Silithium). This input was never signed, so the PQ signature is a forgery against the PQ component.¶

If the traditional component is EUF-CMA, in the black-box construction, s1 is a traditional signature on m', which was never signed, so s1 is a forgery against the traditional component. In the non-black-box construction and Silithium, the traditional component is a response to a challenge derived from the PQ signature, which is bound to the message and the commitment. This challenge plays the same role as in a regular Fiat-Shamir signature, so the traditional part is a forgery against the traditional component.¶

A.3. Strong Unforgeability (SUF-CMA)

If the PQ component is SUF-CMA: in all three constructions, a new hybrid signature on a message either contains a new PQ signature, or reuses an existing one on the same input. In the first case, it is a forgery against the PQ component. In the second case, nothing else can change. In the black-box construction, the PQ signed input m' || s1 fixes s1. In the non-black-box construction and Silithium, the PQ signature fixes the challenge, and the PQ input fixes the commitment. The response is then unique, provided that verification enforces the range check (0 <= S < L for EdDSA, 0 <= x < q for Silithium). All three constructions are therefore SUF-CMA whenever the PQ component is.¶

If the traditional component is SUF-CMA: only the non-black-box construction remains SUF-CMA. A new signature either has a new PQ input m'', a new s2 on an existing input, or the same s2 with a different response. In the first two cases, the adversary must produce a valid response to a new challenge, which is a forgery against the traditional component. The last case is impossible, since the response is unique for a given commitment and challenge. In the black-box construction, a new s2 on an existing input directly gives a new hybrid signature, since nothing depends on s2. In Silithium, a new ML-DSA signature on the same message and context that keeps the same challenge c can be combined with the existing x.¶

A.4. Non-Separability

A hybrid construction provides Strong Non-Separability (SNS) for a component if an adversary, given hybrid signatures, cannot extract a signature that is valid for that component scheme, on any message. SNS is considered here with respect to the component schemes as they are specified and used on their own.¶

A component used as a black box cannot provide SNS, as the verifier has to extract its signature to verify it, so an adversary can do the same. None of the three constructions therefore provides SNS for the PQ component, and the black-box construction does not provide it for the traditional component either.¶

In the non-black-box construction, the traditional component provides SNS: (com, rsp) is only a valid EdDSA signature on a message M if the EdDSA challenge H(com || pk1 || M) equals chl, which requires breaking the preimage resistance of the hash function. A similar argument applies to the traditional component of Silithium, under an additional assumption on how the challenge is computed from the ML-DSA signature.¶

A.5. Exclusive Ownership (EO)

Definition: an adversary cannot produce a signature that is valid under two different public keys, possibly for different messages [BUFF].¶

In the black-box construction, m' does not include the public keys. Therefore, an adversary can keep pk2 and replace pk1 with a key pk1* under which s1 also verifies on m'. Since the input m' || s1 and the key pk2 are unchanged, s2 still verifies. EO therefore requires the traditional component to provide EO. Symmetrically, replacing pk2 requires the PQ component to provide EO.¶

In the non-black-box construction, m' includes pk1 || pk2. If a hybrid signature is valid under two public keys with different PQ keys, s2 is valid under two different PQ keys, which breaks EO of the PQ component. If only the traditional keys differ, m', and hence m'', differ, so s2 is valid for two different inputs under the same PQ key, which breaks MBS of the PQ component. EO therefore relies on the EO and MBS of the PQ component.¶

In Silithium, the same reasoning applies. If the ML-DSA public keys differ, the ML-DSA signature is valid under two different keys, which breaks EO of ML-DSA. If only the EC-Schnorr public keys P and P* differ, the contexts R || P and R* || P* differ, so the ML-DSA signature is valid for two different contexts under the same key, which breaks MBS of ML-DSA. EO therefore relies on the EO and MBS of the PQ component.¶

A.6. Message-Bound Signatures (MBS)

Definition: an adversary cannot produce a signature that is valid for two different messages under the same public key [BUFF].¶

In the black-box construction, m' is part of the input of both components. A hybrid signature valid for two messages would give an s1 valid for two different inputs m'_1 and m'_2, and an s2 valid for two different inputs m'_1 || s1 and m'_2 || s1. The first breaks MBS of the traditional component, and the second breaks MBS of the PQ component. MBS therefore holds if either component provides it, assuming PH is collision-resistant.¶

In the non-black-box construction, a hybrid signature (rsp, s2) valid for two messages gives the same challenge chl and the same commitment com for both messages, but two different inputs m''_1 and m''_2. Thus s2 is valid for two different inputs, which breaks MBS of the PQ component. MBS therefore relies on the PQ component [Jan25]. The traditional component does not help here: its transcript (com, chl, rsp) is the same for both messages, since the message only enters the construction through s2.¶

In Silithium, a signature valid for two messages gives the same challenge c, the same response x, and hence the same nonce R and context R || P for both messages. The ML-DSA signature is then valid for two different messages with the same context, which breaks MBS of ML-DSA. MBS therefore relies on the PQ component. The traditional component does not help here: R, c and x are the same for both messages, since the message only enters the construction through the ML-DSA signature.¶