VOLEs and Non-interactive ZK proofs - Carsten Baum

Transcript

So, hi everyone. I'm Sunny, who work at PSE at the Ethereum Foundation. Every once in a while we put on some of these learning shares. Sometimes we have a guest. Today we have Carsten Baum. He's an associate professor at DTU Compute in Copenhagen Denmark. And his research focuses mostly on efficient post-quantum secure computation and zero-knowledge proofs. There's [clears throat] increasing attention on quantum risks and therefore more attention on PQ proof systems. And Carsten's going to talk about one one such construction today.

In addition to also being PQ, these VOLE constructions are also really compelling in terms of like their end-to-end performance. And so they're really interesting for privacy-preserving client-side proving applications like digital identity and such. So, I'm trying to encourage people to look more into them. And yeah, so I invited Carsten over and he's kindly accepted. So, I'll pass it over to him and I'll let him do his talk. Cool. Thank you. And I thank you for the of course for the invitation and for the kind words for the introduction.

And yes, what I will talk about today these VOLE-based ZK proofs they have quite a few applications in the in the area of digital identity. Funnily enough, last week I've been at the Real World Crypto Conference in in Taipei and actually talking to quite a few people about applications to privacy-preserving digital identity. That being VOLE-based constructions or others and what the future will look like and um it it seems that there's there's a lot to be done. So, I'll I'll I'll try to explain how they work. They're not as complicated as you

might think. And and I'll try to explain a few applications. Yes, and as Sunny just said, if you have anything that you want to ask, just raise your hand. And we'll do this just a bit more interactively. Yeah, first of all, before I will go into technical details or anything just that this this whole this this presentation is based on quite a few works by now. Um They have appeared at multiple conferences.

And so there were this fantastic large set of co-authors that I would of course want to thank. And yes, there's this specifications in there, there's publications in there that that led to to all of this. And what I wanted to do is first explain how these proof systems work. What is a VOLE? What are VOLE-based proof systems? How is VOLE in the head working? And then two applications. One of them is a post-quantum digital signature scheme that is currently in the uh in the NIST process for these like additional on-ramp signatures.

Will it be standardized? I have no idea. But it's I think it's kind of cool and I think think people find it interesting just design-wise. And it was the kind of the first application that we found of of these VOLE-based proofs. VOLE in the head-based proofs. Then I'll talk about blind signature scheme, which is a recent work that will appear this year at USENIX Security. One of the top conferences in in computer security. And blind signatures are probably something that everybody in the cryptocurrency space is familiar with.

I mean the old way of doing digital cash before Satoshi came around the corner, for example, was using Chaum's blind signatures. So so this kind of this kind of stuff is probably of interest. So, if you if you look at your zero-knowledge proofs, then the way how how it's usually discussed is two terms. Prover runtime, proof size. And if you do any kind of engineering, there should be a third axis, which is how hard is it actually to implement this thing? I leave that out here and just focus on prover runtime and proof size.

Usually, if you if you have a larger statement then if you're uh if you want your proof size to stay rather small, you take a succinct proof system such as Ligero STARKs or however they are all called. They have a succinct proof. At some point, the proof is smaller than the statement that you're trying to prove. But they all have this disadvantage of having a prover runtime that scales um non-linearly in the in the size of the proven statement. So, your runtime increases quite a bit over just running the actual computation that you want to prove.

So, these have These are often interesting if you if you are in a blockchain context, if you if you think about having a proof that is that is smaller than what you're actually trying to show there and also verify a runtime that is very small. If you want to do ZK rollups or so, for example. But then there are also quite a few applications where the proven statement is actually quite small and you pay a lot for for the succinctness. These are These are proof systems that they are usually proof systems are interesting that have a a proof size that is larger, even up to linear in the size of the the statement that you're showing.

But where the prover runtime is quite a lot smaller, right? So, where the overhead that you're paying for proving something in zero knowledge is is like the concrete cost of doing this is is is small enough, but it gets you a proof that is that is that is larger and the verifier runtime that is larger. But in cases like digital identity, this is often fair enough. And the the state of the art there was was was MPC in the head for a long time among other proof systems. And then recently VOLE-based zero knowledge came as as another solution to that. And here I mention only proof systems that are post-quantum secure. So, of course there's a lot of You can do a lot with elliptic curves

and pairings, but I don't mention that here cuz I only care about the post-quantum setting. And in VOLE-based ZK, we can actually or for proving circuits that are binary circuits, we can get as as small down to one bit of communication per AND gate that we have in the designated verifier setting. So, that's the that's that's that that's kind of the best we can hope for. And there's been a lot of a lot of work in optimizing this kind of stuff. So, how do these proof systems actually work mathematically? They are they are quite simple.

What we need to for them to work is a bit of an understanding of what is called what is a vector oblivious linear evaluation or a VOLE. And the VOLE, you have a a correlation between the prover and the verifier. So, the prover has some information, verifier has some information. The prover in this example here has a vector U and it has a vector V. Um They usually can both of them just be random. And the interesting part is that the the the verifier also gets some information, which is delta, that is some random field element. And then and then a vector Q.

And Q is the fun part because Q is actually a linear combination of the the vectors that the prover got. However, that linear combination is such that one element, namely U, is multiplied by the scalar delta that um that the that the verifier also has as information. So, you have vectors. Everybody there gets vectors except for the scalar delta. And you're kind of evaluating um a a linear function which is which has the one element U and in this this so if you if you think about this, you could think about Q as as as being um

kind of the evaluation of a polynomial determined by by U and V that you evaluate in the point delta. Right? So, you could think about this as as the prover getting getting a polynomial of degree one or a linear equation. And the verifier getting the evaluation of this linear equation in a single point. So, it knows the point. And it knows the evaluation of this polynomial at point. This is what a oblivious linear evaluation is. And if you do that for a lot of linear equations in the same that you evaluate in the same point, you get a vector oblivious linear evaluation or a VOLE. This this is what these things are.

And that's kind of the most Oh, I see a hand being up. Hi, Justin. What would you like to ask? Hi there. Just a quick question. In practice, are there any constraints on on the field? Is it Does it have to be of a certain size to be cryptographically relevant? Does it have to be a prime field or anything else? Fantastic question. I'm have have been sweeping a lot of things under the rug here. What you what you usually want is that your field size size is is large enough to like like something of of the size like 128 bits or so. However, you can arrange things such that for example, U is only going to be in a subfield. For example,

