1.5-Time Signatures and More

Transcript

So, yeah, I'm going to talk about um one-time signature scheme, but actually the main result is a new few-time signature scheme. So, um the idea first um came when we looked at the one-time construction and we have stateful signatures in mind as well. And uh what is the problem when one-time signature is reused twice? And for standard Winternitz constructions, the the ones that are used in SPHINCS, even the ones that uh what's plus C, and but more or less standard, uh you get roughly 30 bits of security

after second reuse. This is very low. No one can rely on it in any sense, and um we were trying to look at uh what can be done better, and so there was some construction evolved from that. And then we thought actually that we may use those ones in constructing a few-time signature scheme. So, right now, most of the few-time signature schemes, which today and yesterday and last week, I think, is changing more and more into this uh construction that I'm going to talk about uh during this presentation. But uh before that, the few-time signature schemes mainly works that you have uh a single Merkle tree or couple Merkle trees that uh the leaves are just secret

values. Uh you take the message, you hash, and you get some indices you need to reveal. You reveal those indices, you reveal the authentication passes, and uh this is your few-time signature scheme. And to break it, you need to map to already revealed secret values. And those Yeah, AI is the authors. We need to ask. >> AI is >> The re- re- re- to answer questions.

But yes, so this few time signatures are actually pretty big and therefore SLH DSA it's more than 30%. And we have set of different proposals and new schemes arrive every day. So for example in this presentation I didn't compare the last one I've seen B plus minus C plus BFP which I think gets close to what we achieve here but with different um approaches but yeah. So but they all follow the same idea is like okay, I still have this Merkle trees, I still have this secret elements.

How we group them together, how we maybe we use different Merkle trees, maybe we do some grinding to group up the secret values so I can use the one authentication pass. But what we did we changed a way and we decided to use also we have a Merkle tree but instead of secret values there we have actually one time signatures. And this turned out to be actually really beneficial. So yeah, we build a few time signatures from many small one time signatures.

Again, just a quick reminder the Wots plus secret construction you have a certain you map your message through a hash function onto some nodes in the chains. You assign number to each position in the chain and Wots plus C requires you that the positions that you map to sum up to some constant number which gives you so called incomparable encoding but for example yeah, let's look at the two signatures. One is blue, the other one is red.

Um each of them sum up to four so this is our target sum but because we have now two signatures, there is one more signature that can be signed, which is 2 2 2. Yeah, it's a forgery. And the first question is actually, yeah, what is the probability after several reuses? And for a single uh what scheme, it's for what's plus C, it's actually not really great. But actually also the uh current Sig Golf leader is using a few time signature built not from the Hogwarts construction that I will present next slide, I think.

But actually just from plain what's plus C signatures. Uh so, uh yes. I think uh what what I want to Did I miss a slide? Pardon. Uh yeah. So, let's let's look at the construction. So, hidden group what's what we have. We have first Do I have a Yes, I have. So, we have several what's instances. Let's look.

Group one, uh group zero, group one, group two, group three. Each of them is its own what's plus C signature scheme with its own target sum. So, I if I map to this uh instance, I have uh the target sum. So, here, for example, I need uh the sum of these values be equal 34. This one is also 34. This one is also blah blah blah. So, this each of them is separate. Then, as a normal what's plus C, you compress the ends of the chains into a compressed public key.

But then, you don't stop there. You take a look at each of this group and uh think of the compressed public key of the what's instance as a start of a new chain. Here you have another chain, here another chain, another chain, another chain. And this can be also considered as a what's plus C instance with its own target sum. But the trick is also here. When you hash the message, you decide the digest decides for which parts you need to sign with this what's plus C instance

and for which you sign with the top chain. Does it make sense? I think this is probably the most interesting part of the talk is uh uh how it works and then I will just be showing numbers. Oh, this is good. >> [laughter] >> Uh so, yes. And uh why this is First of all, we can intuitively see why this is reuse more resistant because if I have a different digest then I may be asked to reveal the group that was hidden for my previous signature.

And there I don't know anything. And so, if I'm asked to sign with unrevealed group before that's secure friendly. If I have [snorts] the same revealed or hidden groups this has its own target sum, this has its own target sum. And so, you have so many requirements to fulfill that gives you much more reusable security. And I think uh if we take Hogwart's scheme, which is roughly 8 uh 100 bytes, after two signatures, I still have 80 bits of security, which I think quite a lot for a one-time signature scheme.

