On hybrid signatures – Key Material

Skip to the content

Search

Search for:

Close search

Close Menu

Introduction

It has come to my attention that people are wagering dinner invitations to anyone who can convince me to publicly state my opinions and reasonings on hybrid signatures. So in the interest of not having people starve, here is a blog post on this topic and the recent controversies surrounding it.

This is going to be a somewhat lengthy rant, so in case you want to check if you owe somebody dinner, here the takeaway upfront:

Using pure ML-DSA for keys that can be rotated (even if that rotation is under great pain), is perfectly fine. Using the ML-DSA44 parameter set for such keys is also fine. I won’t go as far as telling you that you should never use hybrid signatures, but I will say that hybrid signatures have a hidden cost that often makes them not worthwhile.

Why hybrid signatures are easy

The point of a hybrid construction (in this context, there are about 3 different things in cryptography called a hybrid) is to take two schemes and create a new scheme of the same type that is as secure as the more secure of the two schemes. In the case of KEMs, you need key derivation functions for this, and if you are not careful you run into weird edge cases with IND-CCA that make your combined scheme technically (although not practically) insecure. In the case of signatures, constructing a hybrid is dead simple: You simply concatenated the public keys and signatures of the component schemes, and add two ampersands between the two component verification calls. Done. You know have a EUF-CMA hybrid signature scheme.

Why hybrid signatures are difficult

It turns out that in practice, creating a hybrid signature scheme is surprisingly difficult, mostly because people cannot agree which color the two ampersands should have.

Part of this has to do with understanding what motivations people have to advocate for hybrid schemes. The first (and in my opinion only permissible) motivation is the one I outlined above, wanting to have a signature scheme that has the security of both component schemes. However, a second motivation that many people have is to use hybrids in the transition itself. The scheme level is in my opinion the wrong layer to switch schemes, but what people essentially are arguing for is to continue using their old classical keys, just now augmented with an additional PQC key.

The less harmful version of a similar motivation is to use two completely separate implementations of the schemes, for example using an HSM for the classical part and a software implementation for the PQC part. While this is less dangerous, it forces the implementation to be crossing several layers, again leading to the wish of being able to use the keys somewhat separably. And once keys are used separately, an attacker starts to be able to take a hybrid signature and rip it apart into a separate, valid signature, or take a non-hybrid signature and a broken secondary scheme and glue them together into a hybrid signature the signer has never signed.

This property is called separability, and our simple concatenation scheme is very much separable. So are pretty much all constructions, to varying degree. And that varying degree allows for discussion of the color of ampersands. For example, we could introduce a domain separator into our hybrid scheme, and hope that that would make component signatures unusable. However, domain separators need to be chosen from a prefix-free set. And if you are only adding the domain separator to the hybrid, and not the already existing classical use, you run into the problem that the empty string is a prefix of every string, and as such your set of domain separators is very much not prefix-free.

Next, we have the issue of the context. Both ML-DSA and SLH-DSA have a context parameter in their specification, and if you are trying to describe a hybrid, you have to define around that, resulting in even more possible shades for your ampersands. You either ignore it and upset some people, or you retrofit it into the classical signature scheme and upset a bunch of other people. In either case, you are dealing with far more cryptography than you originally thought.

Next, we have our old friend, prehashing. ML-DSA with external-µ uses external µ, and with it a very specific construction using SHAKE256 as its compressing hash function, while, say, ECDSA-P256-SHA256 uses SHA256. Now you could sign µ with ECDSA, inventing ECDSA-P256-external-µ in the process, but that would be a different signature scheme and now you’ve upset the people who wanted to reuse HSMs. You can add yet another compressing hash function into the mix, and now you have something that starts to resemble the current LAMPS draft, arriving at a scheme that everybody hates the least.

This still leaves probably the biggest issue with hybrids: The combinatorical explosion. Given that you can combine any two schemes, you can...