it's just a bit and everything else is in an extension field. And that turns out to be nice because that allows you to do efficient proofs later on that allows you to do efficient proofs so you just send one bit, but you get uh soundness that is as large as the security parameter. But yes, good question. Thank you. And yes, if there's anything else, just hands up. Um okay, where were we? So, we have linear equations and we want to we evaluate them. And Justin has another question. Yes.

Sorry, I got confused. I was trying to put my hand down, but I accidentally cleared that question. Okay, so no question. Good. Then I'll continue. Um So, yes. So, we have this setup. On one side the prover has U and V, at the other side the verifier has the evaluation of this of this linear equation. What are we going to do with this? Um the interesting thing is this is already a linear commitment. Um and this has been known since like the ages of the ancient ages of of of cryptography. Maybe not the old Greeks, but uh since the 1980s for sure.

Um because like if you So, if you have this correlation that commits the the prover to the value U. It also commits it to the value V, but let's for now think it's the value U. Well, why is that? Um if if if the prover So, if you think this is a commitment, so the verifier has has Q and delta. The prover can open open can open it by basically sending the equation to to the verifier, and the verifier can check if when he evaluates this uh this equation on the point that he has that he gets Q. So, the evaluation of that point.

So, that's that's kind of the opening of the commitment and it reveals the message U. This is hiding because at no point does uh Q or delta leak any information about uh about U before you um before the the prover actually opens them. Right? But there's like if you let V be uniformly random, when you generate these these wall correlations, then nothing about U is being um given to to the verifier. And the same time it's also it's also binding, and this is just like good old Schwartz Zippel as it's been used everywhere.

If if I don't know the point at which the verifier has the the evaluation of the polynomial, the moment I use a different uh the moment I use a different secret, I get a different polynomial, and that's only going to agree with, you know, the polynomial I started with in one point because two lines if they are not identical only intersect in one point. Um so, if you as a prover you don't know delta, so if you change your opinion about U, um you're very likely getting caught by the verifier except with probability one divided by the field size, which means that this is actually a a commitment. And if since if you add two equations,

uh you get another equation of the same degree, um this is also a linearly homomorphic commitment. So, this just um the kind of the the the dumbest way of doing commitments. It requires that you're able to to generate these wall correlations to begin with, um and that's what um what was what most of the research has been about. So yes. This is something we already observed back in 2021 to build an efficient proof system in the designated verifier setting uh where delta is being kept from the prover.

So, how do you build a proof system out of this? Uh if you have random if you have random volts that are commitments to random values, you can derandomize them. You can, you know, it's a linearly homomorphic commitment scheme, so as a prover you can just announce the differences between uh what you want to commit and the secrets that you actually want to put in there and and and what is committed there right now, and this allows you to to update the commitments to to something that you actually want to have. And then you use the linear homomorphism to evaluate uh the circuits. So, you can add commitments because they're linearly homomorphic. You can multiply them using a multitude of different techniques.

That's actually where most of the research has been in. And then at some point you get the output a commitment to the output of the circuit, and then you just open the commitment. Like this is kind of standard techniques as as they are used in many um zero knowledge proof systems. Uh and it's usually called the committed proof paradigm that is also at this point almost as old as me. Um yes. So, [snorts] so so that's what you do. The thing about uh vector e-based proofs is that you are usually not looking at them just as uh commitments and addition and multiplication gates or linear gates.

Instead, the the programming model for them is quite different, and that's what I want you to uh to think about because this is actually important to how you use them. Usually you care in the in the ZK proof system about how many multiplications you do because this directly impacts the um the communication that you that you pay for. Um in wall in in wall-based proof systems, this is a bit different. You could you could think about as follows. Every um every wire in your circuit has has a degree. Uh and your in degree is is actually one. So, in because you start with commitments that are of degree one, um linear equations so to say.

Now, whenever you do an addition or a multiplication, you either keep the degree of your commitments going in, or you increase the degree. So, for example, if you do a multiplication, instead of instead of getting a commitment of degree one out, you get a commitment of degree two out. So, a degree two equation and so on and so forth. And that makes the degree grow throughout your circuit.

And at some point you can use what I would call a reduce gate that allows you to get the degree down to one again. Um the interesting thing is that um you if you if you if you look at what is the cost of evaluating evaluating a a circuit based on commitments in the wall setting, then actually both linear and multiplication gates are for free. Um like they don't require communication, but multiplication gates increase the degree.

And then you can have a gate that reduces the degree again, but then you actually have to pay for the communication. So, that is uh that is kind of the programming model that I that I have in mind. Now, you would Now, the the obvious question that you would ask is why would I ever use a do a reduction of a degree? Well, the thing is also that um the prover computation time depends on the degree of the commitments. So, this means that in wall-based zero knowledge, you have an interesting trade-off between um in how you do how you do multiplications, for example, in that you can increase the prover run time and make the proof shorter, or you instead want to

um want to like make the prover run time as optimal optimal as possible, but then you're fine with a uh communication being being larger. But since communication also always entails uh delay, there's actually an interesting trade-off to be found there. So, that's just something for you I want you uh to keep in mind when we look later on at applications such as digital signatures and blind signatures. So, So, now everything I've been telling you about was that the verifier keeps a secret state delta. And that's not really great if you want to build uh non-interactive zero knowledge proofs. And often we want to have non-interactive zero knowledge proofs, right? We want to just be able to send a

proof to somebody else. Um and then they verify it, and they don't need a secret state for that because, you know, otherwise proofs will be um not so sound if the prover ever gets the secret state of the verifier. So, how can we get rid of this? And this was actually something that we looked into in 2023, and we came up to the following conclusion. Well, let's look at look at these wall-based proofs and how they are working. So, in the beginning the uh we want that the prover gets his his or her linear equations, and the verifier gets the evaluations.

Um the prover also has her witness that she wants to prove something about. Now, it's in order to generate the proof, in order to generate a zero knowledge proof, the prover needs her share of of those linear equations. So, she needs U and V. >> [clears throat] >> She needs this information in order to generate the proof that she then sends over to the verifier. Okay? So, she runs uh she commits to um the witness, she does the circuit evaluation, blah blah blah blah blah. But at no point does that actually need uh does the verifier at this at this point need uh anything from from from those walls from those wall correlations so far.