Uh so, yeah. This is the main idea of Hogwards. And then uh what you do uh Yeah, this is a bit more detailed. Yeah, you have these two constraints. First is inside the what's instance, you have to be uh upper in the chains than previously revealed signatures. Uh you need to be in the groups part. Uh yeah, and even if you map the same groups, you also need to satisfy there.

Um >> Why do you need the 12 steps? >> This is just an example because this example uses 12 this the chains of size 12. But, this is parameter. You can change. >> What what I mean is why 12 rather than one? >> No, uh >> Anything. >> So, the longer the chain I think the mhm No, it depends. You have the number of chains and the length of the chains that affect uh the probabilities that, for example, two random signatures they reveal certain positions.

And you can combine them together. You take the lower ones, and then the third random map will it be higher than everything that is revealed before. And if you have just a one step there is 100% probability that I will be the same or higher because there is no movement there. >> Uh I think the probability will depend uh which layer of the hyper tree you will you'll be targeting. The the forgery part. So, if you target the middle layer, then the probability is one kind if of forgery. If you target the higher layer, then the probability will be different.

>> It is true. I think for the proposal we are targeting uh the middle layer, and we also uh don't do grinding. We do a direct encoding. So, you you take the hash of the message and you uh encode it into the positions from the code list of incomparable encodings. >> That's actually another question related to grinding. So, if it if for example, you can grind the second if you do grind, then if you can can you grind the second signature to increase the to to decrease the forgery chance?

>> You >> To increase the security >> You could you could, I think, but we don't do grinding. But yeah, I think you could, yes. Because you can try to search for closer positions. I don't know how successful would you be and how much work you would need to for kind of each bit of security extra, but definitely this gives you something. >> It also depends maybe on which groups you will target or the groups are deterministic. >> Uh the revealed and unrevealed groups uh are derived from the hash. The digest tells you the number are fixed. So, you say each signature, for example in this example, has uh

three hidden groups and one revealed group. >> Mhm. >> But then the digest decides which group uh is revealed and which stay hidden. And for example, for the top here, if uh I would uh say now this is hidden, but this is revealed, then I would uh sum the positions from the first chain uh third chain and the fourth chain. So, this uh Yeah. >> In intuitively, it would mean maybe that uh if the second signature targets the same groups, >> Yes.

>> then the the forgery the the security will be higher. Because it will be bigger chance that uh the adversary attempts will miss these groups. >> Uh but yeah, this is this is kind of the idea is that yeah, you either have you you have to match the already revealed groups. And then within those groups you also have to match the chain the revealed chain values. Uh Next.

So, yeah, this is a little bit more formally if we want to look after uh R reveals we have uh hidden sets. We had uh the code words. For each code word we can look at A I think A R I is the most uh the lowest revealed value. B R is the uh most revealed values in the hidden groups. And so, when you uh compute a new random digest uh it must match uh the subset of hidden groups that they they should stay hidden across all of

the history. And then each position must uh be higher than the revealed ones. And then you can compute it. And then for one signature it's exactly one over the code word. But if you have more signatures you can just more precisely compute it. And yeah, this is also partially what I already uh covered is that yeah, previous constructions you have these uh uh trees of secret values. Now you have just uh small instances at the bottom.

Uh and I think uh we can go to numbers, which is the interesting part. So, four I think this is uh yeah, a few time signature. I want eight reuses, still have 128 bits of security. Uh the this is what we have. We have forest plus FP gives you 2,000 bytes. B forest plus FP 1.8. VCT is this construction where we just use plain what's plus C and then Hogwarts gives you the smallest signature here.

But the the downside is our verification here grows, yeah? From uh as for example here 150, we get 324. This is also some price that you you have to pay here. Uh when I talk about security, we don't have security proof yet, no lean, no pen and paper one, but it's pretty No, no, I don't want to say Yeah, obvious, but uh there is nothing happens here that is Yeah.

>> Your plan is to replace these things for the What sort of >> This is This is with few times signature. >> So, here we want to replace force with this. >> Yes. >> But and you leave like 2 to the 80 or or or for use or what? Because you said that if you use twice or you you >> But the thing is Well, here I can clarify a lit- Uh I can clarify here a little bit is that when I make a few times signature scheme, I have now I'm selecting several uh Hogwarts instances and I need to sign with each of them.

And because now I have let's say K uh Hogwarts instances, each of them give me a certain reuse probability, da da da, and they all all together give me 128 or even more security margin. >> Got it. Thank you. >> So, yeah, you're selecting a subset. You again build a Merkle tree. Each of them is a uh Hogwarts instance. You select a subset and then yeah, this this how it works. Uh yeah, so this is for uh standalone.

