ZK12: Skyscraper : Super Fast Hash for Big Primes - Katharina Koschatko

Transcript

[Music] good so um what I'm going to talk about it's a Hesh function a new one that we designed uh it's called skyscraper super fast Hesh for big primes so who worked together with me on that or is still working with me um it's Clos the audience marus in the audience and then Loren Loreno Fabian Christian Dimitri and that's it good um so super fast hash for big primes what do I mean by that um maybe start right into so big primes I mean big in a sense of 254 bits or a

little more um and super fast I mean nearly as fast as Sha or as good as Sha three or competitive to 64-bit um hash functions um so um in this figure you see like a comparison for or if you wanted to compress so 2:1 compression of around 500 bits and um there are different methods one could say that you could apply so one idea is to just take some hash function that works over 64 bits like posidon or monolith and yeah then make the state large enough so you get enough bits in there um so you see that here monolith is pretty fast already there um and yes

um if I now want wanted to use big Prime Fields like 254 bits um the situation is a little different so you can't use this fast monolith thing because it's only defined for 64 bits so there are other H functions where you can just plug in the large frames uh like posidon or posidon 2 but they're way slower for large field so it's the blue uh line here um and there's also um a hash function which was just designed for big primes it's reinforced concrete but um it's still pretty slow in comparison into fast ones um so what was our goal now our goal was to design a hash function this fast like fast in comparison to sha three or sha and which works about big primes and

these are our results here so it's called skyscraper and as you can see for large primes it's around 100 times faster than um using posidon with a big Prime um comparing this whole thing um in terms of sha 256 so let's say sha 256 is the Baseline it's one fast um and if we wanted to um hash like longer messages say 500 bits or um even longer messages like uh 10k of bits so 20 times more um then we see that um in okay here um we are comparable uh to monolith here so we are only 2.8 times

slower than sh to 56 which is pretty fast um and um yeah also for longer messages we do not scale as good as um for example monolith which works for 64-bit or posidon um but still it's it's comp um yeah comparable uh we also suggest a different setting for which um going to longer messages um scales better so now you might have some questions on why we want this why we use this why another hash function we already have so many of them um so first point why a new hash function we already have shot shot to 56 um so the point is and you might know that that we need the

different sort of hash functions if we want to use it in um CK so we need a hash function that can be represented in in an arithmetic circuit and those hash functions are called arithmetization oriented or arithmetization friendly hash functions or ck friendly sometimes um good um so this is the one thing but there are already a lot of hash functions um that are CK friendly so why another one and the answer is simple we need one for large primes so there is already one for large primes but it's not good enough and um there are several CK protocols where we need really need large primes so if you think about protocols that are based on um elliptic

curve pairings and they inherently use those big primes like 2054 bits this PN 25 uh 254 um so um hashing over big primes is good um so just some application I guess most of you know better than I do more a crypt analysis person um but um a very typical application is a set membership proofs um in Merkle 3es or a provable Randomness um where you basically have some non um non- interactive proof and you have some um Randomness created and you want to prove that the derivation of the randomness was correctly was done correctly and many more use

cases so how do we now get to to this goal of having a performant hash function over a Big Field how do we get there um and um also um another thing we thought about was okay somehow all those designs exist already um are pretty complicated so they have for example the states and you have various State sizes and you need to kind of choose the state size um appropriately then you have maybe um full rounds partial rounds and there are many par parameters right um so it's hard to to analyze the security of those ciphers or of those um

permutations um so one idea was or one goal for us was make it simple so it's easier to analyze and the last point we wanted to achieve is just use lookup tables they fast um yeah but this restricts a little bit the where our H function can be applied so we need lookup based Pro systems so how do we get there um first point forget about SPN and use fil so um I guess you are familiar with SPN construction so substitution permutation networks basically um all the hater based design are a bit like that um so you have some round consent additions you have some nonlinear substitutions and then you

have some diffusions matrix multiplication basically um on the other hand um in the fisel construction in the normal feisel one you just have two inputs and you have a f round functions you apply the round function um add the other branch and then twist um here the big Advantage is that we are getting rid of the of the linear layer here and the linear layer is quite costly if it comes to large State sizes or um to to many rounds that one might have um so it's good to not have a linear layer and the good thing about the feistel is that the diffusion comes by construction with the feistel so what round functions do we

