ZK Whiteboard Sessions - S3M3: Lattice-based SNARKs, w/ Vadim Lyubashevsky

Transcript

Welcome to this module of the ZK  Whiteboard Sessions. I'm Nico, I'll be today's host, and our guest today  is Vadim Lubashevsky from IBM. Hello, Vadim. Oh, hi, Nico. It's a pleasure to be here. Yeah, it's a huge honour to have you here,  especially to talk about today's topic, which you're a leading expert of, which is? Lattice cryptography, and in particular lattice  proofs, where we try to actually do proofs compactly and with efficient verification.  So in this session, we'll try to cover as much as we can. First, we'll introduce lattice  problems, so the hard problems that we think are computationally hard, even for quantum computers,  because that's kind of the main draw of lattices.

One of the main draws is that they're  computationally hard for quantum. Then we'll talk about how to get commitments  from these problems. It's going to be pretty straightforward, but it's its own thing. And then compact commitments, how to commit to a long string, sort of compactly, and also, very  importantly, to prove knowledge that you know this long string, that you know that it's long that  you know the string, and that its norm is short which is pretty important for lattices. Then  once we do that then we're going to actually try to prove more exact norms of this. So as  we'll see, with lattices, it's a 2-step process.

First, you prove that something is kind of small  so you know it's a commitment and then you kind of get into it and say, actually, the norm use some  more techniques to prove that the norm actually is as small as you kind of desire as long as you had  it originally. There's no relaxation in what you prove. So we'll do that and we'll actually prove  but that'll be almost the complete high-level introduction to how one would do these proofs in  practice these lattice-based proofs in practice. Then we'll switch over to maybe an even more  high-level overview of how you would do this even more efficiently, instead of over integers, over  polynomial rings, which is what's done in practice for all other lattice-based schemes. This is very  compatible with the proof systems, which are not

going to be zero knowledge at this point, but  they can be made zero knowledge using some other fairly standard-by-now technique. Sounds good. Okay, so I guess the very first thing we should know is what is a hard lattice problem, because  we will need something like commitments for proof systems, and we will need a hard problem  for that. So let's first kind of describe what a hard lattice problem is. So in general, it's a  linear algebra thing, so we work with matrices A, and they're usually in some, let's work over  integers for now, but in practice, we really work over polynomial rings for efficiency. But maybe if we have time, we'll talk about that later, but hopefully a lot of the  techniques carry over. So we have some Zq,

and q is usually a prime, let's say, of 2 to 3.  In these schemes, it'll be about 32 bits, 48 bits. In encryption schemes, it's smaller, but  let's just... q is something like that in Zq, and it's like n times m. So n is usually tied  to the security parameter, and in practice, it's about 512, 1024, something like this. m can be whatever you want. And then there's a secret s and it's a vector in z to  the m with small coefficients. So the norm of s is small with respect to q. So you could think of s as being binary, maybe, but it could be bigger than that.  It just has to be small with respect to q.

Is s a vector in Zq, or just Z? It doesn't really matter, right?  Because, yeah, think of it however you want. We'll do operations mod q. Because we're assigning some norm to s, we can think of it as integers, but if you want to think  of it in Zq, that's fine as well. Whatever's easy. And the 1-way function is fA of s equals As mod q. So that's it. I basically take s, and I multiply it by A, and that's my 1-way function.  So it's hard to find s given fA of s, given this.

Okay, fA and A, and it's hard to go back to s. Exactly. You're given fA of s and  A, and it's hard to get s. Exactly. So this is called the SIS  problem, the small s. SIS? SIS Basically this. So this is the inhomogeneous  version, meaning that this part is not 0. Okay. You can also have the homogeneous version,  is when you're given an A, a random A, find s such that As equals 0. I'm going to  stop saying mod q, because everything's mod q. And As, this is the 0 vector?

This is the 0 vector. Cool. And I'll probably stop writing vectors.  Yes, sounds good. Okay, because I'll forget. Okay, good. So this is the  SIS problem, right? Okay. So one thing you may know, may kind of  see immediately, is that you can get a commitment scheme like this, and a compressing  commitment scheme. So all you do is you multiply, you have your A, you multiply A by s equals  t, and you say t is a commitment of s. And the reason it's binding is because if you  find another As prime equals t then this implies that A times s minus s prime = 0. And the norm of this is basically twice as

large as the norm of s, which is still small  with respect to q. We set our parameters, so this is still a hard problem.  And this is now a solution to SIS. So basically somebody who can find  a second pre-image solves SIS. Okay. So our commitment scheme is  just multiply the vector we have by A. And that we've committed to A. Yep. And notice that since I said before that  m could be sort of arbitrary, almost arbitrary large, this is a compressing commitment.  So you could have a very long vector s, so basically of dimension m, but at the end  you get a vector t that's of dimension n Okay. Now the coefficients of t are bigger  because s had small coefficients, but this has coefficients all the way up to q, but that's not a  big deal, right? That's a log q difference there,

but you do have a big compression from m to n So is this what we call the Ajtai commitment? Yes, exactly. This is the Ajtai commitment. So from 1996, this is from the original Ajtai paper where he said actually being able to  solve SIS is as hard as solving some worst-case lattice problems. And kind of that gave us  the framework to build on, to care about this SIS problem specifically. And we said, okay,  now let's actually analyse this SIS problem. Okay? Yes, exactly. Okay. So now that's kind of all the tools we need to start building our proof  systems. Nice and simple. Yep exactly.

So, yeah, there's actually a lot less math here  than you need for other things, right? This is basically all you need to know. Okay good. So now I guess we're not going to get into the most efficient schemes, but we'll try to  just give an idea of how you can get a succinct proof system with an efficient verifier to  prove something that's interesting. So the interesting thing will be so suppose and  this is very basic, suppose we have some vector s. We want to commit to this vector s. It's a very long vector s. And we want to prove that the norm of s is some  bounded thing. It's some bound.

So that's all we're going to prove. We can  also, like in the real, for real systems, we can also add some linear equations into it. We  can also prove that s satisfies blah, blah, blah. But that's kind of, let's say, the easy part.  Okay. Proving linear relations is pretty easy. It's proving this norm of s that's always  the tricky part, quadratic relations. And this is necessary because our problem is  only hard when the norm of s is small, right? Exactly. If the norm of s were large, then it's  actually pretty easy because if you draw your A, you have your A times s equals t, right?  Then if there's no size restriction on s, then you could just, well, pick a square  part of A that's invertible, right?

Set all of the rest to 0.  Right? So you ignore this. I see. And then you just have A times something  equals t. And using Gaussian elimination, you find this something, right? So, yeah. So it is quite crucial that the norm of s is small. No, it's okay. It's annoying,  but I think that's also what makes this SIS problem plausibly quantum safe, so  that there is this size restriction on s that seems to make it very different than  discrete log and problems of that form. Okay. So we've described commitment  schemes. So now let's actually commit to s, and prove to a very long s and prove that  we know it and that its norm is small.

Sounds good. Okay. So we have this long vector s. Let's say its size m^2. Okay. So little m^2. So what we're going to do is we have our  matrix A, right? Which you remember is A is an m by n. And we're going to break up  our s into m parts of m dimensions each. Okay. So we can have, so now we have a  matrix like A [s1, s2, all the way up to sm] These are vectors. Yeah. I've given up on the arrows. Yeah. It's not going to happen. Exactly. Each of dimension m. And this is equal to like t1, t2, up to tm. Right. And these are all vectors of dimension m.

