ZK14 - Resource-Sharing Permutations for Computational Integrity - Fabian Schmid (TU Graz)

Transcript

All right. Thank you very much for those who still stayed here on the side stage for this last talk. So, I'm going to talk about SpinX, which is our new hash function that we're currently working on. And I think the subtitle resource sharing permutations for computational integrity is a bit of a historic artifact but across the talk I will go a bit into where this comes from. All right, a little bit of background. Um so, we've heard a lot about CK proof systems today. We've heard a lot about different applications and yeah, higher levels and I really go back down to the primitive level talking about CK friendly hash functions. So, very short motivation for those

who are here pretty obvious probably, but why do we need hash functions um in the context of CK? Well, we use them in Merkle trees where we have um large commitments to to inputs. We use them in the future mere transform um basically turning interactive protocols into non-interactive proofs. And then, of course, for hash-based proof systems, we do need um these hash functions in there. And more precisely, if we then also want to do recursion, then we also need a way to efficiently prove hash function evaluations. So, I think it's quite uh obvious why we need

hash functions. And a bit historically again, um this is again just some implementation um where different hash functions are implemented in Circom, but we see really when we try to build R1CS constraints of course, there are papers that do that more efficiently now, but I think it just gives you a high level if you intuitively implement uh proof system friendly hash function like Poseidon 2, you will just achieve much much lower constraint counts. Um and ultimately the goal is really when designing such a hash function to minimize the multiplicative complexity uh while maintaining security. So, what what does it mean? Why is it the case

that these hash functions are so slow? It's not that they were designed so badly, but rather that they were all defined in uh the binary field or binary extension field usually, and these bitwise operations need to be emulated on the prime field level that these proof systems usually operate on. And when we define our um hash functions directly in the algebraic context, of course, we will achieve much higher performance. So, um let's start with BNX, uh which basically goes into leveraging the NTT hardware structure to achieve efficient hashing.

And uh essentially and that's where also the title came from, is the idea that in modern uh cryptographic processors dedicated for CK evaluation, we usually have quite a large area usage dedicated to the NTT evaluation. We find the NTT evaluation in hash-based signatures, but also in homomorphic encryption. So, NTT is really a useful tool, in essence, a tool that maps a polynomial from the um coefficient space in the into the evaluation domain.

And then if we look at the chips now, we have this large area for the NTT and then usually have a separate somewhat large area for the hash function. Can we build a hash function that not only reduces the multiplicative complexity, but also reuses the structure of the NTT to really deliberately reuse the area in the hardware? However, of course, the NTT alone is only a linear and if you've ever dealt with these algebraic hash functions, similar to a neural network actually, we need this interleaved evaluation of linear and non-linear components to really get this confusion and diffusion going.

All right, so a bit about the area savings potential, a bit of additional um motivation before we go into the design. So, in essence, um what we can see here is this is what maybe your setup would look like. This could be one ASIC, this could be a couple of ASICs or FPGAs, high-performance implementations of your engines. And the idea is really in hardware design, everything or a lot of things are about space really, and then if we have more space, then we can implement more efficient algorithms, or we can often do um area versus time trade-offs. So, what we really have in an ideal scenario is

that we combine the same area for entity and hashing to overall then speed up both, or at least keep entity at somewhat the same speed while speeding up the hash function significantly using not more area than before. And um of course here in this area, there will be some routing overhead because of course you have to switch between the states of evaluating a hash function and evaluating the entity. However, um we see, at least in our estimations, that this routing factor will be quite small as compared to the to the optimizations.

All right. So, now, uh let's get into the main building block that we actually use, where also the name comes from. It's the Benes network. Uh Benes network actually comes from um real net computer networks, um and uh efficient relay stations. However, we find and we will see shortly that it's quite similar to the butterfly structure that we have in non-linear layers. All right, so this is um the core part of the Benes network. We have two input and two output gates and all of them are connected and all of them have potentially a function connecting them. Originally, this was really a gate either letting