Like it's just no interaction that like where he does anything based on based on those walls. So, so until now the the the verifier would could actually have been silent like except for sending random bit strings as challenges in the ZK proof. Um and and now we're in the situation where the the the the verifier would like to verify. Hmm, but he hasn't gotten Q and delta yet. So, what are we going to do? And the interesting thing is at this point the prover has now finished her whole proof, anything that is based on U and V and so on and and so forth.

Um and she she can't like if she does learn delta at this point uh this is not of any help anymore, right? She has finished she has finished her proof. The only thing she uh she can do is not give the uh like like we want we we could take her help in giving the verifier his share Q and delta as long as this is this is correct, right? She can't convince the the the verifier of of the wrong thing anymore of a wrong proof like the soundness is now the soundness of the proof is ensured. She can learn delta.

So let's do that. The verifier will give her delta. And she will give uh delta as she will give Q to the verifier as long as you know the verifier can verify that it's the right Q. Um so actually in Vol base zero knowledge uh what I said earlier that we want the soundness uh that the proof is uh is sound because the prover have no delta. Um it's actually not not right, right? The whole proof system is sound as long as the prover doesn't learn delta before he finished or before she finished um the whole proof stuff, right? So afterwards she can learn delta and anything is still okay. But this there's now an asymmetry where the prover learns

some information a lot earlier than the verifier. And this actually is something that we can use in order to build a proof system that is non-interactive. Right? Because we don't have there's no secret state that the verifier has anymore. Uh that would make it necessary uh to be a designated verifier proof. And this is actually how how Vol in the head works. So let's put the Vol into the head and I thank uh chat GPT or whatever for for generating this picture a long time ago. Um how do we actually now make the proofs publicly verifiable?

Um well first of all this has a downside. Um in the sense that of course we're linear size. Vol base proofs are also linear size. That was uh what I mentioned before, but they will now have a larger uh overhead in comparison to um those designated verifier proofs. You pay something um for mods two. Uh for binary circuits you pay 11 to 16 times the witness size. Um however, you can compress multiplications again, so that's not actually what you pay.

Um but the cool thing is the the way how it's set up is that we only use uh AES and SHA in order to uh build these Vols to to generate these Vol correlations and then then then and do the whole proof, which then makes the implementation quite efficient. And as I said throughout the rest of the the presentation I'm going to talk about well like how do I turn this into a signature scheme and how do I turn this into a blind signature scheme. Um and the the the way how to how to think about this is well I want to I want to generate Vol correlations.

Um how will I do this? Um and if you have ever heard of something called oblivious transfer, there's actually a nice way of uh of getting Vol correlations due to uh Lance Roy, paper from Crypto 2022 where uh he observed well if I have secret sharing uh I can build Vols um over kind of the same a field of of of of size N. Uh and it works as follows. Um I take my U, so this is the secret uh from my Vol. Uh I share it into uh N individual pieces, so if I add them up afterwards I get U back.

And now we I run an N minus one out of N oblivious transfer, so I give N minus one of the uh N values uh UI to to to the verifier. Then I can think about this as being equivalent to picking a delta in the field and obtaining all UI where uh I is not delta. This is this is what an N minus one out of N OT is doing. So it gives me everything except the index uh except a certain index and that is the same in this case as getting all UI that are not I being the index. Okay.

Well how can I how the hell can I turn this now into a Vol? Um here's the interesting observation. Well as I said my U is uh the sum of all the individual shares. Now this is fine. The interesting thing is how do I define V? V is this odd here if you if you look see it on the on the lower left side uh is this odd um a sum where I'm not just summing the UI. I'm actually multiplying them with uh minus their index. So minus one U1, minus two U2, minus three U3, down to minus NUN.

This is how I define V. Okay, so I have U and V that my prover needs. Now I just need to make Q and um delta I've also already chosen. How can I derive Q from this, right? If if I have this linear equation defined by U and V on the left side, how can I get Q on the right side based on these N minus one values? And the uh the the thing that that that Lance observed uh back in '22 uh is the following. It's really trivial um but it's it's it's it's great. So what if I sum up all the UI uh that I got as as the verifier?

And I multiply them with delta minus I. So on the right side here that you see you have the summation of all the UI multiplied with delta minus I. Um well delta minus I is going to be zero um when when I equals delta. So I can compute this sum Q as the verifier even though I'm missing a single UI value. So that's great. But at the same time if you expand this equation this this equation is actually U times delta plus V.

Um so um even with as the as as the verifier even without having um UI at this specific point, I can still evaluate the polynomial in the point delta by just setting things up in this way as I just mentioned. Um and that is uh that is how from N minus one uh secret shares I get get an OLE correlation and the Vol correlation. Okay. Now oblivious transfer is an interactive primitive doesn't allow me to to build a non-interactive zero knowledge proof.

But how do we how do we then turn this into a um into a uh kind of into a Vol generation for for for uh for for an LIZIC is where instead of uh instead of kind of generating N secret shares uh and sending them through an OT and the receiver only learns N minus one what I can do is I can commit to uh N bit strings and random strings wait for a challenge from the verifier and then open all except one uh of those bit strings. So an all but one um vector commitment.

And those things we know how to very efficiently uh do in a post-quantum setting based on uh pseudo-random generators. And then as I said then with this you just convert them to to to VLE locally. But the great thing is uh the prover has all the information she needs in order to generate her share at the time when she generates the commitment. And the the the the the verifier, you know, only needs to ask for the opening at the time whenever he actually wants to to to verify the proof.

Okay, so how do we do a a such an all but one vector commitment? It's actually very simple. Um you take your a favorite pseudo-random generator like uh AES in counter mode. Um and then what you do is you pick yourself a seed um a random seed. You apply the PRG and now you recursively apply the PRG again and again and again. Right? So that just gives you a tree that's usually called a GGM tree. Um and yes, so this this is how you uh expand um how you generate all of the random values that are that you add together in order to generate the Vol correlations.