use then um we have uh s boxes similar to the ones in monolit if you know it but we get to it later and we use Square Rings um what is important important now is um that the squaring over the finite field is not um not a bjective function so you can't invert it but we do not care because we using a Fel construction um and the second thing is um that the the S boox we're using is also not invertible again we don't care use a f um to make the whole thing still a little faster we using the monom trick you might know it from tip five already um yes so it's basically just a monom

multiplication and um the last thing is for the lookup so for this sbox um it's pretty simple so we just split the whole state let's say 256 bit or 254 bits in eight bits if it just doesn't fit we have two empty bits at the beginning um then we do some rearranging so in particular it's some circular shift um then we apply some nonlinear 8bit s box basically which can be implemented efficiently in Hardware just with some bit shifts and then we recompose the whole thing what's important now is um for the recomposition it might be that the result is not um in the finite field um but we can just do module P because we don't care about

invertibility good um so the whole picture is like this so basically we um have this skyscraper of blocks that's why the name skyscraper um so um we alternate um squar rings and Spar functions so for the square operation um again it's two consecutive squarings um with this non inable x square um which has good statistical property and we speed up VI Montgomery for the bars operation um again non invertible um this uh split or decompose and uh lookup approach has a high jebra Dee degree and um should does be pretty good against um algebraic

attacks and we speed the whole thing of why efficient operations in the small s boxes basically good um so now I said in the feisel construction we only have two inputs so what if I wanted to to use more inputs what if I want to use it in a sponge then I have like raid one capacity one doesn't sound so good so what can I do and as I said we wanted to keep the construction simple so we don't want to use a larger state so the idea is maybe you don't think it's simple but the idea is we switch to the extension Fields so the construction with the F stays just the same but instead of having field elements as inputs we use

extension field elements um just a quick reminder what is an extension field so if you have FP to the^ of n it's nothing else than a polinomial with n coefficients so n coefficients in the finite field FP and um that's an element of the extension field if you want to add to two elements of the extension field you just do a polinomial addition and for multiplying you first do polinomial multiplication and then you need to do a reduction modul of some irreducible polinomial and depending on how you choose this polinomial it might be more efficient in implementation so there are some faults in there as well good um so um basically by using those extension Fields one could now say

we kind of simulate a larger state so if we have FP to the^ of two um then instead of having uh two elements for the inputs of the feisel we have four um on the right side there are just some very quick um comparisons for the runtime so in NCS so for one bar or with mulate field we um have eight NCS and for the bar over fp2 uh we have 12 NCS so now we here we see um in this case we operate on two elements at the same time so um basically it's more efficient than having just two bars um on the other hand for um the squaring it looks like as if it was less

efficient to work of extension field but what's um important to mention here is that you cannot just um do the squarings and afterwards not mix up anything up so if you have more elements like a larger state after the squarings you would still need to mix it then you would need again an MDS Matrix and then use lower again so we have some tests done in this direction but I will spare you with the details there good um so for the um bar design for this sbox component how does this work now um I just use a very simple example 15 bit and I want to split in 2 * 8 Bits And um so um if we have the normal finite field just FP how does it

work um we just split this number can you see the cursor yes perfect so we just split this um number into two 8bit elements then we apply this circular shift and then we apply the sbox or this small 8bit SBX recompose so in this case we see that the the result that we get so just taking this D3 um Ser e is not a field any element anymore because it's larger larger or equal to P so we can just do modum and then we're in the field again how does it work for the first extension so for fp2 basically the same thing now we have our Pol with the two coefficients and we take the

coefficients and um do the splits again so the decompositions in each eight bits then we do the circular shift and now the important thing is we do the circular shift over the whole state basically so we are not only having this um nonlinear T's in here but we also mix um um Parts um from the first um coefficient with parts of the second coefficients so it's another mixing down here another day of mixing basically um yeah then apply the nonlinear uh T and uh recompose so recomposing is again the first two eight bits go into the first coefficient and the second two times 8 Bits go in the second coefficient um in

this case we did not need to do any modular ruction afterwards and very very similar for the logic case so for three um I think it's not necessary to go through the details but just you see how the mixing goes in here so doing this circular shift basically um this one um component has basically inputs from both the the orange one and the blue one um here the middle ones has inputs from there basically and the last two ones from those two good so um we talked about plane performance we talked about how does