Okay. So can we understand this as doing A  times s1 equals t1, A times s2 equals t2? That's exactly what it is. Right. And now observe  that this commitment is now smaller, right? So before, if each s had dimension m,  then this was m ^2. But now this is n by m. And n is the security parameter, right? So it's kind of independent of m for the most part. Okay. So our commitment is now smaller. Okay. Good. So, and then, you know, instead of writing this, I mean, you can think of it  like this, but I'll write it as As equals t.

Okay. And it's all mod q. Let's not forget this. Yes. Okay. Good. So now I want to prove to you  that I actually, so I have this t, I want to prove to you that I know some s, so  that s satisfies T. All right. So let's just do kind of a bit of a thought experiment that's  almost a proof, but it's going to be a proof. All right. So now the verifier gets A and  T. And what he does is he sends a vector c. So c is in a random vector  in 0, 1 to the m. Okay. Okay. All right. And the prover responds with  z equals s times c. And he sends the c.

Now the verifier then checks that (1) norm of  z is small. So in this case, like what can we hope for small b, right? Notice that we have  our s, which let's say s is binary, whatever. Okay. Right. So if s is binary, then  each coefficient of SC is at most m. Yes. Because at most we have all 1s in our  c and we're adding everything together. So each coefficient is at most m. So that's  something you could check. You can check the L2 norm is m times square root of m, right? Because we have m of these dimensions. Okay. Right. So small is just, I'm not going to write preSISely

what it is, but it's just small depending on what  we're trying to prove about it. Sounds good. Okay. But again, it has to be small enough  with respect to q so that the SIS problem eventually is still hard. We'll get to  how this relates to the SIS problem. So we keep it vague for now and  we'll come back to it later? We'll make it less vague. Okay. Sounds good. It'll still be vague, but maybe at least 1  can fill in the blanks. Sounds good. Okay. And (2) we check that A times z equals  Tc. And notice that if T really is As, then this should verify.

We have ASC on the right, and here  z is also sc, so A sc. So A sc, A sc. Okay. Sounds good. Okay. Good. So the protocol  is at least complete, right? Yes. Okay. So now why, at least  why can we hope that it's sound? All right. Now suppose that, so we have our  z that satisfies this, and now suppose that the prover can also answer this query for  another c. For a c, let's say for a c prime, that's the same as the c here, except  in the i-th coefficient, it's flipped. So if the i-th coefficient of c was 0, the c  prime is 1. And you know. Could we write maybe a very quick example of how to show them? Yeah, sure. So if c is like, is the vector,

I don't know, 1, 0, 1, 1, and we care  about, we want to flip this position, then this c prime would be 1, 0, 0, 1. Cool. Okay. So now you notice that c minus c prime is going to be 0 everywhere except plus or minus  1 in the position that's flipped. All right. So if the prover, I mean, that's a big if, if  the prover can actually answer for this as well, then we'll get the, we'll get z, we'll  have z bar, z prime. Equals SC prime. SC prime. Okay. Well, no, we don't  really know that the z prime is SC prime.

z prime is something.  Something. And z prime is small. And Az prime equals Tc prime.  Right. So now we have Az equals Tc. Az prime is Tc prime. Subtracting, we get  A times z minus z prime equals T times c minus c prime. Now notice that c  minus c prime is exactly, you know, 0 ever except the i-th position. So this is actually ti.

Or - ti I guess. Yeah exactly. Or - ti. Exactly. Right. So then we have A times  something that's small equals + or - ti. Right. So, and there, and that's actually, so  we do know something. So now, of course, the size of z is bigger than the size of s.  So what the prover knows something, but he can only prove that something's a bit bigger. But as long, but for now, we don't really care about the side. We just care that it's  committing. So it's like its small enough. Right. We're going to, we're going to end up  proving that something about the norm of s that's actually much smaller. Right. But for now, this, we're just trying to say that he committed to something.  There's only one thing he can open to.

Okay. Okay. So just in this case, this would be si. This. Well, it's the extracted. So this, let's call  this like S bar sub i. That's not the si. So he knows some si, which is maybe  binary. Right. But now the Zs have coefficients size, you know, as big as m. Yeah. Right. So now this A times si equals ti. This is not. Okay. This might not be exactly si. This might, he may not prove that he knows si, but the important thing is he cannot open it  any other way. I see. So there's only one thing. Maybe he knew something that was much  bigger. Right. And that's what he proved.

Yeah. But whatever. So there's only  one thing he could have opened to. We don't know about that. We can't  still ascertain that the size is as small as he claims, but we know that there  is only one thing he could have opened to. Okay. Yeah. This is. Yeah. Clear. Okay. So let's. So that's good. But now let's. So now  we can be like 2 things to discuss here. 1 is, well, this doesn't really, we can't  really expect the prover to do this. Right.

Because let's say the prover, some adversarial,  he only needs to succeed with probably less than a half. He can say, no, look, I will only  answer this challenge if this is a 0. Right. He'll just fail. Actually, because  he cheated on the ti. Right. Yes. Okay. So then the solution here is,  well, this here, we sent the vector c. But what if we send a matrix c? Right. So here  we sent, what we did is we sent a vector c. Right. That was 0 1. Right. And then the extraction, we fixed c. Yeah. Everywhere except 1 position and flipped that. Yes. And that we said, well, the prover may not answer that. But what if we  instead send a lot of challenges c?

So like a matrix c. Right. Yeah. And then z was s times capital c. Right. So basically sends a lot of these z’s. Right. And now all we have to do is we fix everything in this matrix, except we make this  last row completely random. So we make it … So we don't necessarily flip it.  Yeah. But we say it's just random. Okay. Okay. So now since there's,  let's say, 128 of these, now he has to reply. He cannot  just not succeed on all of them.

Right. Okay. Because if not, we do have  a sound protocol. Exactly. Because then he probably just has, he’s not  going to succeed very often. Yes. Right. And so now with high probability,  1 of these will be flipped. Right. And for that 1, we extract our z. Okay. Right. So now, of course, the downside is now this is  much bigger, much bigger. So just to resume this step, the problem  we had here is if the prover notices that we have a flip, they might just  abort. Yeah. And it's not a big deal to soundness because they  still have 1 half chance to win.

Yeah. And then here we force it to become much larger. Yeah exactly. Okay. So it's not even notices,  right? It's like he says, look, I actually cheated on position 3. Right. Right. So like I will only reply when it's 0  because I have no idea what it actually is. I need my s to be multiplied by 0. I see. I see. Okay. Or it's like s is actually huge and I need  it to be or let's say, yeah, it's something. Okay. So if our challenge is such that  position where the prover cheated is 0, then prover is happy to go. Yeah. Exactly. Let's say the s in  that position is actually huge. Yeah. Right. But he's like, oh, that's fine. That's great. Because as long as it's 0 it doesn't contribute. So he's like,  that's all I'm going to answer.

Okay. And good. He'll succeed  with probability of half, right? So it's, yeah, it's actually not  just a proof or problem with the proof. It's actually insecure. Right. But here, if he says the same thing, like, oh, I'm going to, you know, s is large and  there's not, you know, you'll never catch. Well, that's not true. We will catch him. Right. Because 1 of these will be 1. Right. And he has to answer. Gotcha. If he's  waiting for all of these to be 0. Never going to happen. He's  never going to happen. Right. Okay. So that's the intuition. I mean,  yeah, this is the intuition if you really want to do this over the integers. Right. We never do things over the integers. But I think this idea of  kind of fixing everything except one thing that has a large entropy  and changing that, that actually is