In in order to commit you just hash. Uh you just hash them together down down as a Merkle tree. Um that's all fine and good. Um and then how do I open all but one of those values, right? If if somebody wants to give you all uh all of these PRG seeds except for one well you can look at the path from from delta to to the top uh that generated uh everything uh and you now simply reveal everything uh all those intermediate nodes on the tree um that are kind of on the co-path of this, right? So where whenever you go

down like a level you look at like what is the what is the sibling node uh to the node that is on the on the path and uh you reveal all of these. So in order to reveal uh N minus one leaves, I only need to send you log N uh seeds, right? So this this is um how I can how I can build a uh a lot of um so this is how I get all of these uh PRG seeds to somebody and now what you can think about is um for my Vol correlations um I can generate random Um I can generate random votes just by

giving the seeds to you and now you can locally expand them into arbitrary long strings. So, if I give you the uh the seeds on the bottom here, they just define uh arbitrarily long uh vote correlations that that are random and then you just need to derandomize them. Um there's actually optimizations for this kind of stuff because as it turns out that this can can be expensive if you do a lot of this. But this is a way of of setting up all correlations that have been used in in in Wolverine the head. You then need to derandomize them, which is where this overhead uh 11 to 16 comes from.

Um okay, so far about like that that technical part of it. Um then so we we saw a way of how to generate these vote correlations and then we saw if we have vote correlations, we can just simply turn them into a uh into a zero-knowledge proof. So, there we have Now, let's use it for something. Um I'll I'll talk I'll start with digital signatures. This is probably the digital signature scheme with the worst logo that has ever been invented. Um we did a terrible job in Paint there, but uh now we're stuck with it.

Um What what what we did there was um we used the following observation, which is not just to us, other people have been thinking about this before. Well, if you have a non-interactive zero-knowledge proof and a one-way function, then you actually easily can can build a digital signature. How? Well, um you you pick your one-way function, evaluate it on a random point. The output of the random point uh the output of the one-way function evaluation becomes the verification key and the input is the secret key. How do I do it a signature? Well, I prove in zero knowledge that um that I know the secret key that evaluates to the to the verification key.

And then you use your usual Fiat-Shamir transform to hash in the message and poof, out comes a a digital signature scheme. But this is all fine and good, but as you can see here, um it it it requires that we prove in zero that evaluate the one-way function in zero knowledge. So, that means the signing time of of my digital signature scheme is going to be proportional to the runtime of a proof of of of knowing a preimage of a one-way function and the signature size is going to be proportional to the proof size. Um So, for vote that means uh for vote-based ZK means I want a one-way function that I can easily express in the circuit format

that I mentioned to you earlier. And then I that directly translates into uh into the proof size that that you're getting. Um so, you could look look at your most favorite um like let's say let's take an encryption scheme as as the one-way function. Um where you fix um the you fix an input um the secret key of the of the encryption scheme some kind of block cipher for example becomes um becomes your secret your secret signing key and then you you take the encryption of a publicly known input using this secret key is is is your

verification key or your public key. This has been used in a signature scheme called Picnic before. Um so, this could be an interesting starting point. And now you could think about okay, let's take any kind of zero-knowledge friendly uh encryption scheme and use this as the one-way function. There's stuff like LowMC MimC Poseidon uh Rescue, all these kind of hash functions. I looked into that and then uh had an interesting thought, which is why not AES? But if you want to uh build a digital signature scheme that you want to be conservative, you probably want to build an use an encryption scheme in there that is um as as battle tested as possible.

Um and say what you want about Poseidon uh and and all these other ciphers, but I everybody has a bit more um is a bit more convinced about AES than than other uh encryption schemes. And we're already using it uh as a pseudorandom generator in order to generate these uh these these vote commitments. So, let's let's let's just use it. Um so, we looked at AES and can you actually run AES efficiently in a ZK uh proof system? Usually people say no. Um so, what we we looked at AES again.

Let's quickly consider how it works for 128-bit block size and and and key length. Um well, first you have your key expansion, which expands your secret key into um into a number of round keys. Then you XOR your incoming message um with uh the first round key. That gives you the initial state. You apply the round function, which includes uh throwing in the next uh key from the key expansion. You get the next state. You repeat the whole thing for 10 rounds and out comes the outcome of AES.

So, that's evaluating AES um in in in plain. So, if we wanted to use it as a one-way function for digital signature, we would have to do uh all of this stuff that I've that is displayed here in uh in zero knowledge. So, that means we throw out the key expansion and focus on evaluating the round function. So, what is the round function in AES? Well, it has a non-linear part. This is unsurprising. A block cipher that is only linear is not very secure. But um so, it has this uh this non-linear part called sub bytes, the the S-box of AES. Um But then in addition, um it has

uh the these other three steps, shift rows, mix columns, and adding in the round key. And they're all linear operations. And if you think about it from a uh ZK proof system perspective, uh if you commit to the state and if you commit to the round key, right? Applying linear transformations is you know, linearly combining commitments, which is for free, right? This is prover runtime, but this is not communication. And since we care about getting the signature size or the proof size small, that's great.

Um so, we have to think about how does the S-box look like? And interestingly, um the um uh the Rijndael or AES designers back in the late '90s, early 2000s did us a great favor by designing an S-box that is actually very very very nice if you want to evaluate it in a ZK proof. Because what the S-box in AES is doing, it's inverting it's it's looking at the input bits. It takes eight bits and maps it to eight bits.

Um it takes these eight bits and looks at these as being an element in the field. Uh like some version of F2 to the 8. Um and then it inverts this element in the field and that's the output of the S-box. It maps zero to zero just so we're complete, but this is how this is how the S-box actually works. And now if you're um if you're like me, then you then you realize well, in ZK, I know what the input and the output is.

So, to check that the S-box has been correctly evaluated, I just need to do a multiplication in F2 to the 8. Uh multiply the input and the output and check that it's one. Right? This is how I figure out that that um an S-box has that that I I I got the inverse uh of the input is if I multiply the two and it gives me gives me one. Okay, now an input could be zero with probability 1 / 256. Um for the first version of Feistel, we actually just assumed that it never happens, which reduces the key space a little bit. For uh the new version of Feistel that we have now published, we actually handle those cases as well.

Okay, so then how you actually check evaluation of AES in a in as an is it as a vote-based is it as the following? You commit to um to the states of every round uh as bit commitments. Then you apply the linear uh function, apply the add the round key. All of this is committed to over F2. These things don't cost you anything in communication. You you had to commit to the states. That was necessary, but then to evaluate the linear functions forward and backward from the state, you pay nothing.

