Post-Quantum Transaction Signature Breakout #8

Transcript

Antonio Sanso: Hi everyone, as this will wait a few more minutes.

Matteo Vicari: Hi, Antonio.

Alessandro Baiocchi: Right.

Antonio Sanso: Couple of more minutes, and then we'll start.

conduition: Hello, microphone checking, anybody hear me?

Antonio Sanso: Perfectly.

conduition: Awesome. I'm just gonna share my screen now to set up the presentation. Do you guys want to do anything first?

Antonio Sanso: No, no, you can go ahead.

conduition: Awesome.

Antonio Sanso: I usually do a quick presentation myself, but just back from some trips, and I didn't manage this time.

conduition: Can everybody see that? The, slideshow?

Antonio Sanso: Isn't it?

conduition: Wicked, okay.

Antonio Sanso: Alright, let's start, actually. Welcome, everyone, to the post-quantum transaction signature breakout call number 8. it might be a bit different than usual. I've been traveling, so I didn't just do a quick presentation at the beginning, and we got as well a cancellation, so we might be shorter than usual, but I'm really happy to have here condition that is showing a bit of, some optimization. If people follow these, these calls, or the post-quantum, transaction signatures, a story we have seen that we have been kind of slowly migrating towards hash-based signatures, and I hope to see… today to see a really nice optimization. I already read the article of condition, it's some really nice piece of work, and thanks a lot for sharing this.

You can switch yours.

conduition: Oh, thanks so much, Antonio. I, I think of this as more of a hacky trick than a nice optimization. But we'll see what you guys think. So, hi everyone. I'm conduition. I am a freelance, independent cryptographic engineer and security researcher. And recently my work has been focusing a lot on post-quantum signatures, and In that effort, I came up with this idea called hypertree pruning. This is an optimization to the SPHINCS+ signature algorithm, so before we get too deep into the weeds here, we should probably talk about SPHINCS+ first. I'm gonna guess that a lot of you are already familiar with it, but just to make sure we're all on the same page, and anybody watching the YouTube video would be later, I'm just gonna go over it again.

SPHINCS+ is a hash-based stateless signature algorithm that's been standardized by NIST. It uses very conservative cryptographic assumptions, which we hope are post-quantum secure. It's built out of a hypertree structure, and this is kind of a tree of trees, a tree of Merkle trees that are arranged into different layers, where each layer of the tree signs the layer below using a Winternitz one-time signature key pair. The bottom level, at the very bottom of the Hypertree, is used to certify a set of FORS key pairs, where each 4 as key pair can be used to sign an actual message, like, say, a transaction, something that we care about for the purposes of the cryptosystem. The verifier will follow the signatures and a set of Merkle authentication pads all the way back up the hypertree to the very root of the root tree.

And this root hash of the root tree is our public key. So for key generation, all we need to do is generate just the root tree. And for signing, we only need to generate the trees that are used for the signatures. And depending on the size of the overall hypertree, we have a given signature budget. And if we exceed this budget, if we create more than this many signatures, then the security of the key pair will start to degrade below a certain threshold, say, 128 bits. Now, for SLH-DSA, for example, that budget is typically quite large, 2 to the 64, but there are other parameter sets, and if you decrease the size of the parameter sets, you get lower budgets.

Now, SPHINCS+ is great. But it's also very slow, especially for signing and key generation. The main reason why is because of the Winternitz one-time signature system. If you profile SPHINCS+, you'll see that over 90% of the runtime is dominated by Winternitz key generation, and most of those are for Winternitz keys that you never use, because you have to generate all of the leaves of this tree, even if you don't use them for certification signatures. Now, there are many ways known in the literature to optimize SPHINCS+. For example, there's algorithmic modifications, like SPHINCS+ plus C, or SPHINCS+ Alpha, and these give you mild speedups, as well as better signature sizes, but they're all incompatible with each other. If you have an SLH DSA verifier, they can't verify a SPHINCS+ plus C signature, for instance, and vice versa.

But better are hardware techniques. These make better use of available hardware on whatever platform you're on, to run the same algorithms faster. You're squeezing better performance out of the same algorithms, and this can result in better speedups, orders of magnitude better, actually. Some of my recent work on Vulkan has shown you can actually improve on the reference implementation by more than an order of magnitude, and you get another order of magnitude speedup if you can use a GPU. And this is great, but it doesn't work on very weak or embedded systems. Say, hardware wallets, which is something, as cryptocurrency developers, we tend to care quite a bit about. So this leaves an unaddressed use case.

