Enhance Research and Development in India with Digital Signature Licitness

How to eSign a document: digital signature licitness for Research and Development in India

- [Alexandre] Welcome, everyone. My name is Alexandre Bouez and today, I'm going to be presenting actually my master thesis results. So during my master's, I did an internship at a company in Paris called IRT SystemX with Kalpana Singh, so this is a joint work. And at this company, we had a client that I can't really disclose who had a very specific use case in which they wanted to use threshold ECDSA. But looking at the state of the art in threshold ECDSA, we realized that there was nothing that quite fit what we wanted to do. So we ended up devising our own protocol. Today, I'll be talking about non-interactive threshold ECDSA without roll call, the added benefit of this protocol being the without roll call part. But no worries, I'm gonna start by introducing all of these terms. So let's start with what threshold cryptography is, which is kind of the basics of this talk. So in a threshold cryptosystem, you have a private key that is distributed amongst a group of people. So here, we have five people and they each have a share of the key. And the benefit of threshold cryptography is that supposedly, a certain number of people, whoever they are within this group, should be able to reconstitute the key. Here, we have a two-five crypto system, so you'd need at least three people to be able to reconstitute the key, but it can be any group of three people within the whole group. Here's a more formal definition. This is something that a lot of people discuss, should it be t plus one or t signers? In this presentation, it's t plus one. And why is this useful? Well, it's very useful for shared accounts, it's useful for voting systems, and in the case of our client, it was useful because they wanted to distribute a key amongst the board of a company and for the board to be able to sign decisions directly using their shares, and so it's kind of a voting system. Next up is ECDSA, so this whole signature scheme we did in ECDSA, the reason for which is that it's a very widely used signature system. I won't go really into the detail of its inner workings. The only thing we kind of need to know for the later part of this talk is what an ECDSA signature looks like, which is this. And the important part for us is, so you have a value k, which is a random value which defines the security of the signature, m is the message, and r is a public value that is defined using k, but then x is your private key. So this would be the private key distributed amongst a group. And in this signature, the thing that is kind of problematic for us is that there is a multiplication between k and x and both of these values have to stay secret, so how do you compute a multiplication of secret values that are divided amongst a group without revealing them or the shares? It's kind of a hassle. Next up is non-interactivity. This is something that is very useful for specific use cases, for this company, it was useful because they want to be very efficient, very quick to sign messages. So let's say you have three people who want to sign a message together. One is in New York, one in Paris, one in Tokyo. If you have multiple rounds of interactions required for them to be able to sign something together, that would mean that it might take multiple business days, which is not good. So a non-interactive threshold scheme is a scheme that requires the players to only send a single message in succession without having to communicate with each other to be able to generate a signature. And this is kind of easy to achieve for some signing schemes, but it's a bit difficult to achieve for ECDSA because of what I was mentioning before. So one way of doing this is, in the current literature, is something called a one-round online protocol, which is kind of non-interactive but also, it's kind of also a trick that they use where you divide the signing of a message into two phases. You have the pre-signing, which happens before you know what the message even is and where you shove all of the complicated communications and computations and you don't care that this takes a lot of time because the messages aren't even known yet, you can do these, a lot of these a long time in advance, and then you have just preSignatures stored somewhere that you will be able to use when you want to sign something. And then the signing, which happens after the message is chosen and which should only require a single step of interaction. So this vision of one-round online scheme is where the issue that we were having for our use case starts to appear. So the issue is that, in most current schemes, I'll get back to the most later, but at the time, it was in all current schemes, the pre-signing only involved the signers. What does that mean? That means that, before you even know what the message is, you have to be sure who is going to be signing the message. Sounds a bit weird. So one comment that we got, one common solution that was just thrown about in the literature was, why not prepare for every subset? I mean, that could work. In our case of five people, there aren't that many groups of three that could sign together, so you could prepare for every subset. But first of all, this can get very computationally intensive once the group gets large. In our case, we had 100 people, so that starts to be a bit voluminous. And it creates a lot of sensitive data that you need to store in a secure way. So you don't really want that, it's annoying, it's a hassle. But there's also another issue. That issue is that you have a hidden round of interaction that people were not discussing then even if you do this. Let's take an example of where we are only going to look at the signing phase, so let's imagine they prepared all of the possible groups of the pre-signing, they have these stored. Let's say the top person over there wants to sign a message, he sends it to everyone else. Well, he can't really send his signature share without knowing who else is signing with him. So he needs to wait until at least two of the other people answer him to say, yes, we want to sign with you. Then and only then can they all compute their signature share, which is dependent on who else is signing with them, and create a signature for the message. So there's this hidden round of interaction there of having to choose who is going to sign, and this is what I call a roll call. And our protocol is one that doesn't require this, the whole point is we wanted to remove this. So when you use our protocol, let's say there's, again, the top person wants to sign a message, he can tell everyone I want to sign this and then he immediately chooses one of the preSignatures, whichever, 'cause they all work, and he sends his share of the signature, which is independent from who else is signing with them. Then the only thing that the others need to do is send their share of the signature. And once they have enough shares of the signature, you can compute the signature of the message. And this computation doesn't have to be done by any specific member, it doesn't even have to be done by a member. Once you have enough shares, it can be done by an automated system, a computer, whatever, you can compute the signature. And this also has the benefit of only using a single preSignature, some people were proposing schemes where you start by using a lot of them, one for every subset, and then you slowly make like a precise who is going to be signing with you, but that consumes a lot of preSignatures, it's not very efficient. Okay, finally for the introduction, a small overview of the state of the art. The most interesting protocols that existed at the time first were those of Gennaro and Goldfeder. Why, well, because they are very widely used, but also most importantly for me, as someone who wanted to give something to a client, these protocols were already implemented by a company that is maintaining their code, so it was very practical if we could just use that. Another very good protocol that already existed at the time is that of Canetti et al., which is kind of similar to the protocol of Gennaro and Goldfeder, they kind of came up with it at the same time and they use similar things, but they're not exactly the same. They're even so similar that the two main speakers of these, the two main writers of these articles ended up collaborating together to write another protocol that kind of has the benefits of both of these protocols merged together. So that was the state of the art when I started, and there were no protocols that were without roll call at the time, all of those required you to know before you even do the pre-signing or at least before you start signing who is going to be signing with you. So our, in this category of protocols without roll call, there is ours, obviously, that's why I'm here. But in 2021, there was a protocol that was published by Michaella Pettit that I have to mention because it is extraordinary. And that protocol is also without roll call. And it is one of the most efficient protocols in terms of computations that exist, it is very fast. The only issue with that one is that it comes with this drawback where the threshold, the number of people that have to sign with you cannot be more than half of the people. So you can't really make a voting system out of this one because you can't have a threshold that is very big. So it's kind of a big restriction there in terms of the parameters of the protocol. Okay. So now that this is done, we can dive into how the protocol works, and I'm gonna have to start by introducing a bit of math, so it's gonna get more complex from now on. First up is something called commitment schemes. So a commitment scheme is a set of two functions. One where you are going to commit to a value that you've chosen, so you send a commitment to everyone and later on, you will decommit that value so the people know that you didn't change your value in the middle. It's maybe a bit abstract, but a very common commitment scheme that is used in our implementation is a hash-base commitment scheme. So instead of committing, what I do is I publish the hash of my message earlier. So later when I publish the message, you can verify that I didn't change it, unless I'm able to break a secure hash for some reason. Next up is additive secrets, this is fairly straightforward, I just have to introduce them. An additive secret is a secret shared amongst a group of people where you need everyone to cooperate in order to reconstitute the secret. The simplest kind of secrets are additive secrets where the secret is set to be the sum of the shares. And this is kind of useful in multi-party computation to create nonces, so single-use random values where you know that no one had a hand in choosing that value. So one way of doing it is everyone commits to a random value that they choose and you wait for everyone to have committed and then you decommit them and you set the nonce to be the sum of these values, so then no one could have chosen the value. And, but this, what we are doing, is thresholds, cryptography, so obviously, we are going to need some kind of threshold secret. And nearly all the threshold cryptography protocols that exist are based on one kind of threshold secret, which is Shamir's secret sharing. And that itself is based on the Lagrange interpolation. Very briefly, I won't go into any details, the Lagrange interpolation is a theorem that tells us that a polynomial of degree t minus one can be uniquely defined by t different points. It sounds a bit complex, but a restriction of this that everyone knows from high school at least is saying that, well, a line can be defined by two points because a line is a polynomial of degree one. And we can extend that higher saying that a polynomial of degree two can be defined by three points. And this we can use to make threshold secrets. So let's take a group of five people and let's take a polynomial of degree two, we can pick five points on this polynomial, we gave to each of these people one of the points on this polynomial, and then logically, any group of three will have three points, can find the polynomial and find a secret, which we will say is the value in zero. So this is how threshold secrets work. Another benefit of a Shamir secret sharing is that polynomials are linear, which means that you can do sums of polynomials, if all of these people add their shares of two secrets together, then they will have a sharing of the sum of the secrets. It's quite interesting, another application is you can use it to do verifiable secret sharing. I won't go into the details of how that works, you can look it up if you're interested. Here is a formal definition of Shamir secrets, and the reason why I need this is because I need to talk about why the issue of the roll call that I'm discussing here had never really been discussed yet in the literature. So if you look at how a Shamir secret works, you'll kind of see that there is two versions of the shares that exist. First up is the share that is distributed amongst the people, all of the people, so it's the point on the curve, and that's gonna be here yi, so you get a point. Once you know who else is signing with you, you know who the other participants are, you want to turn this Shamir secret, which is threshold distributed amongst five people, into an additive secret distributed amongst three people. The way that you use this is you use something called the Lagrange coefficient. And that Lagrange coefficient is dependent on who else is signing with you. In a lot of the literature, the yi and the yi,S values are used interchangeably and sometimes have the same notation, which is kind of hiding whether or not you know who else is signing with you and what the subset is, which makes it kind of difficult to understand if a protocol is with roll call or not. And this is something, this is not a notation I invented, this is a notation that already exists that you can find in some of the literature. So it's good to try and use it from now on to be sure of what you're doing. So within a subset S, we are going to call the yi,S the local share of the secrets. So it's an additive secret within that subset. Okay, and finally, last preliminary, sorry about all of this, it was very dense. There is something that we use extensively in these protocols called the MtA protocol. The MtA protocol means multiplication to addition. It's gonna allow you to turn a multiplication of two secret values into an addition. So let's say Alice and Bob each have a secret value a and b, they don't want to share it, they want to obtain an additive distribution, an additive sharing of these values. What they're gonna do is Alice will send an encrypted version of her value using homomorphic encryption. Then Bob can perform a computation there with the encrypted version of the value and he will select a random beta there. He will send his, the results back to Alice who can decrypt it, and these values alpha and beta, if you look it up, they sum up to a times b. And this seems very simple but also, we can extend this to additive secrets where, if every pair of players performs an MtA like this with some sorts of equation, you can obtain a new sharing of x times k, even though these are secrets. So it's very practical for these kind of protocols. Good, we're done with the preliminaries, let's look at these protocols. So first, the protocol we're going to dive deeper into is the one that I base my own protocol on, is the protocol of Gennaro and Goldfeder from 2020. So the key generation starts using VSS, I said I wouldn't go into what that is, it's just how to create securely a Shamir secret without having any kind of, sorry, any kind of trusted party distributing the shares, you want to do this just amongst the players. So in the key generation, the players will create a sharing of the private key, so they're sharing of a Shamir secret sharing of x. And then during the pre-signing, which is when the subset S is known, the players will first start by generating a nonce, so this is an additive sharing. Then they will compute the public values R, which I don't go really into the detail of because we have not changed that, these are just public values needed to compute the ECDSA signature. And then they have to use an MtA to compute a sharing of k times x. And the only reason that this works here is because you know who the subset is, x can be transformed into the additive version of x. And so they can use the MtA protocol I was describing before to obtain a sharing of k times x. And finally, once the message is known, the players will all, all the players who want to sign will publish this and the Sis will form an additive sharing of the signature. Fairly straightforward, fairly easy if you actually dive into it. And we needed to modify this so that you don't need to know who the subset is for the pre-signing. So let's look up what we did. Here, there is a typo, the subset S is unknown, sorry about that. So basically, one way of summarizing what we did is that, in our protocol, everything is a threshold secret, there is no additive secrets, we just need everything to be threshold. So instead of generating K as a nonce, as a additive secret, we generated using VSS the same way that we generate a private key. Next, we actually used the same version of computing the R values that they used in their protocol. So the way that we do this is we enlist the subset of the players to, of the parties to do it. They don't need to be the same subset that will sign, so it doesn't affect anything, it's just, it was already very efficient, why change it? And next, that is actually one of the main contribution of this protocol. We devised a modified version of the MtA that could work between two Shamir secrets. So the players will all have to start by creating two threshold secrets locally that they keep for themselves so they know all of the shares and they know the secrets. And then they will perform a modified version of the MtA that is in the article between all of the players, even those who won't be signing later on, and they will obtain these values ai j. And these values will actually, in our protocol, be made public, they will be published. The reason why this is not revealing any information is because both of the players who participated there put one of the local shares they created into it. So it's kind of hidden, the information cannot be obtained. And once they've published all of this, the pre-signing is done. When you know what the message you want to sign, the players can choose one of the pre-signings that they performed, they compute these values si. And then using these values si as well as Lagrange coefficients and the values that were published in the pre-signing, they can compute the signature over there. Finally, we actually implemented this protocol because we needed, well, to give it to the client and we performed some benchmarking on it. But unsurprisingly, we find that our protocol is actually not as good as Gennaro and Goldfeder in terms of speed. But the reason for this is that actually, if you divides the benchmarking between pre-signing and signing, you will see that, well, our pre-signing is in constant time ing to t because, well, we enlist all of the players in the pre-signing, whereas theirs do not. However, our signing compares to that of Gennaro and Goldfeder, so we are not slower in the signing, which is the important phase of the protocol. So that's it for my talk, a little overview of what we did. So our protocol removes the issue of the roll call and it also works for any value t that is less than the number of players. It is somewhat easy to implement using a Gennaro and Goldfeder implementation, I was able to do it, I'm not a computer scientist, I'm a mathematician. And our implementation is actually already available online, however, you should not use it for security reasons, we are not maintaining it, so please try to re-implement it yourself. And even though it is slower during pre-signing, it is just as fast during signing, which is the important phase. Thank you for your attention. (audience applauding) - [Host] If anyone has any questions. - [Audience Member] You mentioned the literature, what literature do you reference when you're studying these things? - [Alexandre] Oh, well, there is quite a bit of literature there, but the non-interactive threshold ECDSA literature is a bit smaller than other ECDSA literature, mostly the works of Gennaro and Goldfeder and the works of Canetti et al. and the people that they worked with are the most predominantly used, the most predominantly discussed. There are alternatives, but people are somewhat starting to move towards Schnorr for this kind of use cases because the Schnorr signature is a bit easier to work with in a threshold environment. So yeah. But as I said, the work of Michaella Pettit is extraordinary if the restriction that she has on her work is not an issue for your use case. - [Audience Member] Is it extraordinary mathematically or is it extraordinary in computer science? - [Alexandre] It's, I think mostly, well, mostly mathematically, it has the same complexity per se, but it is just so much faster because of the tools she's using. There was a question over there, yes. - [Audience Member] Hello, thank you so much for your talk, you definitely refreshed me really well on the topic. And my question was, how much does the curve selection mattered in your protocol? You are using, is it ECC? - [Alexandre] So actually, this protocol can work for any curve so long as the format of the ECDSA signature stays the same, which normally, it always does. - [Audience Member] Wonderful, and do certain curves, from what I remember on the topic, some curves have certain properties and they perform better in certain aspects than other curves, is that true? - [Alexandre] I'm not familiar enough to actually say, sorry. - [Audience Member] That's all right, no problem, thank you. - [Host] Yeah, that concludes the first speaker. - [Alexandre] Thank you. (audience applauding) - [Burt] Okay, and thank you again for that talk, Alexandre, good to see the state of the art continuing to improve. I'll be next talking about some work we're doing at Verisign Labs on post-quantum cryptography with my co-authors Andy Fregly, Joe Harvey, and Swapneel Sheth. So if you've been following the developments in post-quantum cryptography, then you probably know how much good work has been done through this effort led by NIST to identify potential candidate post-quantum algorithms. And even though narrowing down to a short list, there have been so many alternatives considered, but in the short list of digital signature algorithms, one thing seems to hold true. They all have large signature sizes, at least much larger compared to the size of signatures we have today. Now, as data sizes have gotten larger over the years, maybe that's not a problem at all, in some applications, you don't notice the difference if you've moved to signatures that are 10 or 100 times longer. But in other applications, you will, in particular, in critical infrastructure applications like the domain name system where size is still a constraint for moving packets around in some of the underlying protocols. And so when we start to look at these longer signature sizes, there could be a concern that they just won't fit. So as part of the research and development effort on post-quantum, it's important to look at possible alternatives that can reduce the size, impact, and practice, that's what I'll talk about for the next 20 minutes. Let me show you graphically the sizes that you might come to expect, so the first five rows are post-quantum algorithms, the last two are the legacy elliptic curve and RSA. And for the first five, I've illustrated the level V from the NIST PCQ evaluation, these have 256 bit security against classical attacks, 128 against quantum attacks, and they range in size from 1,280 bytes for Falcon, the second row, to 49,856 bytes for a SPHINCS signature in the full size, in that case. Relatively speaking, you can see how much larger those signature sizes are than the classic ones, which happened to be at a shorter size and a shorter security level. But in terms of what industry's been accustomed to today compared to what industry might have to contemplate next, my co-author Andy Fregly has talked about problem we call the tail wagging the dog. If you have some very large datasets, all of which have small records, and then you add signature to them, you might find that 99% of your storage is for signatures and the other 1% is for the data, that doesn't seem to be the right balance if you could avoid it. Even if you go with the level I or II parameters, the 128-bit security levels for the NIST PQC signature algorithms, you're still seeing sizes 666 bytes or more. So that's motivated our research to ask, well, what can we do? And I'll jump to the conclusion but show you how we get there. We can show, by using these algorithms in combinations with other Merkle tree techniques, we can get, for certain parameters, sizes that are, say, around 472 bytes consistently for what we call condensed signatures and then some overhead that I'll describe later. So without changing the algorithms, just using them in a new way, that's why we call it a mode of operation, a mode of operation. It's good work already done for all these algorithms, but how do we use them more efficiently? So the main concept that I'll spend time on is something we call Merkle tree ladders. There just been so many good uses of Merkle trees over the years and so many of these concepts build on one another, and you'll see how Merkle tree ladders will give you some additional flexibility in applying Merkle trees. So here's your classic Merkle tree. Here, I've identified the root node with the label 1 through 14, that's authenticating 14 leaf nodes, it's the usual recursive process so that all of those leaf nodes are then represented by that single root node. And I follow what's fairly conventional in doing a allocation to the left side and the right side, we'll take the largest power of two that fits on the left side and then the rest will be on the right side, and that proceeds recursively. A lot of ways to do this, this is the one that we've adopted in the paper. The authentication path then, as you're accustomed seeing, is the siblings of any given note, so if we want to authenticate that seven belongs to this tree as represented by the root, then reveal the siblings of seven along the path that takes you up to the root, that will be eight and the five six, then the one four and then the 9 14, hash all those together in succession, confirm that you're at the root, okay, that's all familiar Merkle tree material up to this point. The new concept that we've described in the paper is a Merkle tree ladder, a Merkle tree ladder, now, you notice I've made one change from the previous slide to this one, there's no longer a root, in fact, there are multiple roots, there are multiple trees, those trees were subtrees of the original tree. And these three nodes, the ones I've circled, one through eight, 9 through 12, and 13 through 14, collectively authenticate all the leaf nodes. So we take the three of those and with any one of those, you can then authenticate some subset of the leaves. And we'll call those a ladder and call each of the entries in the ladder a rung. I think of that as a way to climb the tree to get to all the points that you can use to authenticate all the values, so if it's a Merkle tree root, your ladder has one rung at the top, you're just climbing the tree all the way to the top to the root. Here, you're climbing to different places. And the goal is for these places to remain relatively stable over time. So once you've put a rung out there, you can keep using that rung. In the literature, this has been called a binary numeral tree, history tree, Merkle mountain ranges, and so on, with this particular structure of taking largest power of two, then the next largest power of two that's left over, and so on. But it's much more flexible in concept, as we describe in the paper, you can use other ladder structures by choosing other subsets with different trade-offs, here, I'll use this binary structure. So what happens when you add more leaves to the tree? We added another five leaves, we're up to 19, now we have different rungs. So we'll have the 1 through 16 rung because we've reached that power of two, then a 17 through 18 rung and then the top one, the 19 through 19, and that continues onward. And then if you look at your authentication path with this ladder, so we're back to seven again, seven siblings or then the eight, the five through six, the one through four, the 9 through 16, that will take you up to the 1 through 16 rung which covers the seven leaf. But you'll notice what's happening along the way. You're going back through the same path you started with when you had only 14 leaves in the tree. In particular, you're going back through the one eight. So if you have this path from the seven to the 1 16, you don't need to have ladder 19 to verify it, you can verify it with ladder 14. Ladder 14 has a rung that's along the way, the one through eight, so that very same path can be authenticated by a previous ladder. Okay, this is a property that Reyzin and Yakoubov observed in their paper on cryptographic accumulators and they called it old accumulator compatibility. And so it's an example of a more general case of having ladder compatibility. Okay, so why will that be important? We'll see that in a moment. Now, Merkle tree ladder mode is a way of applying this ladder construction to digital signature schemes. Remember, the problem that we have is we're trying not to have such large signatures every time we sign something. And so Merkle tree ladders will help us get shorter signatures and will result in a format that has three parts. The first part is the authentication path, the second part is a ladder, and the third part's a signature on a ladder using the underlying signature scheme, so I've drawn that so that looks somewhat larger, that's the large part, that's the part you don't wanna send if you don't have to. The relatively short part is the first part, which is this authentication path, logarithmic in the number of leaves in the tree, and the second part's the ladder, which is depending on how many rungs you have in your ladder. So those are relatively short but particularly, that authentication path's gonna be short. And I've drawn it like this with the following symbols, i is the index of a leaf, so it was seven in the example before N is the index of the ladder that the authentication path goes to. So in the expanded case, it's 19. And N prime is the index of the ladder that the verifier already has or whoever's processing that signature already has, N prime would be the 14. So we have from 1 to 19, but 14 is what you already have. And that says signature verification will work through this compatibility property if the i is less than or equal to the N prime and the N prime is less than or equal to the N. When you initially generate, of course, they're all equal, because the first time I generate, it's the very top rung, and that's the path taking me to the top rung. So what we wanna do is generate signatures like this. And the reason we wanna generate them is because we can find a way to shorten them. 'Cause you're looking at me at this point and saying, wait, you've just taken a long signature and made it longer. So how did that help? It helps because we can actually make it shorter. And this is a process we introduced in the paper called condensation and reconstitution. So imagine you have an initial signature, in fact, an entire set of initial signatures, so I might have published all my signatures in this initial form with their authentication path, their ladder, the signature on the ladder. And then I wanna send you information that's sufficient for you to authenticate one of those signatures, to verify one of the signatures. I'll send you what we'll call a condensed signature, which will replace the authentication path in the initial signature with an authentication path to my current ladder. That's what I've shown on the right-hand side, the signer's current ladder in combination with the signature on the ladder is the signer's current reference value. So the signer has some reference value, whenever the signer is sharing signatures, the signer replaces the original, the initial path from i to i with a path from i to N. And then some handle chi sub N, which is a pointer to that reference value. Now, what does the verifier have at this point? A particular verifier may not yet have caught up with the signer's current ladder or reference value. That particular verifier may have an earlier ladder and reference value lambda N prime. Remember, the 19 and the 14 and the seven before, so it may have 14 when the signer's already up to 19. And so that verifier is gonna reconstitute by combining the condensed signature that arrived with the reference value that the verifier has, and as long as i is less than or equal to N prime is less than or equal to N, the verifier can then verify the reconstituted signature. So our goal is that the verifier doesn't have to update that reference value very often. In fact, if you signed everything all at once, the verifier would just need one reference value. But we wanna be more sophisticated than that because we might be continually having new things be signed, and so the verifier has to keep catching up. Question is, how often does the verifier have to catch up? Okay. So we'll turn briefly aside to some security proofs. And just show you, you can look at more detail in the paper. Does Merkle tree ladder help you or not in terms of your security? Well, we don't want it to hurt to add Merkle tree ladders, and with some of the conventional notation here, we can show that the adversary success probability in Merkle tree ladder mode is no more than it would be with the underlying hash function, sorry, the underlying signature scheme, plus two additional terms that depend on the number of hash queries that the adversary performs divided by the sizes of our parameters, but this is pretty good as things go in security proofs. There's a linear growth on the right-hand side, so more queries divided by the number two to the l, that's how you can figure out what your sizes need to be. We do a slight modification of this Merkle tree ladder mode, it's called robust, this is borrowing from concepts in the XMSS-T and in SPHINCS. And we can then model more of the components in the standard models, so you see more of the InSec terms on adversarial capabilities there, and similarly still have a linear increase on the end, okay. And finally, you need to show security against quantum adversaries for anything post-quantum. And here, in this quantum setting rather than linear, you get either the second power or the one and a half power and bring in the number of signature queries. All of that leads to the following conclusion. How long do your parameters need to be? How long do you need your hash function and your randomizers to be? And consistent with other hash-based signature schemes, we end up with hash outputs of 128 or 256 bits, depending on the security level you're looking for, quantum security and all that works out. Those of you who've seen this before understand the flow for this, but where I can move ahead on this is simply saying, uses hash functions, it's consistent in its security, you'll end up with similar sizes at the end. So what's the practical impact? Does this really help? Did it really reduce the amount of bits that you need to transmit? And so I'll show you one model, so remember the use case that motivated the research is a domain name system, the domain name system's security extensions adding digital signatures on records. And we can model this by imagining that we have a set of DNS records that have been signed already. Call this N sub zero records, imagine 10,000 records, that's the primary use. And then this set of records is being updated over time and new records are being signed. So let alpha be the number of new records per iteration, if you like, for every minute. There's so many additional records that are added to your set and they get new signatures. And there are multiple requesters who are trying to verify those signatures and imagine that, for a particular requester, there are rho messages requested by that requester where the signatures need to be verified. So alpha and rho give you some parameterizations on this. And I've oversimplified, but it seems to hold up in practice if we assume that the verifier is asking for a random message to be verified. Remember, it's a set of messages signed and published, that's how DNS works, publishing information about names and IP addresses and so on. The provisioning takes place in advance, the signatures are computing in advance, and then the verifier's interest depends on where the verifier is navigating to. So the verifier in effect is looking up randomly among that set, not looking at all of them. If the verifier had to get each and every one of them, that's a different problem, the verifier is looking randomly in the set. And assume that the verifier initially has a ladder that covers the first N zero, the first 10,000. Here's our question, how long until the verifier needs a signature on something that has an index bigger than N zero? So new things are added, verifier is choosing randomly among the set of everything that's already been signed. What's the chance that the verifier asks for something beyond 10,000? Well, obviously, the further you get from 10,000, the higher that probably becomes. This will turn out to have an analysis very similar to the birthday paradox, and we'll see a square root of N term on the right-hand side. The number of messages that the verifier requests until there's a 50% probability that the verifier goes beyond 10,000 with its index is roughly a constant times squared of N zero times rho over alpha. And we can take a closer look at some of that through this chart where I've plotted on the X axis how many requests per iteration, the rho value, on the Y axis, how many messages until the next reference value. And then the three lines are drawn from top to bottom in increasing values of alpha, how much is added? What I want you to take away from this is that, at least for a good part of this chart, it's more than 10 requests, maybe 100 requests, until you need to get the new reference value. It will be highly dependent on your parameters. So we had to do some modeling on this. This is what it shows you in terms of the effect on the signature size, starting with these 50,000s down to single thousands and below because we're amortizing the cost of that single ladder with its signature across all of the requests that come in. So send these condensed signatures, the authentication paths, and the occasional reference values. The effective size then moves down to something much more practical. And we did some analysis of existing DNS datasets to see what would've happened if this dataset had implemented something like Merkle tree ladder mode, this is from a 24-hour sample in the DNS-OARC Day in the Life dataset from 2015, I think. And each one of those dots represents a single requester relative to some dataset. And if that requester had used Merkle tree ladder mode, how often would it need to request a new ladder? And we assess that by looking at the signature inception time. And when did the signature inception time on the signature return increase, when did we reach a new maximum, how many times per day? Actually, we saw, in this particular data series, we didn't have more than 29 new reference values per day. But in general, for the fastest querying requesters, they had endurance of 100 for their ladders, meaning that on average, they could use the same ladder more than 100 times to verify signatures before they have to get the next one. Even the slowly querying ones were at least 10, that's the Y axis on here. So it says there's some hint of practicality if we were to use this, we wouldn't be adding more complexity without any benefit. And this is what a system will look like with this implementation, so on the left-hand side, you see the sizes of the condensed signatures. Again, this depends on parameterizations and so on. The right-hand side, the size of the reference values, you get those when you need them. So there's some overhead for that, but you could fit the condensed signatures into the regular protocol without necessarily increasing the overhead. Okay, every one of these presentations has a call to action at the end, things to do next, so I'll leave you with a few things to think about next and then we'll take some questions. So one, take a look at your applications and ask whether these large post-quantum signature sizes are gonna be a problem, in fact, look at post-quantum parameters of all characteristics. Will that be a problem in my application, is that something I'm concerned about where this size might break something, because now is the time to say something about that, probably getting too late to have other algorithms at this point, in fact, even building on Adi Shamir's comments on the Cryptographers' Panel, if you're putting these algorithms out, you've gotta have a lot of confidence in them, the ones that have survived the process so far are likely to be the choices. So think about whether that size impact is something that you could work with for upgrades. Secondly, if it is a concern, see whether using methods like condensation and reconstitution might fit into your protocol, do you have enough flexibility to be distributing signatures in parts and keeping track of things like signed reference values and updating them and so on? And then thirdly, if that's the case, for the long term, let's think about using things like Merkle tree ladder mode, maybe there are other ideas that can do this, but this idea of a mode of operation, standardize the signature scheme and then find ways of using it, one thing you'll notice if you look back in my description of condensation and reconstitution, there is no private key on that slide. No private key. The condensation and reconstitution operations are entirely public, therefore they don't affect the security proof 'cause the secure security proof is about interacting with the private key, adversary is already presumably able to do condensation and reconstitution. So those could be performed by anybody, which means that the ecosystem can help reduce the sizes, the signer produces the signatures, the ecosystem distributes them. If your ecosystem can do that, then your mode of operation can reduce the size overhead. And then finally, you've probably also considered, based on my description, that Merkle tree ladder mode is stateful. It's stateful, the signer's keeping track of how many things it signed in building the tree. And I wanna give you one final thought on this, even though it's stateful at this point, state is actually to your benefit, not a risk. A lot of times, we're hearing about stateful signatures and don't use the same state twice because you'll use the same one-time key pair twice, we've seen that in hash-based signatures. That's not what's happening here, if your underlying signature scheme is stateless like SPHINCS, which we were hearing about in the Cryptographers' Panel as well, then the only risk of reusing the same state twice is that you create additional targets that erode your security proof, but don't break it. So you reimagine the state, don't eliminate it in this case. And we can have some productive improvements on size that can help us get ready for post-quantum or whatever comes next. Thanks very much. (audience applauding) - [Host] If anyone has any questions. - [Mike] Hi, thanks, Burt. So I thought that was really interesting and probably very useful work too. So one thing I was wondering, could you optimize this further by stacking the signatures that are kind of for the most common DNS names in the right part of the tree so you don't have to go as far up or you don't have to request other rungs of the ladder? - [Burt] That's a very good question, Mike. So in the paper, we describe actually a slight generalization to what I've put here, where you can have more than one tree operating at the same time, we call it a tagged signature scheme in the literature. So you got your underlying signature scheme and then you build multiple trees. And those trees then could be optimized for these different purposes as you're describing, so good point. - [Host] Anyone else? - [Audience Member] So you've saved the space on how much you're sending. If I've signed something with, say, SPHINCS, which takes a very long time to validate, am I still, I am still, when I receive this, I'm doing that validation, yes, or am I just doing a small number of hashes? - [Burt] So it's a good question, and what's the practical impact? I described it in a very general way where every message gets signed and gets a full signature on the ladder that comes out at that point. In practice, as we've described in the paper, you would probably do some batching. So you take a collection of messages, form the tree or update the tree with that collection of messages, sign that once. And so it's that ladder that then becomes a reference value, so your reference values are more sparse. Then on the verifier's side, whenever the verifier needs to get a new reference value, the verifier verifies the SPHINCS or other signature on the new reference value and then holds that reference value for some additional verifications for some period of time. So what we're also able to achieve via this construction is reduce the computational overhead on signer and verifier. And Andy Fregly made a comment on one of the mailing list discussions as well, it reduces the total number of times that you need to use your underlying signature scheme. Now, this can be combined with an underlying signature scheme that is stateful and it's good to reduce the number of times you use your underlying stateful signature scheme because you have a maximum. But it also helps with SPHINCS+ because SPHINCS has an analysis that depends on the total number of times that SPHINCS+ is being used, even though it's not stateful. The security properties depend on the maximum number of signatures, and you can make it more efficient if you have a lower maximum. So for both these reasons, this mode of operation gives you a way of improving on the existing techniques. - [Host] Okay, that concludes our session. I'd like to thank everyone for coming down to RSA. (audience applauding) - [Burt] Thanks.