Then you can in vote-based proof systems actually lift um your secret from a base field to an extension field. So, your committed value can be lifted to an extension field, in this case F2 to the 8. And then I can do this check uh over F2 to the 8. This check that it's that it's actually an inverse. And I only have to pay I have to do like one multiplication for it. So, this we turned into a uh this again is uh is actually a a full-blown uh non-interactive zero-knowledge proof system, uh which we uh implemented and it got us on around 5 um 5,000 to 6,000 bytes uh for

uh for signature and then sign verify times um up to 4 uh milliseconds. Uh so, that was uh Feistel round one. Then we threw in a lot of optimizations for the optimized GM trees, optimized AES evaluations, and so on and so forth. Um and we could actually uh squeeze the the the signature size down to 4 and 1/2 um uh 4,500 bytes approximately. Um and uh sign and verify uh times that are yeah, down down to the uh 500 uh milliseconds uh microseconds.

Uh so, half a millisecond. Um now, the the we would have to set this into uh perspective. Um this is a sign and verify time that is it's it's equally good uh for an optimized uh ML-DSA for example. Uh we get worse signature sizes than ML-DSA, which was would be the standard that you have for post-quantum signatures. Um however, we don't require any lattices for signatures. We just use AES and SHA.

That's it, right? So, that's your your hardness assumption there. Um so, that is that is an interesting trade-off. Um anyways, as I said, we have a signature that is a uh but it is actually a full-blown non-interactive zero-knowledge proof system. So, what else can we do with it? And uh one thought that we had was let's build a blind signature scheme out of it while we're at it. Uh what is a blind signature? Uh the way how it works is uh you not just have a a signer and a verifier. You have a signer a user and a verifier.

So, the user has a message. The signer generates the signing key and the verification key. It hands out the verification key to everybody who wants to have it. And now, how do you sign? Um well, you have an interactive process with the signer who gives you the signature um and then you can show the signature to anybody out there. Uh as a user, you can you can give the the the signature to to other people. Now, why is this an interesting uh cryptographic notion? Well, the first of all, we want it to be a signature, so the user doesn't have the signing key, so the user without interaction with the signer can't sign messages. But more importantly, the signer also never learns the message. So, the signer really kind of generates a

really signs um the a bit string without having any clue what he's signing there. Um this has has numerous applications in digital cash, but also in uh rate limiting and and and other applic- other applications. Okay, those are blind signatures. These are signatures, but like with a little more, one could say, right? So, um and one thing that I also have to throw in, if you want to build a digital identity scheme that is privacy preserving, also called anonymous credentials, you usually start by building a blind signature, and then you extend it to an anonymous credential. So, building a blind signature is also actually the starting point of building a full-blown digital identity system.

Um the way how um blind signatures can be built, uh there's like a well-known construction due to Mark Fischlin from around 20 years ago. Um how does that work? Well, you have your signing key verification key, same setup as before, verification key is known by anybody out there. The user um what what does the user do? Uh it hashes or it commits to um it commits to the message uh together with some randomness and sends the commitment to the signer. Can just be like a hash of the message padded with some randomness.

Now, the great thing is this will not reveal any information about the message to the signer because it's a it's a commitment. The signer signs the commitment and returns it uh together back to the user. So, the user gets a signature on on this commitment H here. And now, what is my blind signature? My blind signature is a zero-knowledge proof of knowledge that I have randomness and I have uh a digital signature such that if I compute um if I compute uh the commitment function on my message and my randomness, um I get a commitment string out, namely H.

And I have this digital signature, but since it's a proof of knowledge, it actually keeps uh sigma and R private. So, as a verifier, I don't learn the commitment and I don't learn the digital signature. Right? Instead, I only get a proof of knowledge of a signature. But this this is uh in it this proof of knowledge is in itself uh kind of the proof of knowledge of a signature is in itself a signature. Um this was kind of a an an idea that Mark Fischlin had um back in the in the middle of the 2000s.

[clears throat] And this is a well-known design for for for blind signature schemes. And the great thing is it works for any kind of blind signa- of any kind of signature scheme that you can throw in there. So, if you take a you know, a post-quantum proof system and a post-quantum commitment scheme or a post-quantum digital signature scheme, you should get a quantum secure um a a blind signature. And if your verification function is very efficient when evaluated in ZK, then uh you actually also get a very efficient blind signature because again, the size of your proof is the size of your signature. The the runtime of the NIzK proof is the runtime of generating a blind signature.

Um so, what we're going to use here are as a signature scheme in our construction are I'll I'll leave out this this part. Are so-called Mayo signatures. How do they work? Uh in Mayo or in unbalanced oil and vinegar, uh what you get as a public key for a signature are just a bunch of matrices, uh random-looking matrices and 1 2 MN. Uh that's how they're called here. And what is a a signature?

Well, you hash uh the signature on a message you generate as follows. First, you hash a message, that gives you a vector. And the vector is as long as uh as the number of of matrices MI that you have. And then, uh your signature is actually uh a solution S such that S * MI * S gives you all these VI values. So, uh if I take the same vector S and I multiply it in a in the right way, left and right with all of these matrices, I get out uh I get out V. So, I have to solve a system of quadratic linear equations uh to generate this S uh the the this S

vector in order to generate this V vector. Uh so, verification here is is is First of all, signing is very complicated. You need that these these these matrices are formed in a certain way so that you actually can solve this system of linear uh this system of quadratic equations because normally it should be uh it should be computationally infeasible to actually solve it or a solution should not exist. But the the trick is that you set up these matrices in such a way that you can easily find uh such a pre-image uh pre-image S uh using what is called the oil space of these uh of these matrices.

That's where all the the hardness in designing the signature schemes is in. The greatness the the great thing is in order to verify that you have such a signature well you just have to multiply a publicly known matrix, namely your public key, on the left and on the right with a secret vector, and compare it with uh the hash of of of the message, and there you go, right? That's your verification. Um so, there it's it's just a quadratic equation that you have to evaluate and compare with uh with the hash of a message. And actually, that's that's what we took as a starting point, and that's how we built a blind signature scheme.