things through or not. However, in our case, we speak of course about all of these are prime field elements and these are then connected by some functions manipulating the data. So, we see the entity was a linear transformation. However, the Benes network does not necessarily have to be and we see the Benes network shares the butterfly topology and quite importantly, I will denote the Benes network with this uh uh style B here, stylized B um to really indicate this function.

However, an arbitrary Benes network is not an invertible function. So, we're going to discuss why this matters actually. One thing before, a hash function does map of course inputs to outputs and I've already said that each of these inputs is a prime field element. However, we in our work are particularly interested in the small prime fields, uh 31-bit, 64-bit and then of course uh a hash function to be collision resistant, we require uh 512-bits of state. So, we need lots of these elements and this is also not complete here, but just uh due to lack of space. So, we need to mix these arms together and the original Benes network has this cyclic rotation

after pairwise application of the non-linear Benes network. All right. So, now um the problem that we have, if this is not an invertible function, for a hash function, we want different inputs to always map to different outputs. So, what happens if you design a hash function and have a non-invertible building block, is that suddenly finding a collision in the hash reduces to finding a collision only in one component. If you have found a collision here, then you can apply the collision to every entry, you have a collision to the hash function.

All right, so, what we do to avoid this situation, we define a permutation. So, we define a set of functions F1 to F4 that define then a permutation over the Benes network. All right, so, our approach of defining a permutation is as follows. Quite generically um so, the numbering is maybe a bit odd, it's 1 2 3 4. So, for 1 2 3 4, we have the following two rules only, which is F3 and F4 are equal, um, which is these two and these two need to be a permutation. In our case here, for example, the simple, um, um, power of five, which is a permutation in

some, uh, some of the relevant fields. And then, secondly, we have that F1 minus F2 is also a permutation polynomial. Uh, in this case, uh, this is a specifically chosen, uh, permutation polynomial. And then, you can, if you think about it, if you subtract the outputs, you get, uh, X0 back, and then you can get the output of, uh, depending only on XY, and then you can, uh, get back essentially. All right, so, now, we have a generic method with these simple rules on the left, and then we have some explicit instances for all relevant primes in the paper.

Um, we can also generically, uh, work with, um, power maps or Dickson polynomials of uh, degree one and so on. All right. So, the strength already, we have a very strong algebraic security. So, really the the pain point of algebraic hash functions is of course the creation of an algebraic model to break the hash function. However, due to this bivariate construction, we have quite high um, security against a lot of these attacks.

Yeah, and still we have, if you look at this, only degree five, which is the same degree as we have for example in Poseidon. Um, usually we find that for the same primes we actually achieve the same degree per round. This is particularly interesting when we talk about um, arithmetizing this later. So, we have a relatively low degree, we have a strong algebraic security, and we have a permutation by our simple rules, so by construction. However, as I said, this rotation step only provides a very poor diffusion, and you can imagine that we need many many rounds to fully diffuse, and then many many more to have real uh, protection against statistical attacks.

All right. And what we then found was, okay, we have this extremely trivial linear layer and this very expensive non-linear layer. So, kind of the obvious thing is to go for more balanced approach and put some more cost on the linear layer as to kind of uh, level these things out. And we really took this as an engineering challenge going through the different kinds of linear layers that are found. Um, where we really see, okay, we start out with the cyclic rotation, I would say almost optimal cost, especially in hardware this is essentially free.

However, really minimal diffusion. Then we have this full diffusion at a moderate cost. Uh, you may know this uh, similar style matrix from Poseidon 2. However, also due to recent papers kind of questioning the security of these matrices, we also additionally looked at MDS matrices, which have this maximal branch number at a high cost. So, maybe to this term, a maximal branch number essentially means that if the input here um differs for one S-box, then after the matrix, the input to all S-boxes will differ.

