Post-Quantum Cryptography: PQ Signatures

Transcript

Shall I start? Yep. Yep. Okay. Uh hello everyone. Sorry I can't be there at the beam day. Unfortunately, I had some complications due to my recent bronitis. But um hope that my presentation will be informative enough. So please tell me immediately if there is any connection problem otherwise I'll proceed. So this is um kind of little technical talk about postquantum signatures for the beam chain. This is a joint work with Justin with Mike Codinf and Benedict Wagner. Benedict also from the cryptography team. So um I'll try to make it less technical but still interesting enough participants. So basically how we started we needed a

simple signature scheme uh which is would be easy to uh implement to test to analyze. We need the minimum number of hardness assumptions I mean cryptographic hardness assumptions. I mean the assumptions that are necessary to prove the security of the scheme. We need the scheme to be resistant to quantum attack. Uh the signature should be of reasonably small size. Well, we know that for um postquantum signatures they cannot be like super small but still reasonably small. We need that they are passed to sign and to verify because all this is under the pressure of um slot timing and we need those signatures to be aggregation friendly because we don't

plan to have them all in the in the in the blockchain but uh we uh have to have uh some aggregation of the signatures because there are like many validators for slot and having all the signatures in the plain text is just would consume too much bandwidth and to this requirements we have come up with a simple solution shortly. It's called XMss. It's a hashbased signature scheme and its advantage that it uses just um a collision and primage resistant hash function. Nothing more. As long as this hash function is uh u resistant to collision primitive attacks and to quantum attacks as well means that the hash is not based on any

for example curve machinery then this scheme is plausibly postquantum secure. Uh it's also of reasonably small size. It's between two and three kilobytes uh depending on on the parameters. We have some trade-off between verification time and signature size. It's reasonably fast and sign to verify really fast. It just takes milliseconds to to sign and to verify and it's aggregation friendly. By aggregation I mean that not it doesn't have any internal algebraic structure to make it aggregation friendly but we can aggregate it to prove the knowledge of sufficient number of signatures. And to give you some concrete numbers, in order to prove the knowledge of a thousand signatures, it's equivalent to prove

just little more than 10,000 Poseidon hashes. And we know that uh the signatures 10,000 PID hashes can be proven in reasonably small time. This will be covered in the next talks. And now I will try to explain how the signatures work. So I'll start with a toy example. In this toy example, uh I first explained how keys are generated. So in order to generate uh public key we create five secret inputs. So this five is just the toy example number and in practice it will be a little bigger. So here the ones are S1, S2, S3, S4, S5.

They are at row four. These are so-called chain uh beginnings. Then we hash each of those four times like one two three four reaching uh level zero. this and this form a chain and then the resulting hash outputs we hash them again with like little bigger hash and we get a public key and that's it. So that's the key generation and now how to sign and what can be signed in this to example scheme. In this example scheme, we sign uh messages and these messages are five tpples meaning like there are five numbers and each number are between zero and four integers. Uh but not all

combinations are possible. Not all five to the five combinations are possible but only those whose sum is eight. Uh what that means? Uh here is an example. For example, we can sign a we can sign the message consisting of five numbers 1 320. It's easy to see that they sum to eight and then uh so this 1320 they uh give us the positions in this chain means like here at level one here at level three here at level two at level zero at level two. The actual signature is the array of values not the positions but of values. So this hash outputs

again like uh since we have five so-called chains the signature is composed of five hash values. Um and uh with this scheme we can sign several messages. For example, we can also sign the message which consists of again five numbers but now they are four 004 like here. And then again I would have this five orange uh um balls are signature values are they form a signature. In order to verify this signature, it's enough to hash all the chains till their end. And it's easy to

see that since the sum of positions is eight, then for every message, we have to apply the hash exactly eight times. So now then we get um chain ends uh and then we hash them again and check if they match the public key. It's also easy to see that u from any actual signature you cannot modify it to get a signature for another message whose sum of positions is also eight because in one of chain uh you would have to kind of step back in the hash chain to find the primage the hash which is impossible.

So for in this toy example since we have only five chains and uh five and each chain has five entries we can only sign 320 messages uh with the sum requirement of eight. But if we modify this a little bit and this is actually very close to the construction we have then uh for 64 chains of length 8 and if we require that the sum of positions is 76 then we can sign almost exactly 2 to the 128 messages. Well little more actually because we need this little bigger number for security proofs but around that and this actually give us 128 bits of security. So the actual scheme will

be very close to this. will have 64 chains meaning that the actual signature will be uh the actual signature will be will consist of 64 values. So that was a one-time signature and for how to convert it to multiple time signature that's actually very easy because in this particular BM chain application we know that uh each validator signs for a particular slot and uh all the signatures are enumerated for one slot there can be only one signature and then uh it's relatively easy to have uh multiple signatures from one what we do we actually just create a one-time

signature for every slot. If we have like 2 to the 32 or 2 to the 24 slots we create appropriate number of one time signature and then we make a one public key out of them by just making up a miracle tree out of all them. This means that in order to verify a signature, a one-time signature, it's uh enough to verify it up until the leaf in the tree and then we need another Merkel proof part to verify it up to the very end of the public key and this part can actually be amvertised in practice.

So this is uh done and how actual signatures are generated. So suppose a validator wants to assign a block B at some slot number V. Then we it hashes it B and V and get positions uh from W1 to W to W64 positions on this uh chain structure which we also call hyper cube and uh these positions they determine uh which uh signature which values have to be provided. to how uh validator makes them up. It recalls basically how uh the chain beginnings were generated. It