this thing look like why do we do what we do but what about the proof system well is it good is it bad um and the answer is it's pretty good so um the the thing is um that with our construction we do not need any um matrices so there is already a point where we get getting more efficient for the proof systems then another point is that we only have squarings so we don't need those power maps that might be large like um to the power of five or to the power of seven or whatsoever such that we have a permutation over to finite field um so we only have squarings there and um for the bar those are a little more expensive but we don't have too many um

lookups there um so overall it um we get good results for the comparison so how do we compare it we um for plish performance We compare the um a degree product with the native performance in nanc here um and we see that for um performance this xcess we already more or less saw so for performance um we were pretty good um and for um proof system size we are comparable to posidon yes good so um conclusion we build a new hash function it's called skyscraper um

it's efficient in plane and in a proof system for large PRS uh the plane performance is even comparable to sha three um what's new is that we use the fistal design strategy instead of the normal SPN strategy um this strategy allow us to use non-invertible components which was not the case before um we were able um like this to remove the fine layer and still get good diffusion um and hopefully have a simple design that people like keep in mind and don't have to think about too much like where to adjust what to get what we want um and the last point is the generic bar construction which is very important um

because this allows us to fix the construction not only to this BN 254 for which we implemented already but in general it could be applied to any Prime so we do not need like in monolith or um in reinforced concrete um we do not need a specific Prime and then it only works the construction only works for the specific Prime but it can be applied to any Prime um and due to this construction the generic bar construction with the decomposition if you remember the mixing and the nonlinear um sboxes we get a high arobic degree so this was skyscraper super fast hash for big price I hope you like it yes thank you Katherine we have time

for a couple questions yes so how does the arithmetization look it seemed you had some kind of decomposition of the digits of coefficient of uh yeah blue and green num so in the in the proof system how we doing this yes so so basically there are different paths We are following right now so we're not completely done um this one we used here in the comparison is a pretty um simple basically that you have um one witness for every uh chunk here basically and um then you you prove the mapping St um but we are thinking about

different ways to do this but we're still in the process so question this might be a stupid one so I'm sorry umine in advance are you thinking about um Quantum cryptography at all or Quantum threats like it it would seem that anyone building a new hash function would have to think about that um is that has that been part of your design process or um not necessarily but since we're like typically so this idea for the design is to work over the super large fields and um the the the real threat we would have there would actually um not be of the breaking mathematics side but just

increase the prime size basically so you're saying it's it's add secure as current hash functions against a Quantum threat I would say yes okay because every hash function is now kind of thinking about this right like bitco yeah okay no it's it's a valid question yes but I I personally think that this should not be a problem in this case because we're working with such large primes in that uh you said you had to take model Prime in this Step In The End and doesn't this introduce a bias in the output uh we we looked at this so so first thing it definitely reduces

reduces the the image size so this is one point we had different options there um so we we also tested um instead of doing modulo we tested truncations in their most significant part and rotations and um it appears that during the modular the bias is not high so it's it's bad for circular shifts in the most significant bit so there are operations that introduce a high bias um but for this operation we should be safe one so two questions so how many rounds do you have and how did you choose the

number of rounds uh we have 10 and um so so basically having like a lower bound on number of rounds was more from okay how many squarings do we need to get like good statistical properties and then we said okay um do we already have enough for algebraic security um we did a lot of uh modeling there and um So currently at least from the AL Crypt analysis perspective uh we should have around I think 400 bits of security and but we are aiming for 128 but jaic security is always like a difficult question depending on the model and depending on the approach and but yeah

so so basically for what we're looking uh 10 of both or 10 together like 10 overalls it's 10 F rounds um it's um three blocks of those double squar rings and two blocks of those Double B so overall it's one so one two 3 four five six squar rings and one two uh three four of those large lookups the other question you mentioned that the sbox is not invertible which one reason is the Modo but is it also it was not clear if the 8bit uh sbox is that also non invertible uh the 8bit um sbox is invertible so we are using the the same one that they used in in monolit is

this a GS box yes all right I think that's all for the questions right great okay thank you thank you Karina thank you