And this is kind of a very neat property because then you immediately have some more security aligned statement rather than full diffusion alone. All right. However, all of these have their own issues. So, the cyclic rotation, yeah, it only diffuses after T half minus one rounds. The full diffusion matrix has a weaker propagation of input differences, so we don't have these clear statements. We've also seen recent attacks that make people not so hyped about them. And the MDS matrix over FP is really costly over large states, especially if we're looking at 31 bits where we have these 24 element states. Finding an MDS there is hard, and then finding one that's well-structured is is even harder. So,

all options seem infeasible for our talk. So, yeah, thank you very much, that was it. Of course not. We did not fret, but rather we looked at what we have. So, we have essentially This is our state. So, we have a matrix, and then we have the elements as a vector represented. However, what we can also say is well, we do essentially Beneš evaluations, and this means that we always have pairwise elements in our state that are already combined. And when we talk again about branch number, this is really talking about differences in a single S-box propagating to different S-boxes.

So, a difference in a single S-box is either of the two elements actually. So, what we can say is really we can combine the two elements that are the output, interpret them as a prime polynomial extension field element of degree two, and then multiply it with a matrix that is still in FP essentially. And this halves the dimension of the underlying matrix. And if this matrix is still an MDS matrix in the subfield, then also it is an MDS matrix in this extension field due to the property of our non-linear layer being a bivariate function.

All right. And nicely enough, even if this looks more complex, by the linearity of M, we can say that the output that the uh the we have initially the V vector as our state after the non-linear layer. So, the output times the matrix is essentially just applying the matrix to the odd and to the even terms, and then >> [clears throat] >> putting that together again. All right. So, we halve the matrix dimensions, and uh just have to evaluate two matrix-vector products, but at a much lower cost. Quite intuitively, the matrix is shrunk to a fourth of the size.

However, as we know, finding good MDS matrices is also a challenge. So, really low um yeah. Uh for example, MDS matrices that are circulant um quite efficient for FFT, or MDS matrices that only have low values for only addition and so on. So, all of these things get much simpler if we have a much smaller matrix. All right. So, in the end, the bivariate S-box allows for this cheap MDS matrix. We have this very nice synergy about these two building blocks.

The smaller matrix facilitates finding efficient matrices. This is what I just talked about, having a circulant structure or really, yeah, low values in the MDS altogether. And, yeah, um also this still gives us the same benefits against algebraic attacks. So, now both uh against statistically attacks, of course. So, now we have a strong component against algebraic and a strong component against statistically attacks. And at least uh for now, the round numbers might still be subject to change. There is some internal discussion still going on. However, uh we are still uh quite confident that uh it will land around um

this area. This is our entire construction that we can see on the right side. Um and now we see here on the left side, maybe to to alleviate the confusion, we have the 31-bit primes and the 64-bit primes. There we have the 16-element state 24-element state. This reflects to compression and sponge mode. And then we have the different degrees. This is we went essentially through the most used um prime fields out there, being Koala Bear, Baby Bear, Mersenne 31 Goldilocks.

And for all of these, we could either instantiate the Benes construction with a degree five or degree seven, which we all provide in our paper. However, um our construction works in generality, and the Dickson polynomial approach will also find an invertible Benes in generality. All right. So, for the evaluation now, the concrete performance across the different domains, first we look at the plain performance, and there um the results are really um Yeah, uh across the board, we do achieve quite a significant improvement. We did implement this in the Plonky3 library, essentially using the optimized

implementation of different hash functions that were present there. And um most notably maybe is um of course Poseidon as the baseline because it is the most used hash function in the CK context currently. There, we can just say that our construction, due to its high algebraic security, achieves a much, much uh lower rounds. And thus um this is just beneficial in plain because the matrices in Poseidon are heavily punished, as we see with the MDS matrices in Poseidon 1, for example.

For Monolith, we see, of course, that um the higher state is also punished there due to the MDS matrix being in the base field, and generally, the extremely efficient non-linear layer of um Monolith cannot offset the high cost of its uh full MDS matrix. Um Yeah. Uh so, that's that for the CK proof system comparison. Again, this is an implementation in Plonky3 because there were Poseidon 1 and Poseidon 2 present, and I also only used those where the exact parameters were given, so that not we did