used in our techniques a lot. Okay. So, yeah. So now, okay. So good. So now we modify this protocol.  So instead of this being a vector, now this becomes a matrix in m by, let's say, 128. Whatever. Doesn't matter. Some security thing. And this is equals s times c. This  is now a vector matrix. Sorry. Now we can check that, whatever, norm of z is  small. Let's say all the coefficients in the matrix are small. Again, being as vague as before. Sounds good. Right. And then this is Az equals Tc. Okay.

And then the proof actually goes. This  time it actually goes through. Yeah. Because now we do know that there is  some c that is flipped in 1 of the… Right. And that's exactly what this c is. Okay. Good. All right. So this is… Does the intuition  for the proof look the same? It's exactly the same. Right? Because all we're… What we're going to be saying  is that there is some column… Yeah. …where this bit really is flipped. I see. Right? So they actually… Before we said if there was 1, then we could extract. Right? Yeah. But there didn't have to.

Now there must be 1. Okay? Yeah. Good. All right. So now… So we did this. And so now we know that there is some s. So what we did is we extracted some  A times S bar, which equals to T. Because we do this extraction for every position. Okay. Right? And this S bar was this z minus z. Yeah. So this thing of having 2  columns that are flipped, we apply that to every position.  Exactly. And that's our S bar matrix. And we extract… Right. We apply it to position  1 through m, and we actually extract our S bar.

Okay. Okay. So now we can  extract A S bar equals T. Okay. And now we're going to claim… So this S  bar is not the same as the s, but it's something. Okay. And now we're going to claim that this  z, right, this z must be S bar times c. Okay. Okay. So my claim is that z, claim,  z equals S bar times c. Okay? And the reason for this is that we know that AZ  equals TC. Right? And we know that T equals A s.

So we have A z equals A S bar c. Right? So  we have A times Z minus S bar C equals 0. So let's see. We had A z equals A s. So we know  that T is A times some S bar. Right? Sorry. So we said T equals As.  Why do we have the bar here? Because we extracted the S bar. Yes. Okay. Sorry, I was looking up there. As is  something we claim we have, but all we can do is prove S bar. Okay. Okay?

So we substitute AS bar for T and then… Okay. Yeah. So z must be this S bar times c. Yes. Otherwise, we have a  problem with our binding. Exactly. Otherwise, we have a solution to  SIS. Actually, we have many solutions to SIS. Right? Because this is now a matrix and  we have like 128 solutions to SIS. Yes. Okay. So this is small. This is small. And so this is 0. Okay. Good. So let's just remember that  z is now S bar c. Okay. Good. One additional thing that we'll need is  that something kind of obvious is that let's say I want to… So I committed to the s and I also  want to prove that this s satisfies some other linear relations like some B times s equals Y. Okay. So let's say I want to also prove that Bs equals Y. Well, this is pretty simple, right? All we have to do, the verifier just has

to check that Bz equals Yc because look  what we have. We have As equals T. Right? So this is what we have. And let's say I also want  to prove that B… I want to kind of append this B underneath the matrix, right? Equals Y. Right? So then I do the exact same thing.  I just do… I send the C, the Z. The fact that the S bar is kind of committed  to, you know, is unique and Z must be equal to S bar C comes from this. Yep. And then  this part is just you check that B times… You just have to check that B times  Z equals YC. Like if you think of… So we are redoing this again?  Exactly. But for B and Y.

Exactly. If you want, you can  think of A and T as like being like this is now A and this is now T. Right? And we've extracted… Yes. …the exact same thing. It's just  the top part is needed. You know, at some point we have to argue SIS, right? Yes. So here we need this to be random. So that's… We can argue that,  ah, there really is a unique S bar. But this part can be whatever you want. It doesn't have to be random. Okay. It doesn't… Like once you've established that  there's this s, the extraction… You know, the fact that B times S bar satisfies Y is  exactly the same extraction as here. Nice. So… …we can commit to… Yeah. So we've seen a commitment scheme. Right?

We can commit to something that's m ^2 size  and kind of the commitment size is 0 of m. Yeah. And we can prove that we know some  opening, right? It's quite large. But something… But we haven't  really proved that the norm of s is something small, right? We did prove… We do prove that the norm of s is, you know, not too large, right? It's like m… Yeah. It's small with respect to the SIS problem. Yeah. But it's not really as small as we claim. SIS Let's say if I wanted to prove that the norm… You know, this was binary and  I'll prove that the norm is really like… I guess m. Yes. If H coefficient  is m, this doesn't do it because this proves that each coefficient is m. This is not quite what we want. Okay. Okay.

So now we're going to use this kind  of to move… To prove that… To prove like this tighter relation of the norm. Okay. And the way we do this is something… This idea, I mean, it's kind of… We've been building up to it and now we kind of just noticed that, ah,  this is actually what we've been doing. Mm-hmm. And we're kind of calling it the  left-right technique or left-right proof. Okay. And we'll kind of see what… See why  it makes sense. So this is kind of… This is the proof on the right side of s. Right? Because we're multiplying on the right. On the right. And now we're going to try  to do something from the left side.

Now that we've established that Z is  something, we're going to try to prove something about it from the left side.  Okay. And you'll see why we can't just work with one side and we have to have both. That's it. Okay. I think now we're actually ready to present the full protocol. All right. So let's leave… So let's just remember what we can do here. Yeah. Right? And I'll remind you when we get to that part. And… Okay. So just our statement is, right, that we have an S, we commit it to S, that AS equals T. And also we want to prove that the norm of S… That's actually the norm of S^2, it's easier. Okay. Equals some Beta.

So what do we mean when we say the norm? Yeah. So… Right. So the norm of A, the norm of this  matrix, it's not really the matrix norm because there's a notion of that. Here  I just mean simply the norm of all the… kind of the sum of all the norms of all the  vectors. So, for example, if the coefficients are of this matrix are like, I don't know,  like A1, A2, A3, whatever, then it's just A1^2 plus A2^2 plus A3^2, et cetera. Okay. So, for example, if we treat, you know, these are vectors, right? Then it's basically norm  of s ^2 is the norm of S1^2 plus the norm of S2^2. Okay.

And then the norm of a vector would be… The norm of a vector, if the vector like S1 equals  like A1, AKM, right? Yeah. It has m coefficients. Then the norm of S1 equals A1 ^2.. Okay. Okay. Okay? So it's just the… The sum of the squares. The sum of the squares. Okay. And I  guess importantly for the next step is that here these S's are columns, right? So we're going to be treating the… We're looking at this vector, a matrix S. We're actually looking at the rows. But it's the same thing. The norm  of S ^2, since it's just the sum of the squares of each coefficient, it's the same. It'll be the norm of the row ^2, reverse row ^2

plus norm of second row ^2, et cetera. Okay. Yeah? It doesn't matter how we split, right? Okay. So we'll be trying to prove that this equals Beta. Okay. And… Just a quick question. Why do we have the norm ^2? Why do we have the norm ^2? Oh, because  the norm would be the square root of this. Okay. And we don't really want to take  square roots. Sounds good. Right? Yeah. So, yeah. For convenience, I guess, or… Or because we actually don't… Because what we actually know how to prove  is the norm, right? Okay. So something also to notice, right,  that the norm of like some S1 ^2 is… You can think of it as the inner  product of S1 with itself. Right?

Which is just notation for… Just if you  take a vector and you do the inner product… Inner product element. Yeah. You just multiply this element. Right. So like you have S1 times  S1. Yeah. Transpose, right? Yeah. Then it's just… Yeah. So you do the sum of the squares. Yes. Exactly. All right. Good. All right. So I'm going to start the protocol from step 2 because step 1 kind of will be clear  what… When we get there later. Ah, this is what's missing and that's going to be step 1. All right. So… So maybe we can write 1.