Um so, the first thing we did was we really took what Fischlin did and and and squeezed it into VOLE-in-the-Head. Um for that, we have to run SHA-3 or SHA-256 No SHA-3 on um on the public message, and we have to evaluate it inside uh inside zero-knowledge. And usually, if if you ask any any person who designs ZK proofs, they they tell you, "Please never hash uh with SHA-3 inside um inside a ZK proof." That's what special uh ZK-friendly hash functions are for.

Um but it turns out that that with some massaging and and actually with the fact that we use VOLE-in-the-Head, this is is is is very ZK-friendly. In the same way as with AES, we looked at uh at how SHA-3 works, and SHA-3 works by basically applying a a permutation a few times. Um basically, it consists of 24 rounds, each of these permutations, where where some part of it is is linear and invertible, so this is easy to compute if you have commitments to each of the individual bits.

And then, you have a degree-2 function, and we were uh since it's a permutation, you can also compute it backwards, and backwards, it's degree-3 for each of these 24 rounds. And then, with some playing around with um um with how you how you build the circuit for this specific for SHA-3, uh we were then actually able to uh instead of having to commit to all 24 rounds of evaluating SHA-3, we only had to commit to uh four of the intermediate rounds. And then, we used this uh these tricks of being able to multiply um efficiently and degree reduce later.

Ba ba ba ba ba, let's not care about how this works. Uh there's also a second way of how to do it, and I don't have time for this. However, let's get to numbers. Uh, we implemented this, and we got a blind signature scheme with um if you really take uh, Fishlin's approach and rebuild it in VOLE-in-the-Head with Mayo, which is also currently in submission as a as an additional post-quantum signature, uh, you get down to sign and verify times of way below 100 milliseconds, and a blind signature size of 30 to 40 kilobytes. That's quite nice because in the post-quantum setting, uh, the constructions we had before are blind signatures of

um, that are like maybe of the same size, but where sign and verify times are more like 200 milliseconds. And then we got a different approach, which is, um, which actually allows us to get the blind signature size down to 7 and 1/2 kilobytes, uh, with a sign and verify time well under 50 milliseconds. So, just like outperforming all the state of the art of lattice-based blind signatures. And now the next question is, can this be turned into an anonymous credential scheme? Um, future work will show us. So, in conclusion, uh, VOLE-based ZK, well, that's um, it's a very simple proof system that gives you linear size proofs. Uh, it's very fast.

Um, VOLE-in-the-Head makes it publicly verifiable, uh, requires some tricks to get it uh, to get it to work, but it's also not super complex theory-wise, um, engineering-wise a bit more. Um, we turned this into a digital signature scheme, uh, which is, uh, hopefully post-quantum secure, has, uh, much better performance than other signature schemes that rely on conservative assumptions like SPHINCS plus, while at the same time, um, so, it has a reasonable has a better performance than these, while also having conservative security assumptions.

And in the very end, I now talked a little bit about, uh, blind signatures from Mayo, um where well, we run a whole a verifier for a signature scheme in a ZK proof, and it turns out it's not too bad. Um, and with this, I'm open for questions. Thank you. If there are if there's even time for SPHINCS questions. Yeah, we have we have time. Um, we can wrap it up whenever you are done.

>> a bunch of questions, but I don't want to front-run anyone. No, go ahead, Justin. Okay, cool. Uh, I guess one question I have is um, if you were to use Poseidon Poseidon Uh, can you repeat the question? I think my my internet connection just dropped for a second. Um, so, uh, in SPHINCS, you currently use uh, AES. What if you were to replace AES with Poseidon? Would you get significantly better performance numbers?

Um, nope. I don't think so. Um, in particular because Poseidon is usually defined over large fields, um, and, uh, there are not so many implementations of VOLE over large fields, VOLE-in-the-Head over large fields available right now. However, um, what can do, and which is fun, is you can, uh, instead replace AES with uh, random linear equation and then put random quadratic equations, which is related to this, uh, Mayo assumptions, and, um, it's still probably better than lattice assumptions, and it gives you signatures of around 3 kilobyte.

Um, there's actually a submission to NIST that does exactly that. Got it. I mean, what when you say Poseidon is is not usually associated with small fields, how small is small? Because right now we're using Poseidon with 32-bit, uh, actually 31-bit fields. I believe you can even go uh, lower than that. Yeah, I know I know you can go go lower than that. Um, you you could easily set it up in VOLE-in-the-Head to run uh, Poseidon in VOLE-in-the-Head.

Um, we have just never done it. I have no idea what the efficiency would be, to be fair. Like, we care about AES because because NIST, uh, we did we use AES because NIST would find uh, that compelling because we use something as a one-way function that is well tested, while, um, uh, Poseidon is is like AES is standardized. Poseidon is not, right? Um, that's that's why we used it. Okay, understood. Um, you mentioned you're in round two of the additional, uh, post-quantum signatures uh, com- competition. Um, do you know how many rounds there are, and when the final

decision will be made? >> [laughter] >> No idea. I have really no idea. Um, I'm I'm also not the most optimistic for FEAST because I'm not sure if this is what what NIST is actually looking for. Um, what is what I think what NIST appreciates is that in comparison to other constructions, it is like what is running under the hood is really a full-blown ZK proof system. Um, and this is why we got from from FEAST to something like these, uh, blind signatures, Pomfret blind signatures so easily. Like, it's just it's kind of it's all the same technique. There's not much that we had to add.

So, if NIST is actually looking to standardize something that can easily be turned into an anonymous credential, uh, we'll probably hear back from them. That being said, do I have an idea how many rounds there are, and how how how long things will take? No, I don't have any more information than you have, um, as as an outsider. Got it. I guess in terms of security assumptions, when comparing to SPHINCS plus, for example, is it fair to say that in addition to introducing AES, uh, you're also you're losing the opportunity to have security proofs in the standard model, and kind of making, you know, this making use of the the Fiat-Shamir

heuristic, which also weakens security? Uh, but don't you also need a random oracle in, uh, SPHINCS plus? If you hash your message to, um, I think at multiple points in the proof you also need to, uh, consider the the the the the underlying hash function as a random oracle. Not in order to set up all these one-time signatures, but I think when you hash your message down to, um, one of these, uh, paths, for example, I think there was also a step involved where you don't do Fiat-Shamir, that is correct, but you're assuming that the, um, that the hash function is a random oracle as well.