uh choose them in some way different to um how they instantiated. And we see Oh, this of course uh should not be blue down there. We have the prover and the verifier. Oh, there's some uh there's some shifting going on. Uh last-minute edits uh biting me in the back again. So, um everything here in this layer should be shifted one to the right. Uh Uh, makes very little sense now, but we have here on the very left always the proof size. It's given in megabytes. We have then the prover throughput and then the verifier throughput. And I mean, from the, uh, from the units alone one can realize,

uh, if we're talking about thousands per second, we're talking about proving things. And we're talking about millions per second, we're talking about verifying things. And then we see this very, very strong gap between Koala Bear and Baby Bear when we talk about Poseidon. And this is, this is really this because Poseidon has a degree seven S-box in the Baby Bear and Goldilocks setting. And degree three S-box in the Koala Bear, which essentially renders the proof size extremely, um, diverse. And, uh, yeah, what we can say is that our design performs relatively similar, even though, as I mentioned, we have

this degree five and degree seven. However, in the arithmetization, we can actually have a roughly similar, um, as we see between these two, we have a roughly similar witness size and the maximum degree is, uh, three if we introduce an intermediate variable uh, for each state element. So, yeah, um, ultimately, as a final comment, maybe we see, especially for Goldilocks, where the field is very small, the performance is very uh convincing. And uh >> [clears throat] >> yeah.

Um, all right. I think that's that. And then also, uh, going back, I mean, you've, you've realized maybe now the story switched kind of a bit away from hardware towards the proof system and plain performance, but this is also due to the development and this is still a work in progress showing us these very nice results due to this new matrix construction. And in hardware still we see um it's maybe a bit um uh not so not so nice to compare, but what's very important are these multiplication units, the DSPs that are used to build these multipliers.

Um we see of course um quite generally that the Goldilocks field But um overall we see across the board that yeah, at least at least for this case in Goldilocks, let's let's stay at the field. Um BNX has the better um utilization. This is mainly again due to the lower number of rounds. And um we also achieve really significantly uh better timings.

Um what we can say still for the frequency Baby Bear Poseidon 2, and this is an implementation uh by one of our colleagues who really extensively optimized this uh in the previous months and maybe years. So there the Baby Bear variant of Poseidon 2 still beats us in frequency and also in resources. However, even though this uh high-end optimized Poseidon was used, the clock cycles and times of the real latency of the implementation still cannot match what we have um with BNX.

All right. So um yeah, in conclusion, I'm already coming towards the end. We have a construction that is hardware sharing. We reuse the data path of a high hieratic entity um that leads us to have a much more area efficient design. Um we use a bivariate permutation for the Benes network. This gives us this strong algebraic security and this also implicitly led us to the new way of maybe defining MDS in this context being a MDS really over the quadratic extension field that retains the nice statistically security properties

while having a much much faster evaluation. And then also we rounded it off with some comprehensive benchmarks that then showed strong results in plain CK and in hardware. So hopefully even if we increase the number of rounds we will still be competitive in some metrics. All right, and that concludes my talk. Here are some great references uh to prior works and then happy for questions. >> [applause] >> Thank you very much Fabian. We do have time for questions if there are any. So I I I missed how you go back from So after the the MDS multiplication you were still in the extension field. Do you just like split up the extension field elements to continue?

>> Mhm. Yeah, um that's maybe not described really. Yeah, but essentially it's it's the same. So it's the canonical Oh, sorry. Uh yeah, essentially the question is okay, how do we go back? And in both cases we just use canonical embeddings. So in memory it doesn't >> it's equivalent to taking all the left side of every network and applying one MDS matrix and then taking all the right side and applying another MDS >> In in essence I think the extension field is really also to mathematically mathematically reason about it also to retain the MDS properties.