Yeah. Leave it there. 1. question 2. Is the verifier, so I'll just write V, sends a random… Sends lambda, random lambda in Zq. So just an integer in Zq. Yeah. Maybe you can Zq * so 0 is  not included. Sure. Unlikely to happen that we get 0. Well, q is not that large, right? q is like 2 to the 32. Okay. So maybe you should… Okay. But okay. And now the prover computes, so what  I call U+ and U-. Okay. So now U+ is… So let's write it here. U plus is the  sum from i equals 1 to m of… Okay.

So now we need some notation for, like I  said, the rows of S. Right? So I don't know. We can call them like S squiggly.  Sure. So S squiggly is the rows of S. Okay. S of i times lambda to the i.  So lambda to the i times the row. So we actually sum up the weighted sum of  rows. So the first row gets multiplied by lambda. The second row of lambda ^2, etc. Okay. Now U minus is i equals 1 to m of lambda minus i. Yes. Okay. Okay. Why are we doing this?

Because… So now notice that  these are just vectors. Yes. Right? So now we're going to take  the inner product of these vectors. You notice that U+ U- is… If we do the multiplication… Yes. So now let's… I guess we can write it out, right? Well… Lambda  i times lambda minus i times S squiggly i. Yes. So like… Yes. It's a bit annoying to write out. Okay. But we only  care about like some important… Here's the important thing we care about.  That… So we do this product, right?

So now for the i… For the same i's, the lambda…  The powers of lambda to the i will cancel out. Yes. Right? So we will have something  like sum from i equals 1 to m of Si. Right? We will have this. Yeah. Because the powers will cancel out. When they're equal. Then… Now, what are all the possible powers of lambda? I mean, I guess they  range from like m to… - m to m, right? Plus sum from negative m less than or equal to  i less than or equal to m. And then i is not 0 because the 0… I equals 0 is kind of… The power is covered here already.

Yeah. Right? Yeah. We have… You said it was  easy to work out. No, no, no. No idea, right? Yeah exactly exactly. It's something, right? It's like maybe like S…  You know, the power of lambda to the 1, right? We'll have like S2 and with S1,  right? With S1, right? Yeah. And then also S3 with S2, right?  So something, right? But basically something that we don't care about. Right? So let's just call this some… This is some function of S1 through Sm Okay. Right? Times lambda to the i. Okay. And I guess gi… gi, yes. It's going to be different one at a time.

Yeah, yeah, exactly. Thank you. All right. Cool. So we will have this. And now the  important thing is notice what this is. This is exactly Beta, right? Right. Because  we're taking the inner product of the first row plus the inner product of the second  row plus the inner product of the third row. And we said that the norm ^2 was  the inner product of the row itself. Exactly. Right. Exactly. So sum of all the inner products,  that's the norm of S. Cool. Okay. So that's Beta. Yeah. And this  is something we don't care about. But the important thing is the number of these  terms that we don't care about is like 2m.

Okay. Okay. So it's not as big as our original matrix. Exactly. It's not m ^2. Exactly. So what we're going to  do is we're going to send in the first step all the gi to the S1 Sm. Okay. Okay. So I guess maybe you see where I'm going. We'll be going with this, right? At some point, we'll prove that actually what we have is this, right? Yeah.  Which implies that this part must, that the inner product norm of size must be Beta. Because this is basically short, simple.

Yeah. I was going to say, we see a  polynomial here happening. And we see, I guess, 2 ways of computing it, right? With these guys or with the claim and the g’s? Yeah, exactly. So these guys, right. If we can  prove that these guys are somehow, you know, actually the S’s that are committed to here. Yeah. Right? Then we have proven that, and if we've proven that this is like Beta  plus lambda to the i, then we've proven that this part really must be Beta. I guess I'd see how it unfolds.

Yeah, we can get to that. Yeah, exactly. But that's the kind of the,  I guess maybe you're seeing it, right? Because the lambda to the i is the X, right? So we have some polynomial in X. Okay, good. Okay. So the intuition is, right, if we know  that this is already somehow related to S, right? These U + and U -. Yes. Then we can prove. But we don't know yet that this is related to S. Absolutely. But this is actually what we've done in the first step, right? So let me just notice something  here on the notation. I'm going to write this. Notice that this is, I'm going  to write the vector lambda, vector lambda, which is just lambda,  lambda ^2.. Oh, sorry. Lambda to the m.

And like lambda - is just. So this is actually  lambda times s. And this is lambda - times s. Just notational. I did nothing. I just sort of wrote this as  a matrix vector. Maybe we don't even care. Okay. So now once we did this, now we  have to somehow prove that, hey, actually, what we were doing before was like this S  somehow is connected. To the U + and U -?

To the U + and U -. Exactly. So then what we  do is that the verifier, I guess, and sends it. Yes. I guess implicit to. Yeah, yeah, yeah. I've been writing send here. But yeah, just to make sure. Okay. So the verifier sends. Now we're doing this  thing that we saw before on the right side. AS equals T. Exactly. Sends C from like this 0,  1 to the. We said 128 or something m times 128. Exactly. Something like this. And the prover sends Z equals SC. Okay. So now the verifier has to perform a bunch of checks. Yeah. Checks. Okay.

(a) So he has to check that AZ  equals TC. That's from our previous. Yeah. So that. Okay. Right. (b) He checks that lambda times Z equals U + times C. He checks  that lambda minus 1 times Z equals U- C. Okay. Let's see. Then he checks this thing. That. This here. That U.

That U + with U - equals Beta  plus sum of lambda i gi. That's 1. Okay. Right. So the first 3 things establish that Z really is A. So that Z really is some S times C. Some S bar. Some S bar. Exactly.

Some S bar times C. Right. And now. And this last part. And also that S bar satisfies lambda times S bar is U +. U +. Lambda times S bar is U - So is this sort of the linear  constraint thing you were showing us. Exactly. As well. Okay. Exactly. And this would be our B. Exactly. Exactly. That's why I mentioned that you can actually  just for free prove a linear. Any linear relation you want. So we set up the  linear relation we care about here. Yeah. Right. We prove that this S  satisfies it. So now we know that. That lambda S. Lambda times whatever S we  extracted from here is really U +. We know that lambda times this S bar equals U -. And so now we do this inner product.

Right. So whatever we committed to. Now it's inner product is  Beta. Yeah. Plus whatever. Yeah. Right. So now is it kind of. Now is it. Now do we see why this implies that  the norm must be Beta. Right. Because. So if you think of this. This is some  polynomial in X. So if you write like f of x. Yeah. Like what the prover does in the  beginning is he defines this polynomial. By sending.

Exactly. By sending these  terms and the Beta. Right. Yeah. So you wrote equals like Beta.  That's the constant coefficient. Plus sum of whatever: -m less than  i, less than mi not equal to 0. Of X to the gi of.… Yeah. All these coefficients. Yeah. Yeah. Exactly. This is a coefficient. Yeah. OK. The only question I have is: Is this still  a polynomial when we have negative powers. Yeah. Because you could always multiply by X to the m. I see.

Shift everything. Yeah. Exactly. As long as X is not 0. If 1  is satisfied the other 1. OK. Is 2. Sounds good. Yeah. You just multiply. OK. Yeah. So all we care about is the number of solutions to this. I hope. I hope that's right. Right. So we have this. Whatever. Polynomial. Polynomial. Yeah. I don't know. So we have this f of x. Is this. And now what we what we've  implicitly done here is we've said we've evaluated this polynomial at some lambda. Right. And we said f of lambda. f of this lambda.