However, that being said, we we might we do require likely more our security proofs are not as tight as SPHINCS plus, if I remember correctly. Um, and we also need the security of AES in in in multiple ways. So, it is I would say it's conservative security. It's it's more conservative than assuming new things, um, while SPHINCS plus is probably even more conservative than our construction. Okay, got it. I guess another thing that I'm wondering is if you were able to somehow make AES SNARK-friendly, like, is there maybe an opportunity to use these ideas to have a hash function

based on AES which is also SNARK-friendly? Ah, yes. And if you look into our paper, um, we do have uh, we have a hash function called uh, we um, so, AES as hash function, no, but if you replace, uh, SHAKE uh, with, uh, something else that is more, uh, friendly, um, we have we are you we are, um, in addition to, um, the the so, in the Pomfret blind signatures that we do, we also have an construction where we replace SHAKE with, um, uh, with a hash function called RAIN, um, which is is which you could look at as a version of

of um kind of using the AES paradigm to construct a, um, uh, a hash function on on the highest on the super highest of of, um, of [clears throat] of levels. Like, there's there's a lot more involved, but it's it is a hash function that is very very friendly for uh, MPC-in-the-Head based constructions, I would say. But maybe also, um other uh, for for other SNARKs. Our actual SNARKs, like Aurora, is of course not a SNARK. Okay, so so, RAIN, is that uh, a hash function that you you designed as part of FEAST, or is it a separate paper and and team, I guess, behind it?

Um, it is it is coming out of, uh, TU Graz. So, Christian Rechberger and, uh, other people have been uh, designing it already before. So, we're not the first to to to use it. It's he's also behind Poseidon, right? So, it's it's kind of the same team, um, I I would say. Okay, fair enough. Um, I guess one final question. Do you happen to be on on Telegram by any chance? Because many of us at the Ethereum Foundation are use Telegram. Um, no. Uh, you can find me on Signal on Signal and on WhatsApp, uh, but not on Telegram.

Okay, got it. Yeah, we're also out of signal. Um Oh. I see. Uh do you have time for maybe a couple more questions? Sure. Yeah, I was just been trying to understand what the proof size overhead is. Um like specifically going from the designated verifier setting, which I think in the binary field that like more or less amortizes to one bit uh per multiplication. When you go in into this whole in the head paradigm, you said that there is some sort of like 13x um overhead factor with that. Is that Is that a constant factor? Like the it's

just a linear constant uh increase as the statement uh gets larger? Um yes. So, in the following sense, um in uh in vault-based proof systems, you you usually you you start out with some uh random vaults and you need to commit to your the actual witness in the vault that you want to have. And in in vault in the head, if you if we work over F2, you have to send approximately 11 to 16 bits in order to commit to a single bit.

Okay? That's like for the for the witness input. Now, um the the the thing I was trying to get across is that if you do uh with this like thinking about degree reduction, not every outcome of a multiplication has to be committed to as well. So, you're not It's not It's not that you pay 11 to 16 times input of the circuit plus uh number of multiplication gates. It really depends on your circuit topology uh what you have to pay.

Um because you can if you can align things nicely, you can do a lot of multiplications before you will have to reduce your degree again. Um and this is actually what we uh what we do in in in in pump it in that we that we see instead of if you evaluate Shake, you don't have to commit to all the rounds of Shake that you do. Um by because if you align the multiplication gates in a nice way, uh you can basically do six rounds together uh instead of com- instead of communicating for every round, you just communicate for every sixth round, so to say.

Um and so, yes, you pay a you pay an overhead um for these commitments um for like to commit to the witness, this 11 to 16. Um but you are also uh you're saving because you use vault-based proofs, which allow you to kind of squeeze the the circuit evaluation together. Um which which then saves you in terms of proof size again, right? Because now you're sending less information to evaluate the circuit.

Um with that That's where the interesting trade-off for for for vaults are. There I have to say this trick of um um not paying for multiplications and doing degree reductions instead, it's also something that works for designated verifier uh vault-based proofs. So, stuff like Quicksilver. Right. Yeah, so I guess that would just be like a more efficient like arithmetization. Yeah, okay. Yeah. Uh speaking of Quicksilver, I'm not sure if I'm going to be able to recall this correctly, but it has some sort of like batched like polynomial proof in it where you can Yeah. Are Are those techniques Do those translate into this setting as well?

Um not in ours. I remember that for um um for Antman, which is this this batch paper, uh this batch extension of Quicksilver, there are works that translate this into a vault in the head style setting, but somehow I I missed ever reading the paper of how it works. And if any of the uh the authors ever watches this video, I will be deeply ashamed. Sounds good.

Um I guess just one other one. Uh I did ask you about this in an email, but just touch it over here. Um so, I guess mixed field You already kind of talked about this. So, I guess like the efficiency kind of goes down when you start using larger fields. Um it like is that a large blowup in proof size computation? What like What What is the actual cost is there? Uh it's It's It's actually It's not It's It um It It is kind of um So, the the efficiency actually doesn't go down. It's It's actually quite the opposite. So, uh when you go to larger fields, um the interesting thing is like vault in the head itself is uh is is super

efficient for the mod 2 setting. Uh and then there's a variant of vault in the head that works very nicely for for uh large prime fields or even like mid-size pri- even like 20 to 30 bits. Um however, um and and there actually the factor the overhead that you pay is even for vault in the head is more like a factor of two or three and not like 11 to 16. Um however, we we never got around to implement the mod P version of vault in the head. So, I can't like end with that ever having played with um uh an actual implementation, I can't tell you much about how it how it performs.

Yeah, totally fair. Just curious cuz yeah, often at least at least for digital identity and particularly just like reusing like existing credentials, you're going to have like an ECDSA signature, but then you're also like you would also not prefer to be in that field when you're trying to like validate like a JSON document or something like that. So, the ideal case would be you know, you could just like arbitrarily switch between these fields, obviously with with the cost associated with it, but uh wouldn't that be nice? >> [laughter] >> That That would That would be nice. And uh if if if if if somebody finds me uh the money for a PhD student and a PhD student, then uh this this has been like high up on my to-do list for a long