However, if you think about it as a programmer really, this is what you care about that you really apply the MDS to all the even and the odd elements. And then you don't care in your implementation whether this is an extension field or not. Mhm. >> So what about what about round constants? Oh, yeah. That I also I scrapped some details in essence in essence the round numbers are added here in this uh uh step at the beginning. Yeah. And then I don't know if my last have another question. Uh so, on the on on the hardware benchmarks, I I'm not super familiar with hardware. So, I was wondering this is on some FPGA. What How should I I assume it's on on an FPGA or Yes. How should I read the the frequency? Is it

like a pipeline uh implementation that will like produce a hash every uh >> And that's essentially what this comment here also states is that this is a fully pipelined implementation. >> Okay. Which means that the frequency that you can achieve directly tells you how many hashes you can Okay. Yeah. Yeah. I was wondering if I should like divide the clock by clock cycle >> Uh no. No. The Of course, this would be if we would have some loops in there, but no. So, that's just latency. Uh yeah, basically. Thank you.

However, of course, maybe a note on frequency altogether is that the FPGAs that are typically used all have frequencies lower than this. So, this is just the maximum frequency that you could get with such an implementation. So, in reality, you actually bound by the hardware's frequency. So, what we see in our deployments is actually the frequency is maxed out everywhere and then only the clock cycles matter really. Um could you switch back to the slide where you have the concrete parameters uh the T in particular, yeah. Yeah.

So, that means so, like over M31, you would use 24 is is it called the state size or whatever? >> So, you So, but essentially, you only need a 12 uh times 12 MDS matrix, right? >> Exactly. yes. Doesn't sound like problematic. I mean, the the thing is So, when we think about the linear layers, we really think about diffusion.

So, we want one input to affect all outputs essentially. And this kind of notion is is captured by diffusion, I would say. But the MDS has some stronger properties in some sense, where it's not really only about diffusion, but rather about this um branch number, where we say, "Okay, even if you cleverly select different distances, it's still should propagate into many many output differences." So, an active S-box is then the terminology should disperse into many active S-boxes in the output layer.

And what we have here is that our S-box does not operate on single, but on two elements at once. >> Yeah, that Yeah, and and that's why we're essentially yeah. >> question was not clear. So, I I appreciate this wonderful trick to go to the extension field without paying for it. Instead, you reduce costs. Mhm. But didn't you say at some point in the talk that that finding these MDS matrices is is troublesome at this size? Yeah. It's easy, yeah. Yeah, okay. I mean, I mean, the larger the harder, I would say. And if you go then if you look at these instances, like for example, eight state elements, and then you have a 4x4 matrix, then you can find for example matrices that only have very

small values, and then the whole matrix collapses into some additions. >> What kind of matrices are do you do you use? Say, for 8 * 8, is it like a random matrix with small entries? >> It has to be MDS. So, MDS really okay, you >> You test it on the test >> test it. And then I mean, what we have um for example, I mean, this is not in this project. I'm I'm unsure for there, but what you can do is you just increase the values really staying in a in a particular norm and then randomly test if it's MDS and continue until you found something which is of course feasible for 4 by 4 but gets gets harder and harder and then for the large state not with this trick you would usually then go into the direction of using

besides from from coding theory like Reed-Solomon codes and matrix representation and so on but yeah. Okay, thanks. Thanks for the questions. Okay last But you are yeah we're on time. So last one. I thank you again for the talk. I was just wondering how feasible would it be or how meaningful would it be updating security proofs for example to use this new construction of linear layer in existing functions. Say for example we would like to apply this to Poseidon 2.

I believe in general the the trick works for essentially if your S-box has an arity n then you can increase the matrix also to the extension field arity n and then if you only in your existing security proof rely on the fact that you have an MDS matrix I think it should trivially apply because this is still an MDS matrix in the extension field. So I would say not so much but maybe you can also talk to my co-authors in this regard. Thank you.

Is that fine? I actually have a question. Is it mandatory for any ZK friendly hash functions to have an Austrian co-author? An Austrian co-author? Yeah yeah that's why I'm here I guess. I'm I'm the typical Austrian ZK designer I guess. Okay, thank you very much guys for staying until the end. >> [applause]