Yeah. Is this. Yes. So then we're saying  it must have been that polynomial. Right. But like. Maybe not. Right. Yes. Maybe there was another polynomial. Maybe I. Maybe the correct  polynomial is something else. Right. Maybe. And it just so happens. Equals. I don't know. Something. Yeah. That's not this. Anything  else. It's not equal to f of x. Right. That's how we write this. Yes. Yeah. It's not equal to f of x. Right. Right. And maybe it happened to be that f of lambda. Is. Equals F' of lambda. Yeah. But of course then this implies  that f minus f' of lambda equals 0.

Right. So if we subtract them  off. It's another polynomial. Yeah. f'. So now we have this polynomial  f minus f' of lambda equals 0. But this cannot happen too often. Right. Because  the degree of this f once we kind of shift it. Right. Is 2m. Yeah. And the same thing for f'. And so. The probability of this thing being  the 0 polynomial is very. Or sorry. The probability that this is non-0. Exactly.

And that's lambda equals 0 is very low. Exactly. So this is our third zipple. Exactly. It has at most m roots. Yeah. Right. Yeah. So it has 2m roots. So the probability that it's. Lambda is one of those roots. This is one of these roots. Is 2m over q. Yeah. Okay. So if q is not so big you will have to repeat it a bunch of times. But this is. I don't want to talk about that too much. Because. Sure. This is the integer. This is over the Zq. And we don't really do that. In. Okay. For efficient things. Okay. So now. That's it. That's the protocol. That's it. Are we done?

Did we prove what we wanted?  Actually. Before we get there. I had one more question:  Which is when we did this. The version with just AS equals C. The verifier in the check needed to check  that the norm of Z was small. Ah yeah. Do we still need to do this here? Did I forget this? Yes I did. Okay. Thank you. Checks that the norm of Z is small. Okay. Sorry. Thank you. Then all good. And then to your  question. Does this solve our problem? I guess if you're asking. It means no.

Right. Yeah. So. Almost. Right. But actually. There is this  one part. That seems like. Wow. It's obvious. But it's  actually a little bit tricky. Right. So. Because I. You know. Maybe because I dropped the notation. So I dropped writing mod q everywhere. Yes. Right. So notice. Everything. Is mod q. Here. So what I've proved. Is that. Basically the sum of SI. Yeah. You know. These inner products. The sum of them is Beta mod q. Okay. Which is not the same as Beta. Right. Because. These SI's could be.

It could be q times Beta. Or  2q times Beta. It could be. Sorry. It could be Beta plus Kq. Okay. Right. Exactly. Yeah. So that's not exactly what  we want. Right. So then. Like what do we do? I mean. Here's the issue. We prove that this is exactly Beta mod q. So it's exactly Beta. Right. It's exactly Beta mod q. But maybe it wraps around mod q. So. There are. There is. From looking at this there's a few  things, a few ways to solve this. The first thing you can say. Is the okay. Remember. When we proved. What this S bar was. Right. When we extracted. We said.

Every coefficient is not much  bigger than… is not bigger than m. Or something like this. Right. Yeah. So now every coefficient of S bar is not bigger than m. Okay. So then. Maybe now you have the. The inner product. Now it's m ^2. Yeah. Right. Now you sum up this time. So you can somehow compute what is the  maximum this can be in terms of m. Right. Right. And as long as that  maximum is smaller than q. q. Exactly. We know there's no wraparound that happened. Okay. Okay. So that’s one thing. Right. That'd be very  restrictive on the size of m.

Or that make q have to be a lot bigger than m. Exactly. So here with q. Would have  to be like m ^2 times maybe another m. Because we're summing up all of these  things so it's actually quite large. Right. I think because this extraction  that we had before its a bit too loose Yeah. Right. So there's another thing that we've been doing. This is a technique we've  really using that’s been very useful in lattice based proofs is the random projection method. Like  the modular version of Johnson Lyndon Strauss. Yeah. Like from Statistics. Or from. Ever seen this?

No. But I'm sure the whiteboard  is a good place for this. Yeah. Yeah. Exactly. So let's. Let's erase this. We don't need this anymore. So let's forget about. I mean. This is just like a math fact. Yeah. Sure. We can also switch sides. If you want. We can also switch sides, if  you want to write on this side. No. Okay. I don't think I'm blocking anything. Sounds good. So let's just say we have some vector s which is long. Right. So s is in some Z to the m. Right. And I want to prove to you that, or  at least, I want to convince you that s is small. Yeah. The norm of s is like  something small. So what I can do, is I can create a random projection of s so I create. Random matrix R Let's say it's like even negative.

Or you can have a Gaussian Thing in here like  normal , something from normal distribution. But if you want to be discrete what  we do is we put negative 1 0 1. With like, you know, this is  like 1/4th 1/4th 1/2 probability. Okay. So just a random matrix. Negative  1 0 1. Let's call this R. We multiply by s. Is there a reason why we  choose that sort of randomness. Or that shape for r. Because it’s kind of like a Gaussian. Okay. And normalise. Yeah. It's just convenient to. Okay.

I don't think. There's any advantage  to taking bigger numbers. I see. Okay. And then. We have Rs equals to t. So now, this let’s say is only 256. Dimension 256. And this is. You know. This is quite large. This is our m. Yeah. And. What we're doing. And why it's called projection, Random projection. Because we're taking a vector of dimension m. And we're projecting it down to dimension 256 using this random…. And this part is random. So this is a random projection. Okay. And now what. You can actually fairly easily derive if these were the normal distribution.  Is that the norm of t is very much related to, is very concentrated around  some scaling of the norm of s.

Okay. So basically. If this norm of t which is a  much smaller dimension is something. Then you can conclude that the norm of s is the scaling  factor times that, ou know… within a factor of 2. So when you say concentrated. We  mean. Sort of the probability. Like. Is there some sort of…. Yeah. Exactly. There is a probability. Yes. Okay. Yes. There's a probability over r. Right. Okay. That. So the probability over r hat the norm of t is somehow outside this  tight bound…depending on norm of s is like exp1ntially small. Okay. Okay. Okay. So.

And so. The important thing is that this  bound is now like a factor of 2 or 3. Or something like this. From each side  it's maybe a factor of 4 then totally. So once you have t you know exactly  norm of s within a factor of like 4. Or something. Okay. From up and down. Right. Okay. And now. That's. So now that is a much tighter way to bound he coefficients of s than what  we had before. Yeah. The sort of m ^2. Yeah. Exactly. We don't have this anymore so all we have  to do: For example, 1 simple thing hat we can do is jus do another linear… Now  the verifier can choose the r somewhere. Right. And we prove to it and we send the t. And we prove to it that r s equals t.

Because we already know how  to prove linear relations. Okay. I guess. I was going to say here. Again. We could have r here. Yeah. Okay. That's something we could do.  So that's. Or you could also. Maybe a little bit differently if you wanted to. So this would prove that each column is… Yes. Right. We can also do something …Matrix  like. Yeah. We can do it for each row for example. Something else to notice, but this is…  Sort of. You didn't even want to mention this because this is super special to the integer  case, which will not happen in polynomials. Is that this C, now it's 0 1. But what if you made it -1 0 1. Can it become our R. Exactly. The C can become our R and kind of serve 2 purposes. One to make a commit, to kind of be

the challenge. The commitment. And the other  one, is actually to prove a tighter bound on s. Okay. Right. So this. But we don't do this. In the polynomial case. So this is kind of like this thing that  just shows up in an inefficient constructions. But like an efficient ones we wouldn't  have the chance to use this. It's too bad. But yeah. But yeah. But anyway. But this. But basically random projections is the way we prove we prove things that are…. Yeah. We kind of. Prove. That there's no wraparound. So. So random projections. Right. It's almost as good as this. Right.