Now, it's not looking good for the benchmarks of the current generation of hardware wallets. Ledger and Trezor both take on the order of minutes to produce an SLH DSA signature, and key generation is also not that great either. And the good news here is that of those two algorithms, key generation is the only one we urgently care about. Signing can be kicked down the road because, thankfully, we don't believe that there is a quantum computer available today to threaten us, and so we can continue using elliptic curves, for now. And hopefully the next generation of hardware wallets can be better optimized for signing. But key generation we do need. We want to be able to start migrating people over to post-quantum signature key pairs today, even if they continue to use elliptic curves as their primary daily spending.

In Bitcoin specifically, we're hoping to have post-quantum fallback keys that use a, a second taproot leaf, with the new pay-to-Merkle root address format. And this way, people can start moving their money over, but still be using elliptic curves to spend today. And then, after Q-Day, they can switch over to a post-quantum scheme, if they haven't migrated to something else by then. So this is the idea from whence hypertree Pruning was born. Hypertree pruning is a way of trading off signature budget in exchange for faster performance, specifically of KeyGen, but also you can do the same for signing. In order to understand how it works, let's zoom in on XMSS. XMSS is a very key building block of SPHINCS+, and it essentially consists of a set of one-time signature key pairs, OTS keys, which you hash, and then join into a Merkle root structure.

And the Merkle root of that tree is your public key. And to create a signature, you select an OTS key pair, you create a signature, and then you construct a Merkle proof that proves that that OTS key is part of your XMSS tree. Now, the downside of this construction is you can only issue a fixed number of signatures for a given key pair. Once all of your OTS keys are used, you can't make any more signatures, so you have a fixed budget, it's finite, and once you exceed it, you instantly break the security of the scheme. Now, the other downside to this is that if you want to increase your budget, you need to generate more OTS keys, and that can get very performance-intensive quickly, especially if you use Winternitz for your OTS system.

And, one way to perhaps mitigate this, if you don't need so many signatures, but if the verifier expects you to have a tree of a certain height, is you could prune some of those OTS keys. This saves you the work of, oh, perhaps I should go back. What I mean by pruning here is you replace the hash of the OTS key with some pseudo-random garbage data. To the verifier, this looks the same as the hash of an OTS key. They can't tell the difference between the hash of a valid key and just some pseudo-random garbage. This saves you the work of generating the OTS key pair, and it does not change your signature format. And so the verifier's algorithm is unchanged.

Now, this, of course, has a drawback. It means you have one less key pair for your signature budget, and maybe this is an acceptable trade-off. Perhaps the verifier expects you to have a tree that has a very large size, but you don't actually need to create that many signatures. Now, if you take this idea to its logical conclusion, you'll end up with maximal pruning. With a maximally pruned XMSS tree, you've removed every OTS key but one, and this is basically just a one-time signature scheme with extra steps. And if you can avoid doing this, you should, because it really doesn't add anything to the OTS scheme. But, this is very useful if you apply it to SPHINCS+.

If you were to maximally prune the root tree of a SPHINCS+ hypertree, KeyGen becomes now very fast. Because now you'll only need to generate a single Winternitz key. And then a couple of surrogate hashes, which are very quick. Now, this does mean that you've decreased the size of the Hypertree overall, because now there are no Winternitz keys other than that one that you've left behind, that can be used to certify other levels of the Hypertree. This means when you're signing, you have to grind to find a randomizer that routes through that one unpruned Winternitz leaf. It also means that you now have many fewer FORS key pairs at the bottom level of the tree. And so, when you create signatures, each of those remaining FORS key pairs is far more likely to be used.

And accordingly, you have to create fewer signatures overall to get the same level of security. So, your signature budget must drop. Now, the upside to all of this is that the verifier's behavior is still unchanged, as in XMSS. You don't need to worry about the verifier, because they can't tell the difference between the surrogate hashes and the actual OTS key hashes. Now let's look at an example to see what kind of performance gains we can get from this idea. So, with SLH-DSA128S parameter set, we have XMSS trees of height 9, That means there are 512 Winternitz keys per tree, including the root tree. So you can prune 511, at most, of those leaves from the root tree. This gives about 500 times faster key gen.

And also a slight performance improvement on signing. The drawback is that your signature budget drops from 2 to the 64 down to 2 to the 55. It's a big drop. It's by a factor of 512. And the reason is because you only have one 512th as many FORS keys now. So the remaining ones are each 512 times more likely to be used, and therefore you can only produce one 512th as many signatures overall. So, what I've all just described there is Targeted mainly at improving key generation performance. But we can also use this technique to improve signing. Now, I'll skip the part where I explain why this is the case, but the… turns out the optimal way to improve signing performance with pruning is if you use what I call balanced pruning.