iterates up to the orange positions and it outputs them as a signature. So 64 values uh 64 chain uh values are signature uh well plus the Merkel tree part up above. In order to verify the signature again you just have to compute the hash. you have to compute the hash chains um up until the ends and then to the Merkel route. In order to do this, you just have to compute about 136 Poseidon hashes and that's it. Uh well, this number 136, it varies a little bit if you need uh many more slots. But if you just double the number of slots,

number of hashes as in the Merkel tree proof increased by just one. And uh in order to aggregate this in order to prove the existence of signature you just uh put all the signature verification process into the circuit. Basically uh what you do is uh to prove the existence of a signature you hash block and slot number and uh you get the positions and then the signature exists if there exists uh chain entries from chain one to chain 64 such that if you hash them till the end appropriate number of times and this number of times is determined by the hash of block and slot number and then

there exists a miracle proof till the end then that means that the signature exists and that's it basically um the theoretical part behind this constructions is in two papers that I just published u on print on this links uh they don't contain the full uh scheme that will be actually used it will be in the final report which is just to be finalized we kind of wrapping up with uh some security proofs and some kind of parameters. Based on this uh it will be published very soon. Based on this we'll write a spec uh which will uh be good enough to make a code out of this. Uh

that's it. Uh thank you. Are there questions? Thank you. Right. Any questions on them? What were the other choices in uh designs and why did we choose this one as opposed to? So the question is what were the choices when designing uh postquantum signatures and why was the hashbased construction selected? Right. So we of course are aware of a number of postquantum constructions particularly latest based. So uh what we and that we're afraid of is that uh while the analysis of latest based

schemes still continues there are a lot of uh discussions about security uh of this scheme how to interpret the security. Um also what we do like is that we really have a smallest number of hardness assumptions particular just the security of a hash function since we already have to have a secure hash function then it means that we can get a secure signature scheme uh without any additional assumption. So if we use a latest based scheme that we need to assume something uh latest specific as a hardness assumption if we just use a secure hash uh we don't need anything else and uh also uh the hashb signature

scheme is much easier to verify in uh in circuits because it's kind of the domain is better suited uh to the domain where uh proof systems are built. Uh well of course Latus schemes are are still competitive and we think that it's a viable alternative but simplicity of this scheme and its minimal requirements and the the ease of implementation I think give it a little advantage. That's it. Um, how often do you think we should rotate the public keys and how uh big are they to sort?

How often should we rotate the public keys and how big are they? Yeah. Uh, so for multiple uh multiple signatures uh number of public key determines how big the miracle tree is. So I think we can support up to so 2 to the 24 uh slots is supported easily. I think we can even support to the 32 slots which should be sufficient for all the practical purposes. Well this will make the key generation a little more expensive maybe several days uh because you have to basically calculate all these hashes. It means that two to the 32 times you have to calculate all these

I don't know 500 chains 500 uh hash calls or something. So in total yeah hundreds of of billion hashes which is feasible but takes some hours but overall I think it's it's possible. So for like of course there can be some aggressive variants where you have like really small tree and you rotate the keys pretty often but I think we can avoid it. So maybe we should aim for for bigger trees but to maybe cache this part the upper part in some smart way to reuse it in proofs and in other parts because actually that the outer part is not confidential at all in contrast to this uh blue things uh below. So any

number between 2 to 24 and 2 to 32 which is required I think we can support. So one of the strategies that we've taken recently is to introduce two different concepts. There's the concept of a maximum lifetime which is for example 2 to the 32 slots which would be a century even if we have 1 second slots. Um and then there's the actual lifetime that you would generate practically speaking as a validator. And here what we would recommend to the clients is maybe only generate eight years of lifetime which is 2 to the 24 keys and that would take about three hours on your laptop.

But yeah, if you want to generate 100 years of lifetime then that's up to you to just spend more time on on the key generation. Yeah, small technical question is just so you when you hash the block in the slop, how do you make sure that that maps to one of these particular arrays that uh that you you need? I didn't know I missed that part. Yeah, great question. So the question is uh when you're hashing the message and the slot, how do you make sure that you have the target sum?

Right. So what we actually have here so we uh we hash the block and slot into some kind of long string. Then we convert this long string into an integer and this integer we well simply saying we take it modulo the number of uh possible output positions. So here like how many positions so that they sum to 76 onto 64 chains exist there are about 2 to the 128 2 to the 135 or something.

Uh so we know this number this is just comtorical thing. So we take hash model to something basically and then we uh take based on the result we figure out in which position we are by kind of applying again recursively combinatorial things. So it's basically the question how to generate all the uh all the there's some grinding right if the grinding the grinding allows us to hit the target some uh ah well yes and no so we we we can do this with grinding but grinding allows us to use

like target sound which is little smaller than uh than needed but I think it's to explain this we don't have to talk about grinding so Right here we uh we just can map uh a big integer into the uh into the position. So it's the question of enumerating all arrays of integers whose sum is equal to some constant and this is combinatorial thing how to generate all possible enumerations and in the in our second paper there is exact algorithm that does that. It's a kind of simple combinatorial thing. A few decisions, model reductions and and that's it.

There is indeed little grinding over it, but I think it's not required to uh explain how we do mapping. Okay, one last question. Why do you need to generate all the positions? Why not just the one that represents your integer? I didn't understand. Uh no I meant uh that uh in order to convert a big integer into the positions uh we need the algorithm to that maps one to one and this algorithm is sort of similar to the algorithm that generates all possible positions. Uh the actual algorithm that maps is like well for example if you have like a big integer

how do you write it based base 10 or base 16 or base 5 you do some model reduction subtractions divisions model reduction subtraction divisions here it's about the same just little more sophisticated because uh of this structure of this hyper cube but principle is about the same thank you so much thank Thank you Justin. Next up we have Emil who will talk about uh recursive aggregation.