We're saying because we can prove the norm of s. Is quite concentrated. Right. So maybe. You would say. Oh. Maybe. You don't even need this. And in some cases  maybe you don't. Right. Maybe it's good enough. This d check. Yeah. Maybe you don't even. You won't  even need something like this. But random projections.… It really depends. Right. But basically in some schemes, for example, in the standardised signature scheme Falcon, you  really want the norm to be less than something. If you allow the norm to be like 4 times as big,  now you're losing about 20 bits of security. You know. 50 bits. Okay. I don't know. So maybe then you have to change parameters and the…. So. If this is not very expensive then you might as well do this. Or if you really need  this, you might do this. Maybe in some situations,

you’re not just proving norms. Right here I was just proving norm. Maybe you want to prove some relations  between some quadratic relations. And there, you really kind of need the right proof. Some exact. Well. Here's just integers. But yeah. Maybe. Yeah. Maybe. You're right. Maybe I want to prove some quadratic relations there  I really do want to prove that it's like B. It's not the norm doesn't really have any meaning And so here, we’re proving a quadratic  relation, but specifically on the square. Right. Exactly. Okay. Yeah. This is a very specific  quadratic relation. Right.

This is the quadratic,  which are actually the norm. Right. But we could have , for example, had  a commitment to s. Had another commitment to something else and prove that the  inner product of s and s’ is something. Right. Maybe that has some meaning for something.  Right. And then it's not really the norm. Right. So it's not like. Oh. But the norm is. Like. Well. We don't. No one cares about the norm. That's  not the meaning of what we're proving. Right. So we would still need to prove this approximate  norm. To prove there's no wraparound. And then we would prove some inner product relation  which it's not like a norm relation.

So we actually do need the exact thing… Maybe. Some circuit. Maybe. Or something like this. Right. So we really do want it to be some specific  value. Not just smaller than something. Yeah. I have a couple of questions.  For you. Maybe a bit more. So the first one is: Are we saying “Left - Right”  because here we have this left multiplication and here the right multiplication. Cool. Then the  next question was: Why are we using rows of s. Why are we using rows on the right? On the left. On the left. Yes. Is it just how.

That's just how. The rules of matrix multiplication. Yeah. Yeah. That's just how it works  out. So actually. If you think. So what we're really doing. Is we're  really proving things about the rows. The columns thing is just to  prove. Like on the multiplication. The right is just to prove that there's  a commitment to s. Right. Now you might, you might ask: Okay, why did we need to do both? Right. Why not? We have this SC. Right. We could have just. You know. This SC is just some…. You know. We could have made  C like lambda or something. And we could have summed up the columns. Right. So this would have been exactly this, over the columns. We could have done a  multiplication. The problem is that for lattices you need things to be small. Right. So this C had to be small.

I see. Right. So… so C being small  allows us to prove the linear. The commitment. That this was a commitment to s. And once we know it's S or S bar. Whatever. It's unique commitment.  Then we can play around. We can multiply whatever we want. Right. As long as there’s that commitment… is already there. Right. You could also say. Okay. Okay. Fine. Make these small. And now you can still write. So this wouldn't be Lambda i… Lambda to the i. This would be like C sub i, C sub i So you could just. This didn't have to be powers of Lambda. Right. This could be anything you want for short… the problem there is that  the nice thing here: Why? Why is it like this?

Because these powers, they all  kind of cancelled out. And they all became in the role between m and -m. Right. Right. Whereas if they were just distinct C's. You would have all m ^2 possible combinations. I see. And now. You have a lot more cross terms. Exactly. Now you're back to. m ^2. Right. I mean. Maybe you could make some progress. Like. Okay. Before you started with m ^2. Now you have m ^2 over 4.  Sure. But you know in practice. It's not enough. This is not what we. You know. Yeah. Probably not enough. And this is. Yeah. I really want to go from m ^2 To m. The last question I had is. You often  mentioned here we're working over integers.

But that's not usually what we want to do, that  there's more efficient ways to do things. Right. What are those ways? Yeah. And  do we have time to talk about it? Yeah. I think we have time to  talk about it. But maybe before answering this question: I want to  just say one more thing about this. So. So this gets us a square root. Yes. Right. And notice that the verifier time is also efficient. Because the verifier doesn't work with anything that's m ^2. You only work with things that are size m. Okay. Or a constant. Yes. Constant times m. Exactly.

Right. So. So. But we may want to make the proof even smaller. Right. Yes. So then we could either maybe repeat this itself. So it's kind of… it's pretty similar to a folding scheme. But we kind of we don't think of it in those  terms. We actually want to build a full SNARK So you can either do this. Or we think what's  more efficient, is to feed this into like a very compact scheme, that’s also a lot  of space. Like Labrador. Or there's also Greyhound which is about polynomial evaluations. But maybe Labrador kind of makes more sense here. The problem is that Labrador is linear time  verification. But since we already got square root here, maybe in practice, it doesn't really matter. Maybe you do want to repeat this once.

Maybe you don't. One more time. Maybe you don't. But I think in practice: maybe just feeding into something that's  very compact, at this point, is good enough. So that's something we do. And of course, we  also care about the prover time. Yeah. So, the most expensive thing is to  compute this thing, this product. Yeah. Right. And now. The naive way. Right. is just to do it is just to multiply them out. Right. But each of these. Each of these individual terms.  Right. This is the vector of size m. This is a vector size m. So that's like m operations. Right. And if now you have m, more of these.

That's good. So m. Yes. We do this m times. Yeah. Like each … This is like a polynomial side degree m. Polynomial degree m. Right. You multiply it. Now you can have like m ^2 time thing. M ^2 operations of m things. That's m^3. Which becomes, Which is bigger. This is more than linear. Right. If m m ^2 Is our linear thing. That m^3. Is like. To the 3 halves. Right. Yeah. So we don't want to do that. Right. So like this is unavoidable. Right. Multiplying  these 2 together: Inner product. That's going to be m. Yeah. But the polynomial product that we can do using, NTT or FFT. Right. And that'll be m log m.

So then we'll have m^2 log m. Okay. Prover time. Okay. So that’s… Yeah. I think that's kind of. Yeah. I don't know. Unless yo want to ask something. Before we talk about rings. But  maybe before we talk about rings. Let's just understand what  the inefficiencies are here. And what we may want to improve upon. Right. So here's one inefficiency. Right. Is that this C was 128 rows. Right. So now. We are. Okay. It's a constant. But it's 128  so that’s quite big. Columns. Right. The number of columns is quite big. And the reason we need 128 columns is because, remember like, whenever we were changing one  C, if it was just 1 column, there’s only, there’s a 50 percent chance of the  prover cheating. So there's no reason.

So if we could somehow, if  the c were not integers. If there were some bigger ring or field. That would be better. Okay. That's one thing. The other thing, is that these lambdas. Right. The lambdas are in Zq. And I don't think, there’s anything you can do. Obviously, Right, Because. This is in Zq. This isn't the  same as polynomial in Zq. Right. So now, because q I said, it was like 2 to  the 32. Now you're going to have to repeat. Yes. Actually. We want more  than 32 bits of security.

Right. Parallel repetition, maybe in this  case is not as trivial. As just repeating because some things may go wrong. So that’s also,  that’s an issue. So even if you could repeat, you’re still like doing this for 4 times. I guess the other thing is that this matrix A. If this matrix. But that's just your commitment scheme. A. If this matrix A is really an integer,  Matrix Multiplication is expensive. If we could somehow put some structure into  it, we could have cheaper multiplication. So using, Polynomial rings. That's what we use  in lattice cryptography,. I have been using it, Since ’96, when the Entry Encryption Scheme  introduced lattices & Lattice Encryption using over polynomial rings. Yeah. Just the rings  themselves have changed. But the idea that rings