Uh then we have our own uh metric a little bit, so we we don't yet 100% sure what limitations we want for Bitcoin, but one of the metrics was uh uh the verification computations per byte. So, we have Schnorr signatures, they we map their computations to hash computations, and we can count roughly what would be per byte uh the amount of computations, and so for example, we have this fraction 0.49 computation per byte, and let's use that as a upper bound for what what we want

to achieve. And then uh for a budget of 2 to the 40 signatures, this what we can also get. It's uh 3.8 kilobytes, and then uh yeah, this key gen signing the signing is uh uh 2 to the 21, which for example breaks the Sig Golf uh requirement, it it goes uh too far. But uh yeah, this gives us so far, I think, with these restrictions the smallest signatures. Uh I think again this uh uh BPSS minus C plus BP FP thing is really close to that, but uh I think still beats

roughly 60 bytes or something like this. Uh so yeah, here uh the main win comes again from the uh few time signature construction, so here we exactly win, but uh we also adjusted in this comparison on the previous slide, we adjusted internal one-time signature schemes, because here you have uh uh very few verification, so I could spend more verification on internal one-time signatures for B plus Paul post plus FP, but here I spend more verification, so I have less to spend for verification, so I had to change a little bit internal one-time signature, so this is

not a one-to-one translation, but yeah, this is under under this restrictions. Uh one very important, I think point that we first overlooked is the Uh how the security degrades because what I showed this expectation, this is the expectation, but now the variance is different, so here we see how Uh Sphinx plus is the red line.

How if you get unlucky with your distribution of selected nodes, how the security degrades. So, for example, if you 2 to the minus 24 unlucky, you still get 128 bits of security. But if you are 2 to the minus 24 unlucky with Hogwarts, you lost eight bits below your margin. But the good part is it costs less than 20 bytes. We just start higher and then we will have a good margin, but these things I think often overseen because you it is fair. In expectation, I have 128

bits of security, but these shapes of what happens with the variance is also very important. So, yeah, this is curves for 2 to the 40 budget and this for uh 2 to the 64. For example, for 2 to the 64, I'm very happy with with the curve. It only goes below 128 bits with if you are unlucky with 2 to the minus 64 probability. It's fine. Um Yes.

So, what we have, we have Hogwards, this new hidden group, Winternitz one-time signature scheme. If you look at it as on its own, this has a better reuse security uh then we achieve smaller signatures in general. This usually gives you some payment in terms of verification cost. Uh yeah, I also again wanted to highlight because so far I'm doing some comparison, but I didn't read the paper enough.

This new ePrint paper gives you very similar sizes. For example, uh if we want to spend the Hogwards budget, we only win I think 16 bytes under our restrictions. But if we want Biposto budget, they win the size little bit so it looks like they're very close, but I'm not ready right now to give a proper comparison but you have to be aware there is something similar going on.

And I have uh Well well today I think I wanted to prepare also because Seagull targets 2 to the 32 signatures. And um what I can have for example, uh here I have a comparison with current Seagull leader. I can have uh the signature size of 3 uh kilobytes, but then I again uh run over the limit because Seagull gives you 2 to the 17 limit. Here I go beyond that.

Uh but the size times compressions they improve here. Also, what hasn't landed on the slide yet, but this is also uh a little bit uh uh empirical expectation, I think. What will happen is I can also have a Hogwarts-based scheme, which will go bigger in size. It will have 6.5, I think, kilobytes, but it will be actually cheaper to verify.

I'm not sure what what's what's going on there, but Flo tells me it beats the Siguls. I'm investigating in these hours. Uh yeah, so and I think this is a really nice In general, this is the new idea that came is like, "Yeah, let's build few time signatures from the one-time signatures." This is the current leader on the Sigulf, and I think this is a very promising uh direction.

Yeah, I think that's mainly it. >> [applause] >> Yeah, um I actually think we should um accept lower um work factors for um with low probability. Because if you think about um AES-128, for example, um inherently 128-bit key block cipher, um if you do uh so with probability um uh

2 to the minus K, you lose um K bits of work. So, if with probability 2 to the minus um 64, you can find the key in 2 to the 64 work. So, we should accept that um probability curve also for signatures. >> I also thought about to properly compare um what we already have in the normal cases and what what we are dealing with what we're dealing here. Uh I didn't do this comparison. I also had in mind maybe this curve is actually fine.