This is where you prune each tree across each layer of the hypertree equally. By removing the same number of Winternitz keys from every tree across every layer, you get the optimal performance improvement relative to the cost of grinding. For example, if you were to, as I've shown in this diagram here, prune half of all the Winternitz keys in every tree, this would improve your signing performance by a factor of 2. In other words, it would have the signing runtime. Key generation performance would also be halved, because key generation is a subset of signing, and the root tree is the only thing you need to generate, and so there's only half as many Winternitz keys you need to generate.

And again, just like with root tree pruning, the verifier's behavior is unchanged here. They don't notice that you're doing this at all. Now, there's a security footgun to what I've just described, which is, if you reuse a secret key with either different pruning techniques or with and without pruning, you can end up using the same Winternitz keys to sign different XMSS routes, which will result in forgeries. No good. So, to make sure you don't do that, you can either use dedicated key pairs for each pruning technique that you want to use, say, one key pair for balanced pruning, one key pair for maximal root tree pruning, and so on. Or you use domain separation, where you have different hash functions to generate different Winternitz keys for each of your different, pruning techniques.

But, that's pretty much all for the technique. It's pretty minimal. So I'm gonna go over The high-level trade-offs HyperTree pruning is a… a new trade-off dimension, essentially. It gives you a way of sacrificing signature budget in exchange for better performance, and you can balance that performance between signing and key generation. You can go for really, really fast key generation, or you can go for a little bit faster signing. And the verification algorithms aren't affected by this trade-off at all. So this is great if you had, say, a single parameter set that's been enshrined in consensus, and now you have a really weedy hardware platform that has to satisfy that parameter set. Well, that hardware wallet could,

Use pruning to get better performance. And for a hardware wallet, that's a worthwhile trade-off to make. Because every time the user signs a transaction, they have to manually interact with the device, so it's reasonable to expect that such a device wouldn't produce that many signatures. We certainly don't need 2 to the 64. Even 2 to the 55 is probably overkill. Now, this generalizes as well to any HyperTree-based cryptosystem, such as XMSS Multitree, and perhaps other HyperTree-based cryptosystems that might be invented in the future. Now, there are drawbacks, of course. As I've shown before, pruned and unpruned keys are incompatible, and it can be security footgun if you're not careful. Speaking of security footguns, I could very easily foresee developers misusing this if they prune too heavily, especially for software wallets, where you can essentially create an unbound number of signatures without user interaction.

Depending on the context. So, if you sacrifice too much security, signature budget, you could end up with, users who lower their key pairs too much, or… Or other potential, unknown unknowns. Now, this also affects privacy, because although I've said that, to an honest verifier, pruning is indistinguishable, it is distinguishable to an observant verifier who knows about pruning, and wants to specifically identify and fingerprint wallets that use it. For example, with root tree pruning. If you observe many signatures from the same key pair, you'll notice they keep reusing the same, top-level tree leaf. And that can be identified over time, probabilistically. And of course, the other thing worth mentioning is that hypertree pruning isn't as efficient as just selecting a better parameter set.

Like, maximal root tree pruning is essentially the same as just having a hypertree of one fewer layer. So, you really would be better off if you could just random, or if you could just arbitrarily select different parameter sets on the verifier. However, that said, if the verifier is static, then hypertree pruning is a great way of trading off, budget for performance, in order to please the verifier. Alright, and that's it, but there… I did skip a few things in this talk. I didn't talk about why balanced pruning is the best strategy to optimize signing performance. I didn't explain how grinding affects performance. And I didn't explain how different parameter sets work with this. So, in order to answer all these questions, you can see my article. It's posted right here, but I'd be glad to take any questions if we have any extra time.

Antonio Sanso: Thanks a lot. Actually, I have a few questions, if you don't mind. Great, great presentation, by the way. You described as a hack, I think it's a really useful one. You probably are aware of the last, request for comment of this, let's call it SPHINCS+ Minus, where… the budget was reduced from 264 to 224. Of course, like, your technique applies there as well, and I wonder… In a hypothetical scenario, people use it. and let's say they reduce from $224 with the pruning the budget, I don't know, to 216, if there's a way for the hardware 2… Actually… Warn that you are actually consuming the budget?

conduition: That would be a staple scheme, essentially, and that is something that we're considering, especially in the Bitcoin world. You would need to maintain a counter of how many signatures you use, or you could optionally refer to the blockchain, which has been discussed before, but in many cases, that's not reliable as a source of truth, since you don't know for sure how many signatures have been published. You only know how many are on-chain. The other thing worth mentioning about those parameter sets is that they use a single layer. The main advantage of Hypertree pruning is That there are multiple layers, and so if you prune one layer, say, the root tree, which makes for faster key generation, then