are useful has kind of endured. Okay. So what do they look like. So let's. Yeah. Erase all of this. And just do a little bit about polynomials. So polynomial rings we use in lattice  cryptography are usually of this form. I'll explain what they are. But we write like Rq  equals Zq, adjoined X. mod x to the d plus 1. And this d is a power of 2. Okay. Okay. So.

What is this and why? Yes. Yeah. Okay. So what is. So first. What is Zq[x]? So Zq[x]. Are just polynomials. So Zq[x]. Is just the set. a 0. Plus a1X. Plus a2X ^2.. Where X is your indeterminate.  We're not plugging anything into X. And our a’s are in Zq. The coefficients. The coefficients are in  Zq. Exactly. a's are in Zq. Okay. So now adding polynomials together,  we just add the coefficients. Easy.

Multiplication. I mean. Doable. Okay. I mean. We've been doing. We did this before. Okay. So  multiplication / addition. Okay. That's this ring. Now this mod x to  the d + 1. Well, this is actually not much different than what this q is. Right? So if  you know what mod q is. Every time you see q, you just make it 0. Yeah. You wrap around. So basically q equals 0. Yeah. And here I'm just saying x to the d equals minus 1. So x to  the d plus 1 equals 0. Okay. x to the d minus 1. So whenever. Let's say you multiply 2 polynomials. And now some degree is bigger than d. That x to the d becomes -1. So for example. So if you had like. The 4th. And d was 4.

Let's say d equals 4. Yeah.  Then this a to the 4th. Yeah. Becomes - 1. Becomes a0 - a4 + a1x. Yeah. Okay. So. All the polynomials in this ring are  really all just have coefficients in Zq. Yeah. And of degree less than d. That's it. So when you add them, you just add the coefficients. There's no, never. And you wrap around x to the d when you multiply them. Yeah. You're going to get x to the d.

So you have to bring it back. Sounds good. Okay. So. And now just kind of understand, why did I say power of 2. Because for security,  we want this polynomial x to the d + 1 to be irreducible over Z[x]. Okay. So basically,  you cannot factor x to the d plus 1 over…. So it's irreducible. Yeah. Yeah. And it turns out that x to the d + 1 is only irreducible if it's power  of 2. Now it could be completely splittable mod q Zq[x]. It depends on how you pick it. But for security, we really need it to not split over Z. Yeah. Over Z[x].

I'll take your word for it.  Like I don’t see the intuition. No. No. It's actually very…. I would say it's very surprising. Right. It's okay that it splits mod Zq. Yes. But it's not okay that it splits Z[x]. And this is. This was. You know. Just a historical thing. Just the one of these big kind of things that came  out of these worst case to average case reductions where you, even though they're completely like  per parameter setting, they’re completely useless. Right. What they did say is like. Ha You know. Actually you can prove that lattice. You know. This SIS…. Whatever SIS over polynomial rings, learning  with errors, which is basically like in… So polynomial rings is hard whenever…  at least we can have this reduction.

Yeah. When. This is. Over Z[x]. Wow. And. But not. When it’s… It just fails. It just doesn't work. If it's  not irreducible. Or it's weaker. Much weaker. But Zq it's kind of  like set it to wherever you want, that’s not part of the reduction. Part of  the reduction doesn't care. You can set. Which I would say. Is very surprising. Is very  surprising. But that's kind of the big utility that came out of those reductions. That you say. Okay. Actually q doesn't matter. And we try to apply the same attacks, like  when things split. When they split mod q, they don't work. And there  is some mathematical reason I'm sure. Yeah. Yeah.

But it's very. But now, we kind of  know that this was this scaffolding. Right. These Security Proofs here’s the thing  you want to work with, now set the parameters. Now we don’t care about these worse case problems,  we just use these average case problems that these worse case problems gave us and the parameters Because having worse case problems, its kind of useless. Like what is the  worse case instance. How do I know … With average case its much easier to work with. But I digress. Proofs were important. So now, the SIS problem. Over the rings.

Which we call module SIS. And this  is actually what the standards like Kaiburn and Lithium are based on. Is a very similar before. Right? So now you have A, which is a random matrix  in Rq to the n by m, but now n does not have to be 512. So what we care about is our n times  d has to be the same kind of dimension as… has to be this 512 or 1024, right? So before the  security parameter was n now it's n times d.

So if you're in here, you  know, this d is like 256. So here, correct me if this  intuition is wrong. So A, every element of A is  actually d coefficients. Yes. Right, so now d times n needs to be big and  not just n right? Exactly, exactly. Because d times n is the number of coefficients. Coefficients, yes, exactly. Yeah, it's cool. Okay, and then we have our S, which is  in R to the m. With norm of s small. And norm is exactly how you would, you  just over the coefficients. There are some other ways to compute the norm,  but for this ring, that's good enough.

It's perfect mathematical definition. Norm  of s is small. So the sum of the norm of the coefficients is small, just like before. And the part problem is f of A of s equals to, that's the 1-way function, right?  And it's, again, the product A of s. It's defined as, yeah, A of s. Okay. And  then we have multiplication of ring elements. Yes, now we have multiplication  of ring elements. Exactly. Okay. And this gives us efficiency why? Okay, so let's kind of just, we're  not gonna redo the whole protocol, but just kind of some parts of it we can redo.  All right. So again, let's say we're trying to commit to s to a lot of coefficients, and to  prove that the coefficients are small, right?

The norm is small. All right. So  remember the first step, right? We had our, so we divide our A, we still have  our square matrix S. We kind of put the S into, split it up, right? And we get our T. But now these are all polynomial, vectors of polynomials, right? Yes.  Okay, and remember the first step was he sends a matrix c. Yes, the challenge: c And then I send Z equals Sc. All right. So  before, we said this could not be a vector. We had this problem that the prover  could cheat. Right, exactly. Exactly.

Because each coefficient had only like 1  possibility. It had 2 possibilities, 0 or 1. So now here, the big advantage,  and this is why like these lattice space proofs are much more efficient  with rings, is that you could have, because before you couldn't have a lot  of small elements in your ring, right? Because if you're over the integers, you know,  if you want, you know, an element less than, you know, some B, bound B, there's B of  them. Yes. 2B, because it's minus, right? But now if you're over polynomial rings,  the number of small elements is now actually quite large, right? You can have 2 to the d  elements with 0, 1 coefficients. Right, yes.

And you can actually multiply by them,  right? So now your c could be a vector of small polynomials. Right. Right, because now to extract, you would basically change, you would fix  all the polynomials except 1 and flip that 1. Right. And that one has to, now if there's like 2 to the  128 of them, then the adversary, the adversarial prover or any prover has to be able to  reply correctly to at least 2 of them. I see.

Now, there is gonna be a bit  of an issue. We're not gonna be quite extracting the same thing as before.  Because before, remember, we had the c - c ‘. It was always like 1 or - 1. Yes. So then we ended  up with like Az equals ti times, times, you know, so we had Az - z prime = ti (c - c ’), right? And this would be the 0 1. Yeah. Sorry, 1 or - 1. 1 or -1. Yes. Sorry, thank you. But now it's not, and so because it's 1 or minus 1, we could get rid of this and  we said it’s + or - ti. Now, if it's a polynomial, we don't quite get this. They don't cancel out. They don't, now it's just gonna be ti times some