But >> it's too conservative. >> Yes, I it may be. It's just the problem is we don't have all the decisions and conclusions ready. It's pretty much very right now hot work in progress. The security prove that maybe some modifications. The parameter search, for example, also I I I search for today. For example, if you say the Sphinx plus budget uh 2 to the 64, everything um signing budget for Sphinx plus. And I say, "Okay, I don't want to exceed uh the numbers of Sphinx plus more than twice."

I think uh Let me quickly check. I think I got 3.5 kilobytes for not to lie about uh for the full 2 to the 64 signatures. Let me see. Okay, we can continue while it starts back, but uh yeah. Uh so, there is uh a lot of work in terms of search for parameters. Think about actually what what are your restrictions. Because also, for example, 2 to the 17 signing budget.

Maybe 2 to the 18 signing is also fine. What can I get there for? It's it is very difficult because you have a lot of so many things to tweak, and then they they change slightly. But yeah, this may be maybe this is actually fine. I agree. >> Yeah, that this is why I think bits of security is considered harmful. Um you cannot um specify the desired security level just using one bit figure. >> One number, yeah, yeah, exactly. >> Hi, so um >> [clears throat]

>> I don't know if it's actually the case, but my intuition says it's that these kinds of few times signatures are a bit less MPC-friendly because you have sequential >> have more Yeah, yeah, yeah. Chains. Here you had just a single secret. Now you have this Yeah, yeah. I I I would expect this to be also less MPC-friendly. Yes. >> Yeah, yeah, yeah. I was wondering if you if you've looked into that and how much how bad or how negligible is >> We we have not looked yet into this, but maybe we will try to to to spend some time on that as well.

>> This is one thing we're considering for the next version of Sig Golf to have some constraints on the depth of the the the DAG for MPC. >> I I'm just wondering, have you have you got a formula for the reuse security for the scheme? >> Uh yes, but it's complex and it's not on the slides, I think. This is formal. >> [laughter] >> But but I mean like an explicit formula that you can use in a for a specific instance.

>> Yes, yeah, I mean it it it is uh uh it is uh pretty straightforward. So, for example, when you when I have uh single uh Hogwarts instance I can compute uh the probability expected probability of uh random hash mapping into known values given a history of three other random signatures.

And then, when you scale it to revealing uh uh K instances in a subset, you [clears throat] can compute the expected probability on how many times the same signature will be used. And then you use the expected usage with the expected forgery bound. So, here this CU of X is the expected forgery of Hogwarts under X three usages. Uh and then we sample X from uh binomial distribution after a R signatures with probability cow cow over N you get this signature. So, how many times do I

get this instance selected? And then you do it to the power of K because you need forge K. >> Is it like a Monte Carlo simulation you're doing? >> Okay. But but uh do you have any sort of rigorous um numbers for your security bits that are not simulation? >> I think yes. I think so, but it it is a this one assumes just everything random and ideal. And I think for that we have scripts, but uh I don't have them. Just >> Okay. Cuz I mean depending on the >> them, but I I can >> Yeah, yeah, yeah. And basically like the depending on the few time signature, those formulas can like for four there's

a very simple expression for its reuse security. As you make the few time signature more complex, then the >> I think it Yeah, it it it it it becomes slightly more complex, but not crazy more complex. >> Yeah, you can find a closed form formula that is um only slightly conservative relative to the um the exact formula. >> Okay, like a rigorous formula. >> Yes. >> And like computable for a specific instance?

>> Yes. >> Yeah, yes, yes, yes. >> Oh, for >> I I don't know. I would have to work that out, but I I I claim that this is possible. Um I'm 90% sure, but I would have to do the work. >> But like it's quite good. It could get very complicated to come up with that. >> I Okay. So so if you if you just want a formula that is simple to compute then you can just sort of you can define a curve by interpolation and then prove in lean that that curve is always below the real one.

And then you it's still easy to compute for everyone who's using the the function. >> I think in this particular case you can compute the exact values just recursively. Just >> I think it's also I can I can also give you some intuition. What is the most difficult part here is what is the probability of the forgery of a single Hogwarts instance after I've seen for that instance our signatures. And exactly for example here this is the what's plus C example. Yeah?

After two signatures what is the the the revealed essentially subset of signatures now I can sign. This is computable. It's not super easy formula because we have this target sum thing and you need to to adjust for that, but essentially this is computable. And then plugging into few times signature schemes is actually easy because the only things comes from doing it in the multi multi few times signature construction is how many times my instance will be selected. And this doesn't change whether the the instance is a single secret value a

what's plus C instance, Hogwarts instance, or whatever thing you want to put there. The number of selections will stay the same as in the force analysis. >> Thank you so much Mihai. We're we're at time. Great presentation. >> [snorts] [applause]