time. Um but yeah, without the actual um man or woman power to get this done, uh it's it's it's a bit difficult. But yeah, it's I I am as curious as you are about this. Um in particular, how it compares with uh Longfellow's ZK uh by Google. Right, exactly. Who do this um but using rather different techniques. Looks like Justin's got another question.

Yeah, um Kostas, just to to give you a little bit of context on what we're doing uh with Ethereum. So, you know, we're we want to move to post uh quantum security. And we're going to have a lots of transactions. And for us, the the number one scarce resource is is bandwidth. So, you know, moving from 64-byte ECDSA to anything else is like very expensive. And the basically the only solution that we know of is is signature aggregation, where you know, we have a SNARK that proves knowledge of multiple underlying signatures.

And in order to get signature aggregation, the only solution that we know of that is practical is basically to have some reasonably SNARK-friendly signature scheme. For example, Sphinx, where you you you change SHA-256 with uh with Poseidon. So, for us in the Ethereum context, we're actually very comfortable with with Poseidon. Um especially, you know, if it were to be shipped in let's say 2029, Poseidon would be 10 years old, you know, heavily battle-tested. And even today, it's securing, you know, billions of dollars in the context of of ZK-rollups.

And so, you know, this this research into you know, um vault in the head with with the larger field sizes, you know, maybe 31 bits, uh and using using Poseidon is actually something that we would potentially find very interesting. Um And as an alternative to Sphinx, which is slightly smaller signature. So, I guess the the reason why we still do care about signature size even in the context of aggregation is that there's the off-chain footprint and the on-chain footprint. So, what goes on-chain is the the SNARK, but we still have off-chain in the what we call the so-called mempool.

Um Like all all of these large signatures that have to be gossiped. And you know, we do have ideas, for example, mempool sharding and things like that, but it introduces complexities. Um and you know, you mentioned that you know, you yourself are very curious and you you've been looking for money and stuff like that. I guess is this something that you would you know, consider, you know, working with us? And like how much money would you want? And and I guess >> I have to say there um um So, if if we talk particularly about uh about SNARK-friendliness, right? What

you need to do in in in a SNARK in order to to aggregate the signatures would be to evaluate the the signature verification in the snark, right? If I understand you correctly. Exactly. Right. So, this is actually not too bad in in Sphinx plus because it's just evaluating this whole nice tree and and and verifying that you have some path in there if I remember Sphinx plus correctly. Um that is not so easy in in feast um or or versions of feast because the verification has to build has to expand all of these all of these trees to generate these whole

correlations and then um uh and then apply the one-way function on on all of this. Like there's a lot of um like these 500 microseconds, there's a lot of things going on um computation-wise in order to uh in order to verify the signature. And I honestly am not sure if throwing this into a snark is a better idea because performance-wise, I mean I I agree that like gossiping-wise, you you you cut

uh you cut communication by a factor of two um but uh snark-wise, you're going to be in trouble um simply because the the verification circuit for Sphinx plus or any version of Sphinx plus is just so much simpler than than for feast or or whole-in-the-head base proof systems. That's also why um like the one thing where where Sphinx plus outperforms feast is that it has a much much faster verification time and that's actually where you usually want to use Sphinx plus, right? If you want to uh like outside of outside of the blockchain context, you want to use it uh where you need conservative security

but don't care about uh signature size or or or prover runtime or signer runtime which is like software signing or so, right? Um and and and from that perspective I'm not so sure if I would try to wrap um uh like like try to verify uh feast inside a a ZK proof. It would be fun to see how it works how it works out but um we haven't tried it and I think Sphinx plus would be much much better candidate for that.

Okay, got it. Thank you for the honest assessment there. Yeah, I guess I'm curious go ahead. That being said, if somebody ever tries it, I would be really curious about the results. Yeah, same here. >> I've also asked in the past as well. It is that mostly just the GGM tree and you're having to do just like Yeah, okay. Like which is which is super efficient on a on a on a on a on on on your laptop or or any kind of other device because you have a you have instructions for AES-NI but if you were to so all of these PRG calls are are super super efficient and can be neatly pipelined on a processor but if you were

to all of to do all of the verifications of this kind of stuff in in a snark, it's going to be a pain um because last time I checked, there are no AES or other PRG instructions for for for for snarks that are super efficient. Um However, of course you can replace AES with with something else there but it would still be the bottleneck. I mean if we replace AES with Poseidon 2 which I guess could be used as a as a PRG um you know, we can prove on a laptop CPU a million Poseidon hashes per second.

So like how many calls to the PRG are we talking about? Good question but you also want your output to be bit strings. Though you may not need that for um for the you don't need that for the mod P setting um so it's actually it's a good question. Um for the mod P um uh so for whole-in-the-head modular prime modular large prime it might actually not look as terrible

but I I like even like even even having a pen and some paper, I can't do that like back of the envelope at this point right now. Sorry. I mean you you mentioned it's a few thousand calls for sure. Okay, but right because you mentioned, you know, the overhead being like 15 or whatever and like I was thinking, okay, like the depth of your your tree is like 15 so you have like two to the 15 so let's say 32,000 calls or whatever. Like we can do that in a few milliseconds of prover time.

Yeah, but if you want to aggregate signatures, that's a lot of like that's a lot of repeating that, right? Yes. Um but um it might still be relatively competitive. So for uh so Sphinx plus, we're talking about roughly 2,000 calls to Poseidon. Um So yeah, it depends on the constant there like how many thousands.

Yeah, also also I really don't know what the performance is if we turn if we use whole mod P uh whole-in-the-head modular primes for a signature scheme because we have we have never tried that. >> [laughter] >> So it would be interesting to see but you might end up with signatures that are just a lot that are even larger than Sphinx plus plus which defeats the purpose. Okay, got it. Um Well, if you are interested in Sorry.

Sorry, you can finish that, Justin. Sorry, I think I have five minutes to speak. I would just want to say if you are interested in looking into this and you are looking for money, I just feel free to to knock on our door. Yeah, yeah, thank you. I'll I'll definitely keep that in mind. Um sounds like it definitely that sounds like an interesting direction. I I think I found the master project for a student. All right, well this has been really great. Thanks so much for coming on, Carsten and giving us the run run down on this. I think we probably call it

there. Um Yeah. Thank you Thank you for hosting me and thank you for your time.