c with small coefficients, but it's not,  we didn't really prove that AS equals T. We proved that AS equals T times C, but that's  okay. Because this, because it still proves that there's a unique s bar that can satisfy this  relation for s small, okay? So basically s bar divided by c bar is gonna be unique. Right? It's not gonna be small, but it's unique, okay? But that's kind of all we needed  from the right side of this left-right proof. Can we always divide by c bar?

We make sure that it's invertible, yes.  So this is important. This is why also we don't want, in the way we do the zero  knowledge proofs, we don't want this. So before we used to do it differently. We used  to put our coefficient, the things we care about, the secrets, in the NTT, in the Chinese remainder  form, when this polynomial split a lot in here and we put all our things in there, and it  was nice because you could do component-wise multiplication. But then we realised, no, this is  kind of not the optimal thing to do because if you split too much, then the c cannot be too big. It is not, the entropy cannot be too large. So we actually now prove things  not in the infinity norm, but we prove L2 norm. And this is,  I will show you why this is, okay.

But anyway, let's- Yes, this sounds very  advanced compared to where we are so far. Yeah, a little bit, yeah, kind of a- Looking  ahead for those who want to. Looking ahead, yeah, looking ahead. But yes, very good point. You must choose a c so that the differences are invertible, right? Okay,  so then from the right side, you still get a commitment. You still get like,  yeah, there is a unique s, so that AS equals T, where it has this properties that like s  is small and then s times c is small, okay? Okay, good. We have this. It's going  to be a little more difficult to prove that z really is SC, but that can be  done once we do actually the right.

We would have to do something, a little bit  something else. That's no problem. I mean, it's, okay, something, but yeah, it can be done. The thing about the multiplying by lambdas, that's kind of almost completely for free. You get  a bigger lambda because you can use a bigger ring, right? But now the question is, the question  is like, what are we actually proving? If you remember before, we were  proving the sum of like Si times…. Yeah, this inner product with itself.

This inner product we proved, and then we proved  that this was some Beta, right? Where Beta was an integer. Now this is a bit different, right? Now these are polynomials, so we're actually proving polynomial products. Yes.  And it's going to be some polynomial, but this is not what we want. We wanted the norm. We wanted the norm. We wanted this coefficients and now we're  getting this polynomial product. Okay, so this is now the little trick that we've  been using for the last couple of years. And this is why we switched from kind of the  NTT representation, the Chinese remainder representation, to actually just putting  what we care about in the coefficients.

So let's say, let's just make an example. We  can maybe stop after this too. Sounds good. So let's say we work over, let's say d  is 4, just an example, right? So we have some equals s0 plus s1x ^2. plus s3X^3,  okay? So that's our polynomial, right? And we're basically getting many  polynomial products of this form, right? So s times itself plus some other s  by itself, right? Okay, but we want the norm. We want s0 ^2 plus s1 ^2 plus s2 ^2 plus  s3 ^2.. If we just multiply s by itself, we're not getting that. But you actually  can multiply s by something related to it.

So we define this automorphism of s, right?  It's just a way to flip a coefficient, but it doesn't matter. So we define it as  0 minus s3x minus s2 x ^2 minus s1x ^3. So we fix this one. So you can fix this one  and then kind of rotate it. If you wanna think algebraically what this is, this is actually s. So this is S(x), right? This is s of x - 1. Because if you plug in -1 here,  because remember - 1 is equivalent to?

1 over? Oh no, - 1 was  equivalent to…. No, x inverse. Oh, than I don't know. So yeah, so basically, for example,  so x inverse is actually x^3, right? Because like Xx or -x cubed, because x  times what is 1? X times - x cubed equals 1. Oh, yes, yes, yes, of course. So  yeah, or maybe this is a silly way to write it. s of minus x cubed, right? Like x -1 is kind of, I'm writing it because maybe we'll think back of what we were  doing before with these powers of lambda. Of lambda, I see. It's kind of similar, right? So this is actually x to the - 1. So if you plug in x^3, -x^3 for every x here, right?  So now you have plus s3x cubed plus, right?

Yeah, yeah. So this is actually x to the x -1.  And now if you multiply s of x times phi of s, you'll get in the constant coefficient, right? So what are you gonna get? You're gonna get 0 times s0. And  anything that's power 4, right? Exactly, the negative of anything power  4. So now you have s1 times - s1. And then we take the negative of that. Plus s 2. Minus s2. Plus s 3^2.. And lo and behold. Something times x, I  don't care what it is, plus something x^2..

And that's exactly what. Something x^3, yeah. And something x^3. Yeah, plus something x^3. Just for completeness.  Yeah, yeah, yeah, plus something x^3. Not leaving one out. Yeah. Right, so the constant  coefficient is going to be exactly the norm. So all we have to prove is that in the constant  coefficient, so this will be some polynomial. We can fill in the other coefficients.  You know, we can send them ahead of time. Yeah. Something like that.  And the constant coefficient is exactly what we're looking for, right? So, and like this cancellation, right? Of this x. Very reminiscent of the lambda thing. Exactly, exactly. That's what I wrote.

Like the x to the -1, right? Because this would be X to the minus 1. This would be X to the - 2. This  would be, so you can write this as like, no, plus s 3 X to the - 3. -3, right? And this is m. Plus s 2x to the -2. Plus s1. And it would just cancel. And that would be  exactly the same as there, except here we have this, you know, the powers don't, you know, we  can, we don't have like between -3 and 3 because we can actually reduce my x to the 4th + 1. There we could not. But yeah, this idea of things kind of cancelling out and being put in the  constant, the thing you're looking for is in the

constant coefficient. It's the same idea, right? Like we didn't really realise it that way. But yeah, you kind of come up  with this, this, and say. Always in hindsight that we  realise the similarities. Yeah, I'm not sure what to do with the  similarity. Like, but just like kind of knows, ah, you know, it's kind of, you know, it's  just kind of there and nice to know. Yeah, so basically, so we can prove something  meaningful about the norms by proving this. And we're saving quite a bit because  we now don't have this 128 thing and we don't have to repeat because our c,  you know, because our c is just a vector and we don't have to repeat because our  lambda is now coming from a bigger ring.

Yeah, it's not just from q, it's from this ring. Okay. Yeah, and of course the A  is now, that's multiplication, this A times s is also now more  efficient because now you're not multiplying just a random A, you're  actually multiplying polynomials, which is a more efficient multiplication. You're  saying instead of like n ^2, it becomes n log n Okay. So you're saving quite a bit and you  know, all the linear relations you may want to prove if we're proving like  lattice, something about lattice schemes, lattice schemes will be on the, using these same  polynomials, right? So it's already kind of, you're using the same structure. The thing you're  proving has the same structure as your proof.

Yeah. So that's already kind of, there's  no like, you don't have to convert, do any conversion or compilation, right? So that's kind of where we are. Yeah, with the lattice-based thing, of course,  the improvements, of course implementation is happening and improvements are happening,  but yeah, the high level, the birds-eye thing, is this kind of what I explained. Hopefully  it's, at least the high level is understandable. Yeah. Thanks. So to summarise kind of the  session, we saw hard lattice problems. The SIS problem. We saw how to get commitments out  of it, the Ajtai commitment. Then we saw this AS equals T sort of proof of knowledge  that I've committed to something.

Correct. We saw why having just a small  challenge was a problem. So we had to take these multiple columns of challenges. That's only for the integer case. Yeah, for the integer case. Which will not happen. I'm just citing here, I guess. Yeah right. Then we looked at how to get a tight  bound on or prove a specific norm for s, the s that was extracted, with  this left-right technique. And now we've looked at like how to make all  this more efficient with rings. Yeah. Lovely. Yeah. Thank you very much Vadim. Oh, my pleasure. Thank you, Nico.