you only need to generate, like, maybe one or two or a few Winternitz keys at the root tree, but then the rest of your layers could still be intact, and you would still get the rapid growth of your hypertree from thence onwards. If you only have one layer. you only get to prune that one layer, so, you know, signing and keygen would be improved by the same factor, And it's… I'm not sure, I haven't done the math on it, but I imagine the performance savings might be less significant compared to what they would be for a hypertree of multiple layers.

Antonio Sanso: Thanks, makes a lot of sense. Is anyone else? Have any questions? If you don't want to speak in the chat will be as well good. Right, we get just a few comments. again, I was saying already at the beginning, today is a kind of special occurrence. We were supposed to have another presentation that was postponed for 2 weeks. I don't have a lot more on the agenda, unless if someone wants to discuss about a specific topic. I also wanted to point out, if you're interested in the topic of Quantum computers, They were, in Rome, a few nice presentations, and some panel, specifically was… presentation and a panel… so the presentation by Justin Drake, and the panel,

Danbon and Justin Drake at ETHPrague, and there was as well a panel of Danbon and Justin Drake at ETH Summit. Videos are available. If you're into the topic of quantum computers and how Quick, they can arrive, this will be a good way. To… to… a good, a good way to learn. I see another question here for condition. Did you also bench the masked version?

conduition: But when you say the masked version, does that mean the pruned version? I'm assuming so. The benchmarking? No, I haven't implemented it. And that's mainly because I just didn't have the time. The, idea is mostly aimed at, hardware wallets, so… the first thing that I would probably want to do is implement it on a software wallet, and then start looking at talking to hardware wallet developers about this. I presented this idea to Ledger and Trezor. I haven't heard back from them on it yet. Now, as for benchmarking it, it's pretty easy to figure out what the relative performance gains would be. You would just first… Isolate the performance of the FORS, the few times signature scheme, and just leave that off to the side, because that scheme is unaffected by pruning.

And then you would take the remaining runtime of the algorithm and, slice it up according to how many Winternitz keys that you prune. So, for example, with KeyGen, if you prune maximally of the root tree. you get, only 1 out of 512 keys. So, because Winternitz dominates the runtime in Hypertree, you can deduce that key generation will be about 512 times faster. And as for signing, because FORS is still a factor, you first take your HyperTree signing runtime, which is a subset of the signing procedure, and then you slice that up according to how many Winternitz keys you've pruned, so say if you pruned, half of all the keys in a HyperTree. Then you could assume the runtime will be about half, and then you add the 4 as signing time on top of that.

It's pretty easy math, surprisingly, because there's… Winternitz is absolutely the dominating factor. It doesn't actually, other factors don't affect the signing performance nearly as much.

Antonio Sanso: Alright. There's a question for you, okay. Will both EL and CL use the same PQS algorithm as SPHINCS+? Alan, I can already answer here, no. Because, for a consensus, we can actually keep the state. So consensus, we already know, is using XMSS. So, in that case, we can release statful signatures. This is not the case for Yale. I hope it answers your question.

conduition: So one interesting question that affects whether hypertree pruning is worthwhile would be. whether your verifiers are flexible or not. If your verifiers are flexible and you can dictate parameter sets more flexibly. the temperature pruning just isn't that relevant to you. But if your verifiers are fixed, well, then it does become quite useful, because then, your verifiers might have a very large parameter set that they expect you to satisfy, and your signers might not be able to if they're on constrained platforms. I see someone's asking about side channel attacks here. I'm actually not that familiar with the masked version you're talking about. But, whatever, masking that you're applying to SPHINCS+ can equally be applied to, a pruned signer, just as well.

And I imagine that whatever effect on performance masking might have, the same performance effects will apply to hypertree pruning at the same constant factor.

Antonio Sanso: Right. Any other question? Must not be necessarily a question about presentation of today, but if you have anything in mind, just… Or you want to comment on something? Otherwise, for today, just… we'll wrap here, and… And again, I apologize for the… for the short trick. occurrence.

conduition: Yeah, this is great. Thanks for inviting me, Antonio, I really appreciate it.

Antonio Sanso: It was really nice, and to be fair, I had a lot of fun reading your previous article as well. It's pretty… a lot of details, so I had to… I, like, I started reading, but was a pointer at your previous write-up before, and I used the time to read as well. For people that are interested in the gritty details, I recommend it. It's really nice.

conduition: Yeah, if you're interested in the really nerdy details of why balanced pruning is a thing, and why it's the best strategy, that's the biggest part that I left out here. And that's actually, like. I spent way too much time, and had way too much fun working that out, so… go check it out! And thanks for, thanks for listening to me.

Antonio Sanso: Looking forward to your next ideas. And, I'll thank everyone for attending, I'll see you in two weeks. It's been a pleasure.

conduition: Thanks, everyone.

Antonio Sanso: Bye.

Transcript adapted from ethereum/pm, CC BY-SA 3.0.