Lattice-Based Zero-Knowledge (Muhammed Esgin - Monash University)

Transcript

foreign welcome back to another edition of ZK Study Club uh today we're really excited to have Muhammad esgan uh joining us from Monash University and Muhammad's going to be talking to us about uh some post Quantum constructions or zero knowledge and blockchain uh applications so uh with that over to you Muhammad before zeros um thank you Alex foreign okay so I'll just find this and yeah today I'm going to be talking about kind of like two things like with some introduction to a lot of

space you know this proof so I'll try to tell you a bit about some challenges there and I'll also talk about this uh protocols family that they're calling Matrix which is a Monero like blockchain by the plane system uh you probably all know about zero Knowles I'm not going to talk too much about that but uh we probably want some formal guarantees from journalist groups like soundness and so on and we want to reveal more information as the name suggests and we usually want to be non-infected and we would require as minimal communication or we would want as minimal communication as possible but on the contrary if you look at install it's going to be quite informal

not going to bore you with the material improving and so on and I would like to be as informative as possible and definitely you can make interactive so please feel good in front of me at any time and we should probably aim to maximize the communication okay so I made Alexa I wanted to make sure the video that the YouTube channel captures my laughter at that joke which I actually appreciate it so uh yeah some outline some as I mentioned I'm going to start with some latency on knowledge Basics so I'm going to assume that you know about zero knowledge proofs particularly in the scriptbook setting and I'll try to sort of give you

some idea on why things are quite difficult to do in the lapis setting which is the post Quantum assumption that we are going to be focusing on today which is one of the most commonly used paradigms in the rapid setting which is basically answering how you would consumer on lattices yeah so after these Basics there's going to be like two parts I'm going to talk to you about our crypto19 paper which is the generalization of this Paradigm and then in the part two I'm going to talk to you about this Matrix family which is kind of like a series of works from ACM GCS and Auckland SMP and public key crypto conference

correct so this slide I think you all would be familiar with so when we talk about the sigma protocol this is like a three move protocol between the approver and a verifier the first phase we often call it the commitment and then we have a challenge phase and we have a response phase and particularly in the challenge space what the verifier does is to sample some random value from a challenge that will really kind of say to the proverb here is my kind of random number random value Now respond to this okay and we typically want 30 properties complete this which means that if everybody behaves honestly then the verifier should accept what the the claim might approve yeah Special

soundness I'm going to talk about that and then we have special honors verifies your knowledge which means that if the verifier behaves honestly sort of samples the challenge properly then the approvers witness no information about the Proverbs witness should be revealed totally verified or anyone who sees the transcript of the communication and we can make this easily non-attractive using the surface directional heuristic which I guess you would also know I'm going to be kind of talking to you as a kind of a more interactive protocol so there are in general two types of pseudonymous groups the first step is called a combinatorial proofs or Stern

like proof and in this setting as a name such as so we do more of the combination of things uh for the the plural kind of tries to run three copies typically of what he's trying to prove and then the program gets challenged on certain sets and then those sets are revealed kind of in the NPC the head settings and then in the rest we want to try something without trivialing all of the uh things that was committed in the beginning and typically the challenge is that it's very small like so there's just three elements and as a result we need to amplify the soundness which means that

we need to repeat the protocol many many times and this leads to talk about this multi-shot proofs as a result we get very long proofs and slow proofs because we are repeating everything all the communications and computations but they on the plus side we can prove really complex places and effectively can really prove what I would want and there is also this so-called algebraic proofs which is more closer to the store type proof and in this case we can make the challenge that very large exponents to the large one so we can make it two to go 256 values and on the plus side we can make the proofs very efficient very short and fast in particular the proof can be one

shot so we just do one protocol iteration and then we get enough sums but on the negative side the types of proofs that we can achieve so far are more limited compared to this certain type proofs but that has been very significant progress in the recent years and another thing that I'm going to talk more about is we may be proving more relaxed more approximate relations rather than the exact one so we never really see relaxation description box I think that I'll tell you what they are in the store and we will be focusing on these later type of tools okay so you know about the Snore so what the thrower does let's call the prover

Alice and the let's suppose the verifying spot uh at least there's some secret value are she composition to the dollar and let's call this reality T is shared with about Alice and we have this kind of public parameter as the generator of the group beside the group G and the Order of the group is true let's say so Alice samples and random value y complete C to the Y and sends it over to the Bob Bob picks a random challenge between two minus one and then LS computes that which is kind of like a response y plus x times R okay so R is Alice's secret X is the challenge and Y is summon asking value okay and what checks whether this expression holds c

times t to the power challenge equals g to percent if that is the case then what is satisfied that Alice is having a product and she knows the discrete law which is r in this case and everyone is said then we can show that this is zero normal and so on okay and if we try to kind of build a lattice analog of this let's try to see how we can do this now the public parameter is going to change it's not a kind of like a generator of the group this is going to be a kind of like a random stat Matrix which means that it has more columns than rows and Alice is going to pick a random Vector r

and uh she's going to compute a to the r and what we are going to get is T Vector okay the the t is going to be shared with Bob and Alice is going to compute a to the Y for a random value Y and this is going to be this new C and we will get the challenge and then we will compute something very similar which is z equals y plus x times f okay so you can see that like everything is quite similar you know just changing kind of like the a bit of the notation but truly we are mimicking what each node does uh unfortunately I get wrong I have a quick question and by the way I am going to uh if anyone has questions that they

type in the chat I will I will just myself unless the person like yeah so that way you don't have to look at the chat but so far if I do have a question and this may be more basic to a lot of space cryptography and maybe some people already know the answer or maybe you're going to get to it later but I guess what's what is the um like with the you use this word the fatness of the Matrix the width like why is it important that the Matrix being used here is wider than it is tall why is it more that it have more columns than rows I guess is that a property that you require in all settings for for these lattices or I guess what's the significance yeah so there are some technical reasons that I'm not going to talk too much

about but the one of the main reasons is that we don't want a to be for example an invertible Matrix if that's the case then if I give you for example a to the r sorry a times R then you can easily inverse both sides uh by a and you can you immediately so in for example if you know about its lwe problem we have kind of like a matrix which might be square that's okay but we also have kind of like an identity Matrix and the identity but gets multiplied by some error and then we have kind of like an A times r or a times S Plus some error and this error is quite important if you don't have the error then you can just do gaussian elimination to get the

secret that you are trying to hide so I'm kind of hiding the error here that's why a is fair so I'm concatenating these kind of real random Matrix with icons to Matrix so that it's kind of like a fat Matrix cool thank you happens okay so so far we just mimics what tuner is doing but unfortunately we cannot really just finish here if I hope we could and by the way this will be verification I miss to say the thing will now you will use the editor notation but apart from that uh it's basically the same sort of doing multiplications and exponentiation we are going addition times scale

multiplication right so the problem here is that to rely on a Lotus problem we really need this is it or these kind of components inside the red Z so to be sure so that we can argue some security okay maybe this is not a huge problem what we can just do is instead of choosing a random R we ask Alice to choose a small uh coefficients in this entry so if you are working mode how this is going to choose values between let's say minus one to one okay and true let's say like a totally spelling okay that's good we can show The Challenge again to be some from a bounded set and we can again choose y

to be from abundance okay so that we can make it short but now the problem is that the zero knowledge is not that easy to argue right because if you choose everything small and if you work mode two then for example a simple setting but suppose Y is chosen from let's say minus 10 to 10 and let's suppose x times R can be between minus one to one okay and if we know that Z is 11. then we immediately know that the only possible value that x times R can take is one right because y is at most ten and x times one can be one and the only way you can get to that equals 11 is that y has to be 10 and x times RF has to be

one there is no other way which means that we are definitely leaving some information right so we need to solve this and the way we can solve this is uh sorry there is going to be a check by the verifier by the way to make sure that set is small which is fixing the smallest issue and to fix this you don't know this problem you are going to use What's called the rejection sampling okay so put simply so I'm not going to import you too much about what rejection sampling does is that for example in the case that I mentioned so for example if Y is from minus 10 to 10 and our let's suppose we sample from minus one to one we are going to cut the Tails of the distribution to a tail to the ends

and then if you kind of if you investigate this and you can even throw this that you will see that in the kind of like the center of the distribution we are going to get again a uniform distribution but in a smaller set if you do rejection sample you reject the ends if that is too big and in the middle part you are going to get a distribution that is still uniform okay and there's also a gaussian version of this but yeah that's more complicated so I'm not going to even talk about that okay but we have the suggestion sampling technique so this is a technique that was well known even before this kind of like lattice based zero knowledge proofs and that's the best crypto in general but uh described how it can be used in this

lattice based setting uh so that we can argue the serial numbers what for signatures as well as okay but this takes is the rejection sampling what we do is so we have this interaction and Alice computes that if it's not an acceptable set she rejects and we restart we pick a new y new challenge complete set check the rejection sampling if it's accepted all good we send that over to the verified okay and this is okay if we if this is a non-interrupted proper protocol especially because Alice is going to control the challenge herself so she can just do all these steps and just publish that that is accepted okay

that follows the correct distribution or the corrected distribution correct now if we look at these properties back again kind of like a Lapis variant of the sigma protocol so completeness we have relaxed completeness right we call it the protocol May restart now in the discrete lock setting it's like kind of like one iteration of the protocol is definitely going to conclude if the program knows the witness sampling and for special assembles now this is more complicated and this is what we are going to kind of discuss in a bit more detail um any questions so far

uh enough nothing in the comments I think folks feel free and chime in if you got questions but uh yeah I think you're free to keep rolling thanks Mom yeah yeah so this is your knowledge and kind of completeness we deal we dealt with them and uh sounds we are going to look at next and to do this we are going to do kind of like some abstraction we are going to move away from this uh kind of Matrix notation and we are going to move into the commitment position okay so I'm sure you must have heard about what the commitment is but it's kind of like a scrambling of a message that can be open later on we are kind of like putting a message together with some Randomness in 12 bucks and then we can open the box and reveal what's inside playthrough and

we wanted to be hiding if you just see the Box you should not know anything about what the message is and you want this to be binding which means that when you want to open the box you should not be able to open it in two way so you said I'm able to uh convince someone uh with two different messages okay and in general we say that and M and R player is an opening of their commitment C if you when you compute the commitment on the inputs M and R we should get but again in the latter setting teams do not quite work absolutely as I just described we don't just have that this C is equal to Commitment of MNR but We additionally want that this pair of the

input values are short which means that they are coefficients must be smaller or significantly smaller than this modulus queue that we are working on okay and in some cases the the just having the randomness short is sufficient but yeah I'm not going to uh too much about that but one part has to be sure and we are going to assume that we have an automatic commitment and it is edited on morphing and we are working over in our and this scalar is uh so this C is a scalar in living which is also true right so let's uh so if you kind of capture the figure that we have in terms

of the commitments this is what we end up with and this is what we call Fiat semi Awards and this is kind of like as I mentioned the standard proof of knowledge in the latter setting this kind of get fixation of the locus analog of rational right so let's see how we can then argue samples which we haven't discussed before so this is what we have and we can do a standard rewinding technique right so we can get two accepting challenges so to accepting transcripts with respect to two different challenges so the first step is the same c0 and C1 and by the way here I'm showing the kind of like the public value as being sent in the first

move which will be come clear why I'm doing this in the next slide but let's suppose we are doing this and so c0 and C1 is the same for both rewind transcripts we get two different challenges X2 and X1 and we get two accepted responses with respect to that so at F0 z0 and F1 Z1 okay and we know that e is expressions are satisfied from the uh verification step and as we would do in the descriptor setting we can subtract these two expressions right C zeros cancel out and onto that we have X than one minus x0 times C1 equals using homomorphic properties commitment to the difference

of the responses okay so far so good and if we were in the description box setting what we would do is we would just divide both sides by the difference right and then we would just get an opening of C1 okay but this doesn't quite work in the laptop setting and we can follow two things okay so this is the expression remember we had before we can try to get rid of this difference right which means that we can again divide as an obesity talk setting but the important thing here is that the inverse has to be short right because it's going to move inside the commitment and whatever goes inside the commitment has

to be shown otherwise we don't get a valid opening but to make sure that the inverse is short we need to choose the challenges in a specific way because in general if you take a ring and then you invert the other one they will very very likely will not be a small value so it's there's a very small chance unless you specify the construct I said there's a very small chance that it's going to be short valid okay and to do this we can choose the challenge set to be just the binary values so that the difference either is one or minus one so the inverse is just itself so the division apparently not doing anything it's just might be negating the expression but that's one

but the challenge set is very small in this case as you can see or we can use what's called monomial challenges uh so I'm not really going to talk too much about that but even in this case the challenge set is a bit larger but still not exponential line so we have monthly a few thousand values so we again need to repeat the protocol in both cases okay so we repeat the protocol therefore we get an inefficient uh communication computation but we get an expression in the end that is kind of either except or closer to exempt so we get something that some Alpha times C1 with some openings and Alpha in this case can be either one or two like in the monomial challenges case it actually

turns out that the inverse is not small but two times the inverse is small that's why you still get this true turn okay but we know what Alpha is in all face it's either one or two it's not an unknown value okay in approach number two we can just be happy with what we have done okay so we just leave this expression in this and we try to get around this relaxation we are not getting an opening of C1 but we are another getting an opening of something times T1 okay now we need to deal with the relaxation and since like 2009 Lewis HD signatures we have been working on how to deal with this relaxation

okay we don't need to repeat the protocol so we get an efficient protocol but we are proving a relaxed or an approximate relation okay and one thing to note here is that we got this X1 minus extra expression in the soundness analysis in the witness extraction that's why outside world when you do the proof they don't even know what is X on minus X2 the value is okay it's part of the Proverbs weakness okay it's not a public value this is again another challenge that we need to deal with correct so this was the setting that we have done and this is the standard Fiat semi with airports and the kind of like

the limitation of this is that it only works for linear relation or degree one license okay so we can see that we are approving c0 plus xc1 equals something so degree of X challenge is just one okay and what we have done in our work is to generalize this Paradigm to the non-linear polynomial releases in the latter setting okay so let's see how we can do this so everything will almost remain the same but in the first form the program is now going to send uh that's on a kind of like K plus one commitments and the verify is going to check that

degree K relation okay so that kind of thing uh sum of x to the i c i where I goes from zero up to K okay and now this expression is what has changed and such a kind of like non-linear relation or degree K relation has been shown in the description box setting to be quite useful for example people head we will disabled one out of n Pros uh they have been used to do this arithmetic circuit verifiability and they are also used in the bulletproof steps you might already know for example we might want to prove that some bits is binary so for this we can put b square minus B is

equal to zero and this you can see is a degree two relation it's not a linear relation okay and the goal here is to extract the available opening of the CK okay it can be in a different moment for a simplicity and the goal that we are going to solve is to extract a useful weakness in one shot so we don't want to repeat protocol for a lot of space okay so I'm going to or we are going to investigate how we can do this and to do this we will look at this K plus one special centers so K is the degree of the relation that we are checking and we are sending K plus 1

commitments in the first one okay so we are going to try to build an extractor the exactly going to take an input c0 up to c k not the set of the commitments and we are going to do rewinding K times okay so we get challenges x0 up to x k and you get corresponding accepting responses F0 zero to fkx okay and they all satisfy the verification so we have this expression satisfied for All Eyes zero Optical and what we want to do is to get an opening of CK as I mentioned before so we know that this Folds

and we can write this as a matrix that consists of all of these challenges powers of challenges and then a set of commitments c0 to CK and this equals the expression on the right hand side and this is going to be over some ring r and we or if I've seen it we might know that this is 1.1 Matrix that consists of these powers of the challenges and this also appears in the descriptive settings so that there is not much difference there but the challenge that we need to solve is this shortness issue that we discussed it and yeah as I mentioned the goal is to recover an opening and we are going to

call this an extract witness so we are trying to find a pair of M and R such that they are going to commit to CK and M and R is going to be shot okay and the naive approach that we can follow is we can try to eliminate this fundamental Matrix and the typical thing that you would do is to multiply by its inverse right and the inverse looks something like this you have some numerator which is naturally important but in the denominator which is kind of the terms that get inverted is these are the problematic terms because when we do the inverse then we are not guaranteed that the inverse is going to be small and we get a problem

and in the denominator we have this product of like differences okay so I'm going to more X that tell me what that is but it's kind of like a product of differences and two things we first want to work them to be what we would need them to be invertible but to make sure that we can even compute the inverse and then we want inverses to be short and to do this in a prior work we have used this monomial challenge approach but in this setting we get a multi-shot proof because we challenge it is not larger okay so we don't get the once approved as we want in the first place so let's go back to our goal so we wanted to do this

but instead perhaps we should relax okay so instead of requiring that kind of like an exact extracted Witness we instead want to find the relaxed opening such that we don't get an opening of the CK but we get a opening of something short times CK okay and you might relate this right in this fiately Edwards paradigm we didn't get an opening of this C1 but we literally got an opening of something times even so we are kind of emulating that setting but generally I think it put it on linear relations okay so how about instead of really inverting

this with one remote Matrix we find another Matrix let's call it V Prime such that V Prime Times V is a scalar in the ring okay and the main thing that we are wanting to do is that this V Prime will not involve any inverse term okay but if we do see any inverses then we kind of have to resort to this kind of like more restricted challenges okay and from a nice results from Nets we can use the so-called educate matrices it's a kind of like a semi-inverse but we're not fully inverting The Matrix but we are partially kind of inverted Matrix at a nice property of this educate Matrix

is that if you take a matrix a you multiply with the edge then what you get on the right hand side is the determinant of the Matrix times identity okay now if we take this V Prime to be the attribute Matrix of V okay and we multiply both sides of our expression like that and we are kind of going to cancel V Matrix but instead we are going to get a determinant of v on the left hand side of the expression okay so on the right hand side you get educate of V times C on the left hand side we get the determinant of V times n okay and if you look at what the

determinant is it's nothing but these terms we have seen in the denominator before okay so it's a pair of challenge differences and a product of these things okay and since the challenges were scalars in the ring their differences that are also scalars and their products are also scales okay so what we end up with is this expression in terms of V times a equals something and from this we can get an opening where this relaxation factor is y is equal to the determinant of the random Matrix okay now we need to look at the quality of the witness

and it turns out in the Latin setting that the shorter the witness then you get a better quality witness okay and in our approach we can support the challenge spaces of this form so it has a specific infinite Norm so the coefficients are bounded I'm sorry I should start with the what the challenges are so there are polynomials of degree at up to D minus one for some parameter d and their coefficients are bounded by T so that between minus P to p and they have a fixed Heming weight that we know by w can you just and maybe you may have

covered this earlier but can you just Define like quality here is that in reference to you know how much security or how efficient or so what the size of the proof will be you could just do Define what quality means here yeah of course yeah it relates to actually everything that you mentioned so in the lattice problem that we are looking at the more you restrict the the the solution in terms of the norm the harder the problem it gets because for example if you respect the norm V1 versus to be 10 then in the 10th case like getting a solution that has Norm 5 is a valid solution but in the one case it's not a valid solution which means

that the adversary in the first case would be the try harder to find the shorter solution than the later case that's why the shorter or the smaller Norm bound to you put into your lattice problem the harder the problem is ah I see you gotcha so it's it's first the kind of secure the purposes of the security argument effectively yes so in terms of security argument shorter known is better which means that you can use a smaller lattice Dimension which then relates to the sizes of the vector that you are going to transmit in the proof guide which then relates to the efficiency cool thank you yeah I have a question as well um so

uh you talked earlier about like um ability to prove uh bind binariness um by uh in that form um yeah and uh okay so it seems like on one hand you can you can prove that by proving some quadratic um relation over the committed witness on the other hand getting this relaxed uh opening and so it's like you're extracting something that might not be um binary right because it's a solution like commitment of some uh what did you use like gamma some scalar times c

um but yet you've proven in the protocol that uh it is binary even though you can't uh extract this and then it seems like the reason you want gamma to be small even though you have proven it's uh binary real message is that um for binding you want you can pick a smaller modulus if gamma is smaller but there's something just I don't know kind of at odds between the fact that that's a great question you've proven that I can explain what we can extract in the binary case for example but that's a very good question yeah that's a very good point so let's suppose we were able to prove something like y

times C is commitment to something right and when we do the binary proof we actually do the analyze the binary setting in our favorites then what we extract is we can prove that this commitment as an opening in the form why times m with some Randomness let's call it r okay and we can actually prove that n is really binary but the opening is naturally exact because we are still proving that it's a con the commitment is y times C but the opening is also y times something binary

with some R which may not contain this y okay so R this R is small or short but we don't know that R over y let's call this R Prime we don't know that this R Prime is also shown okay so we get this weird opening where kind of like the message part is kind of exact because we know that m is the binary but the randomness part we don't know that this is of the form r y times something so that does that kind of answer your questions uh yeah and how big would y be in practice so

what are the constraints on y uh yeah for example if you look at if a if you're concerned with this challenge set the polynomials with uh P bounded coefficients then in the in the linear case y would be a difference of two challenges so X1 minus X zero and if you look at it let's say infinity Norm right then we can argue that this is less than or equal to infinite Norm of X1 oops plus X zero right and we have bounds on these individually

with RP right so this would be equal to 2B the overall it's just a triangle yeah so we can Bound by tweaking but this is again a very good question now in our setting the determinant is a product of challenges right and we are not just going to get this but we are going to get a product of photos like this so it's going to quickly get something bigger and in the paper that I'm going to talk about actually I have this in the appendices I'm not going to really show you the full expression but we show how to bound this for challenges of this one of challenges of this one but yes it quickly grows to a kind of like an unacceptable value if the degree

of the relation is very large because it kind of grows exponentially in the degree okay so so that's what's that that's the constraint on how big the degree can be okay that's right yeah we unfortunately cannot get very large degrees and even probably we cannot really get practically if you want to really want to practically efficient scheme but this is still useful because we can handle the cases about degrees two and three but for example these quadratic cases which is needed for minor groups for example oh oh I see so that's like the degree Bound in your circuit I don't know this degree is the degree of the polynomial I'm talking about the

degree of the relation that we are checking in the verification which was yeah because the size grows exponentially okay not this thing so this is different any other questions um yeah that's the fact that you have proven Ms binary um let you in in the like provable security way use a smaller modulus thank you ignore the r yeah the modules would depend more on R

because R would be much bigger than this message here that's why proving m is binary would not really helped in this particular case okay but if you ignore if you're using deterministic uh commitments then you can say that uh the extracted message has uh like L Infinity Norm uh DUI and then pick yes but again we would still need to look at the normal y times n okay yeah plus well it's it's gonna be right p uh y times like ring expansion Factor yeah so the international wood for this

would just be basically again 2p bounded by 2p because what m is binary so we either get y or zero so both of them would have infinite known at most looking and yes if that's just the only constraint then we can choose queue accordingly in the module scheme foreign a system like Planck but but here you're talking about the the low level relations that you can prove so um so so in practice when you build a proof system it's you you're going to be translating it to a polynomial that is a

higher degree than the the um the degree bound to the relations in your proof system so um yeah you probably couldn't do with this directly yeah yeah so this is really the degree of the relation polynomial relation that we check in the verification okay yeah very good yeah thank you for the questions that's great um okay and these type of challenges are the most commonly used ones in the latte settings and we can kind of basically make it as large as we want if we want kind of like a 256 the challenge set and

we can set the degree to be 256 which is the typical setting even for example these standard signatures and so on they use this dilute for example uh we can set the weight to V60 and we can change and set the infinite note we want then you get an exponential large sum inside [Music] and we have generic results on the length of or the norm of the witness so for this I'm going to refer you to the paper and these are parameterized by DWP parameters okay and since we are naturally inverting The Matrix we may even not need it to be invertible we can be single even though it's usually not singular uh and we don't put

any special condition on the kind of like the shape of the modular screw which means that we can use the store called entity friendly uh parameters to exploit this fast computational algorithms numbered analytical transform which is kind of like a variant of effort right so to sum up the first part we kind of talked about two challenges one is the so-called soundness get so we want to prove something of the form a times s is equal to T where s is the secret but we can only have simple prove that a times S Prime is equal to some y times T okay and Y is unknown and S Prime is in most of the case is

significantly larger than the aspect on those approval uses okay and I'm emphasizing every chapter here there are ways to prove exact relations but they're significantly less efficient than proving less relations and we also talked about this imperfect completeness so this arises due to the rules of rejection sampling and this is particularly a problem for multi-part interactive settings for example if you want to do a multi signature professional sickness or something like that because until we compute the response we do not know whether it's going to be accepting so for example imagine the part key is Bluetooth searchable the compute the challenge then suddenly one party might

get a response that's not accepting so we might need to repeat the whole protocol and everybody needs to do this so that's a kind of a quite a problem for this multi-party interactive setting even though it's not a good problem for the non-interactive settings where you have a single platform um can I ask a question about Sarah knowledge so in a in a straight log based protocol for example zero knowledge will often hold perfectly um you'll start holding this setting statistical uh so there it's not kind of like a computational zero knowledge which we are just concerned about the kind of like the response yeah of course if you look at the public

key of the user that the user is using that computation but these little knowledge Arguments for the response if that's statistical it's not competition got it right so that's it for the first part so this was a week of kind of talking about the SpaceX I hope you learned a little bit if you didn't know about family we kind of did a generalization of that okay let's move on to the second part where we are going to talk about this Monaro like private blockchain payments okay so let's see what Matrix family is in a nutshell so the first base protocol as I mentioned well this gives you a

kind of like a monorail style payment system and monitor is a privacy preserving cryptocurrency and I believe it's kind of one of the largest ones along with the zcash and this is it where we it use a protocol so-called ring CT so it's short for ring confidential transactions and in our Matrix work in our initial work we introduced the first practical postmodern variant offering CT and this relies on a normal balance Groove so I'll try to give you the rough idea for this and then if you look at Matrix plus so this is the follow-up work so this introduces a significantly more efficient post contouring safety protocol building on this earlier Matrix work and this exploit this Chinese

remainder theorem and we do attacking using that uh property and it relies on color automorphisms again I'm going to tell you a bit about this and then we have this auditable variance we are not in my Matrix Au or Macy's plus au but this is a variant that gives you formal auditability okay what I mean by auditability is that we can introduce some authorities into the system which can Revolt anonymity of the users for example if they're misbehaving or if there's some illegal activity then this Authority can revoked anonymity and you can see who that user is and this is an optional feature so I'm

going to discuss again a bit about what features that we can get we have efficient open source implementations so you can go to this link so if the code is available they will be linked yeah but the apart from Matrix we have the chords for the remaining fluid but Matrix has become kind of like obsolete at this point is on a matrix plus we should look at the code of them and as byproducts will get efficient postpone to bring and group signatures where we can also call the groups into an accountable link signature thanks to this automatic ability property and we also get what's called The Parsley decryptable commitment scheme and what this roughly is is that you can commit

to kind of like a pair of messages where one part of the message can be decrypted and recovered in the decryption but the other part cannot be okay so you you can get some compression um and you can also do some kind of like some parts of decryption even though you don't recover the full message and be sure that this is still here soon all right I think one of the very first questions that comes into many people's mind is how large are these things and if you take for example a monorail transaction you might think of it as kind of like this very little dot if you can see it and if you were just to uh kind of replace this smaller transaction the kind of like the perimeter that we use

in this setting to kind of like standard let's say like this install type Pros or like standard that is commitments with no optimizations whatsoever so this is about the size of a lot of string safety activities so it's really really it's massively consistent and Matrix is about this bit and Matrix plus is about this thing okay and you might say uh I mean it doesn't really tell you much if I move these things around so it's it's actually giving you a kind of an intuition if this is any good or bad okay so if you now replace this modular transaction with size of model transaction that's the size

then dilutum which is one of the selected post Quantum signatures would be about this big okay so that's kind of like a gap it's been easy the essay and a lot of signature and the Matrix plus is even achieving a smaller depth than what the id2 images and sorry just so I understand the comparison there is that's if you took an existing Monero transaction as designed and you only use dilithium just the post Quantum signature scheme is that what you're saying no no so in the first setting we are assuming that monologue transaction is that rid of that the size of that and we are comparing them to post Quantum bring cities yeah and in the second in the upper level

you're assuming that that little dot is the size of the ecdsa and we are comparing the past that other signature okay got it cool upper side comparison is different than the lower side comparison got it but I'm trying to give you a rough idea on whether this Gap is really any good or bad and I'm trying to argue that it's pretty good I would say because that Gap already exists a similar Gap already exists in these standard signatures anyways okay nice so let's try to move a bit more into how we would do this transaction and let's start with a non-confidence transaction by the way I think we are getting closer to the end of the hour I'm happy to continue but if

you need to finish this let me know Alexander we can finish it anymore yeah no we have technically the session is scheduled for 90 minutes so we can take anything so we we can go over if people have to drop they can feel free and drop but in general we have 90 minutes allocated for these so feel free and continue okay that's great thank you but if you take a non-confidence transaction but suppose we are doing something on bitcoin and we again have the our user Alice she has two accounts One account that's two dollars the other account is three dollars and she has Associated public keys tk1 and pk2 for these two accounts okay what she does is that she broadcasts the message I'm sending two plus three five dollars to book and she signs this transaction okay

we have a bunch of miners or verifying in the system that I'm going to just denote it it's one verified the verifier sees this message and the verified checks certain things okay they would first check whether the signature is valid okay which is just running the verification of the same signing algorithm and they will check whether the input accounts have been spent since everybody can see Alice's accounts they checked that they are unspent they are not in this and transactions and they can easily check that the balance is preserved because Alice has two plus three dollars in the two accounts and she is broadcasting the message where it says five dollars are being sent to okay things work quite nicely

but we are revealing some sensitive information man everybody sees who the sender is everybody the CS4 the recipient is and everybody sees how much money is being transacted so if you wanted to do a confidential transaction and we would want to hide the sensible information so we assign how much money is stored in the account somehow and we have behave how much money is being sent if I could recipient is and we had all the centers okay but now the verifier is a very is in a very Troublesome situation right I mean they don't even know how to do verification I mean they are not even

seeing who the center is they cannot check whether the inputs are uncertain because they are not even seeing how much money is in there maybe Alice is trying to spend minus ten dollars right so she's trying to kind of create money out of thin air and it's kind of problematic to check whether the balance is preserved okay and especially like the balance preservation is really one of the most difficult things to check to convince that she is not cheating and she's doing everything kind of honestly okay and ring CT is kind of a realization of this idea that's also used in monorail

as I mentioned and for these uh to hide the amounts we are going to rely on the homomorphic commitment scheme and ordinary signature is going to be replaced with a ring signature and to hide the recipient Monaro uses what's called that stab address okay so let's see how this spending Works roughly in Monero or in between safety settings I think the public key of the user is going to be a commitment to zero under the secret key okay so it'll be some random value and the coins are going to be the commitments to the amounts under some Randomness are okay and since the whole conversion is homographic commitment to

B is equal to coming into a plus b okay and I'm using editing notation here but that's okay okay so let's have our expander again instead of the direct amounts in the accounts we are not seeing the coins which is first going to Mint an output coin here we are going to denote that as ocn and she is going to create these Matrix okay in some random row uh or sorry it's the random column she is going to put her on public keys tk1 and pk2 and the rest of the columns are going to be occupied by some decoy public keys that

are associated to some accounts okay and she's going to construct another role in a specific way where she is going to sum up the coins that correspond to the public keys in the upper rows of that column okay so particularly she is going to sum up the coin or take the coin that corresponds to DK t11 which is DC n11 okay she's going to take the coin that corresponds to dpk12 which is DC n12 okay so these are kind of like the input coins we sum them up and then we subtract of the output going with achievement okay

we will do the same thing for the next column it will same thing for the next column which is kind of like the analysis column so we have c c and one plus cn2 minus ocn and we do the same thing for the for all of the columns okay now we are going to run a range proof on the output coin we could have done the same thing for the input coins but this is not really needed because they they are other kind of output coins for some previous transactions so they already had some range proofs run on them before so we usually wouldn't run them again but we would range proof on the output coin so make sure that there's indeed a

positive amount inside this component okay so we are not trying to send minus 10 nodes and then you can see that if the balance is preserved then this commitment in Alice's column this last commitment is going to be a commitment to zero because the input is one three submit two plus three which is five and the output is going to be a commitment to five so they will subtract of each other and we will have to commit to presume unders and randoms okay and this Randomness is something known by Alice so she can prove things about this okay and then she is going to run a ring signature or rather a kind of like a one out of and proof for this last row which

is going to prove that among one of these commitments in let's say five entries she knows the opening of one of them and that opening is a commitment kazoo okay which means that we are going to prove the balance using the string signal okay and she's going to run more ring signatures for the first two runs and this Pros that she knows one account out of these five accounts for each of those and it's as part of specific sequences she's even going to prove that all of these accounts are in the same column okay so this is a green card ring signatures

which is going to Output some kind of like serial numbers Associated to the accounts so that she cannot spend these accounts anymore okay along with the transaction sheets of the send the serial numbers and if she ever tries to spend the same accounts again they will lead to the same serial number which will be able to be linked by the verifiers and the verifiers will not accept this transaction anymore okay that's why we do a linkable in sequence to prevent double spin okay any questions on this foreign Darren you want to say your comment for the benefit of the future viewers of the YouTube video

I I was just saying that this technique of um uh where you you basically use a commitment to um run the value as k um and then you use that with alamorphic commitments but we use part of that we use that as a sub protocol in um ccash for um proving um the The Binding signature it's called um and in zcash that is mainly used to ensure non-maleability of transactions um so we don't use ring signatures um but it's interesting to to see the commonality there because I I think

um I came up with that completely independently for zcash yeah yeah the idea is basically kind of thing yeah the marketing to run the kind of like the computation that you want to do on the inputs rather than rather on the outputs yeah it's not an original idea so I think bulletproofs uses something similar as well yeah yeah that's right yeah this is kind of like a natural idea how you would do this kind of like a balance proof apart from the maybe like the ring signature but maybe actually maybe this is a question now that since we've since we're talking

about this are there any protocols that attempt to be privacy to attempt to do privacy preserving payments that don't do the construction like this I mean we mentioned we're talking about effectively A variation of Monero we'll talk about zcash has a similar construction here is there is there other approaches to privacy preservative payments that don't use this that we that are out there so so straws didn't use uh zero cache didn't use I don't know for commitment okay gotcha yeah so we are also when we see our protocol we are not going to do exactly the same thing but it's going to be still using homomorphic audience yeah we just told me to wait for the

punchline no thanks thank you thank you both really interesting uh yeah conversation and observation thank you for sharing Garrett so let's see uh what we do in our uh kind of protocol images protocol and how we do the spending uh translate the most of the kind of like the setup is the same but there is a significant difference in how we create the points it's sort of just committing to the integer amounts that instead going to the the bits the kind of like the vector that is consistent of the bits of the amount okay

and the commitment scheme is homographic on the vectors as well so that's still the homomorphism is satisfied oops I'll tell you why they are doing this so as before we meet the output coin and we construct a same Matrix based on the public Keys coins and so on but instead of running a range proof we are going to run a binary proof on the output commitment with where we are going to prove that this commitment is a commitment to a vector where each component of the vector is a bit so it's either zero or one okay and the reason we are doing this is completely for

efficiency a typical range proof in the latter setting costs almost 100 kilobytes if you want to pull for example 64 of the change proof and this is just way too expensive and if you want to prove that something is less than or sorry something can be up to 64 bits then your modulus needs to be larger than 64. it's right which is okay in the descriptive setting because it would already be using something like 256 bits but in the market setting you will typically use something like turtle bit modulus if you increase the modular significant to 64 bits then your problem becomes easier to solve it's not this problem which means that you need to choose larger parameters to compound

state for this okay that's why using a range proof is very expensive and that's why we are doing a commitment for the bits rather than taking integer amount itself and as before we do this linkable ring signature for the to promote ownership and preventable spending but this ring signature that we run for the last row is not quite working just yet and the reason for this is that even if the balance is really preserved over the integer amount that we will not necessarily get this computation is going to be a commitment to zero

and the reason for this is quite simple because if you sum up the bit vectors this is not going to be equal to the bits Vector of the sum of the values okay because for example the big if you add up like a bit of one plus another bit of one you get two but two is not really a binary value it cannot ever be equal to whatever you might get in the right answer okay so we need to do more uh to prove the balance is there a question in the example because my this meeting controls popped up yeah sorry I uh someone just joined so that was in the chat yep so okay

that's fine okay so we need to do more to Pro balance and the way we do this is by adding what's called what we call a correct commitment okay and corrector commitment make sure that if the balance is preserved which means that if the Num Sum of the inputs equal to the sum of the outputs then we really do get a commitment and this corrector commitment is added to all the columns the last row of all the columns but there is a crucial step which is a this corrected commitment we cannot just let it to be some arbitrary commitment otherwise the expander can exploit this to achieve even though the balance may

not really be preserved and the way we achieve this in this Matrix protocol is that we need to prove that this correct the commitment is opted particular form so let's just look at the first entry we have and let's just you know begin this is s i we have c i minus 2 times c i plus 1 where these Ci's are the carries of the computation okay so the first and last here is r0 if the balance is preserved so again control will appear but the rest of them are the carriers that you would get if you were to do this kind of like Edition okay

and if you really look at this what you're really doing is you take the carry of one digit you would subtract uh um sorry what you would do is it would take the carry he should move on to the next digit right and you would subtract this off uh from the digit that you are working on if you were to do Edition and this is kind of like a structure that we are mimicking in this comic book okay so you can see that we have CI minus 2ci so yeah these we are working with bits at the moment or this base two that's why we get this I minus 2 times c i minus two times c i

plus 1 structure for all of these components okay and we kind of more rigorously argue that if you really do this then you can guarantee that the balance proof works out correctly so the prover cannot cheat as long as they prove that the correct commitment is of this form and we ask the Proverbs really do this proof in The Matrix protocol and the way we do this is by encoding each of the amount of the bits separately each of them occupy a ring element and each of the CIO occupied by another ring element but they're all encoding

encoded separately and independently okay so each of them is going to be represented by a ring of and this is not quite efficient because each bit is just a single value right so it's just one bit value but the ring elements are usually much larger they might be I don't know something like more than 64-bit values or even close to like uh hundreds of bytes depending on the parameters that you are using so we are getting a very significant expansion in terms of how we are representing the bits [Music] any questions so far

would it be possible to sort of do a small number of bits at once okay so in the mattress plus we are going to exploit this so-called Chinese remainder third unpacking which has been used I think initially in this public encryption setting and they have been also exported quite a lot very recently in the zero note setting as well okay well let's suppose we want to prove this balance relation for integers AIS and bis right and we are going to be working over this

polynomial ring and what we are doing here is that we are taking Z2 and we are we have this kind of like variable X and we are of course I think that with X to the D plus one okay where D is often a power of two I mean it's not really important what this polynomial is what we are working on is polynomial okay and using the CRT this uh polynomial ring is going to split into sub Rings okay depending on your choice of parameters the splitting might might differ but uh for this particular parameter that we are working with it always splits into smaller submarines okay

oops so now we can exploit this fact and since I push this into for our parameter settings particularly into many factors and we can use each RP element to encode many values at once okay so I'm going to denote these kind of like each summary of IQ as a CRT slot okay and in each CRT slot we are going to store a bit of demo okay so let's suppose all right let's input 64 uh subreams okay and each of in each of the CRT slots I'm going to put a bit of the amount and I'm going to

compute the inverse mapping and I'm going to get an element of IQ which I'm going to denote by this Hazard symbols okay but a hat I is going to be a polynomial that represents in its the Articles the bits of the integer available AI okay I'm going to do this for all AIS I'm going to do this for all bis okay and then I'm also going to do this for the carry values as well I'm going to get C hat okay so if you now compare those two settings before I head

for each AI I had 64 ring elements right now for each AI I'm just using one ring column okay which is of course a significant saving okay now how do I do the balance proof that gets tricky but the commitment part is pretty much the same so I commit to this Hatchet values none instead of the bits themselves and again I come into the K values in the CRTs notes okay now to do the balance proof ideally what I'm looking for is to find an automorphism that does the following

thing okay well let's suppose these are the CRT spots F0 F7 for Simplicity I'm assuming that there are eight slots okay but in the real setting they're going to be 64 slots and this nothing is going to take my input and by the way if you don't know what work is means is basically a mapping on the set itself so it's going to map elements of R2 to elements of rx2 okay but it's going to do something really nice for the CRT Source okay it's going to shift each slot to the left by one okay I think this is going to be a cyclic rotation okay so F1 will move to the first one F2 to the second slot and

F0 will will Circle back to the end okay and if we add this which we don't I'm going to explain we could ask the verifier take the C commitment and compute 2 times pi of C right and you can realize that this slope would mimic the structure that we are looking for it's sort of really proving or asking the probability that this structure is preserved we can let the verified construct a structure using automorphism okay so since this is homogeneous we are really getting the structure that we want inside the commitment let me pause here and ask if there are

any questions because this kind of like a critical part so the the automorphism has to be compatible with the the commitment number of uh since we are working over IQ they are kind of automatically compelling yes okay everything is that's why it's going to work out yeah any other questions all right but sad news is that for the kind of like this power of two psychotomic rings that are commonly used in the battery

space crypto such a kind of like a full cycle automorphism.com Texas what does exist is kind of like a how cycle automorphism which does this okay so it kind of does this Automotive the Automotion that we are looking for for both house or for each half okay so F0 does not Circle back to the end but it's rather circles bent to the end of the first one okay we have the same thing for F4 F4 kind of circles back to the end rather than moving one to the left okay and what we have now is we have this two kinds like defective spots which is like a 500 the fourth spot and the eighth one

okay so we need to fix this and in our paper we introduce what we call a patching technique to correct these detective spots and this correction is done in a verifiable manner and in kind of like a efficient manner so that we don't spend too much effort and communication to fix these things so that we do not end up with the sort of the saving that we have gotten is not lost okay uh I'm not going to tell you too much about how the patching works because we need to introduce more technical tools for that but in the end what the proverb does is it takes these kind of like bi commitments

subtracts of the input commitment so the eyes are the output commitments subtracts of input commitments and then on the patched variant of the C commitment it constructs this structure that we discussed before and then prove that this is a commutative and the verifier can do the same thing take the bis AIS take the X verifiable attached variant of c and check whether this is the commitment or verify that this is a very conical position okay and in the end so the kind of like the balance idea The Core Balance idea is the same but we are realizing it in a different manner Than This original

Matrix protocol so we don't need to encode each of these bits separately so we're just going to use one element to encode the full vectors which is going to upside which is going to give us a significant um a question um so if you doubled the degree would you not need to do the patching or is does that turn out to be less efficient if you do what sorry if you double the degree then you only need to use half the um the the widths of your polynomial and so it doesn't matter [Music]

yeah so we are then we are using only uh like half of the CRT spots to encode the vectors right so we are basically not exploiting the other half at all yeah in the expansion yeah so so it's a trade-off between Simplicity and and efficiency but you don't have to do the patching so you you gain a little bit of effort [Music] yes yeah that could work but we are kind of losing from efficiency okay um I I have a question just um uh

uh okay so for like Edge tag commitments I get that um you would probably an alternative approach besides um uh using this corrector is to prove that the um inner product of whatever the commitment opening or is and um you know like powers of two is equal to zero right exactly so um it seems like the issue is that powers of two are not small and this creates some issue with abstract commitments I'm just wondering

if um there are proofs over um like bdlop commitments or other commitments that allow you to have arbitrary uh size messages um that permit some sort of linear map proof um or not and if you could use those as an alternative way yeah yeah so for the video commitment that you mentioned it's correct that the message can be unbounded but still as soon as we use the powers of two then to prove the expression spots over set

whenever we get the same total the power 64 minus one or six to three or something like that that value is large and to prove the integer relation we need to choose true to be larger than 2 to the 64. but otherwise we are going to get a volt reduction and then the expression that we are wanting to prove over the integers will only hold much local not all the integers okay yeah that makes sense yeah we are really trying to avoid any large values occurring in the expression because if you were happy with that and we would just use the ring CT balance proof we don't really need any correctors and so on any other questions

okay so I'm going to tell you a little bit about auditability and the performance results and then we will be done so you know about multiples protocols like Alice and Bob exchanging a bunch of messages and if you look at the kind of a privacy prison protocol then we what you may want to hide the identities of the center and the receiver and you may also want to hide what messages are being exchanged and of course we might know about this already but the anonymity features of this privacy present protocol can be exploited by analysis parties for example they might say that they might ask for a random Ransom and say that pay me in one Monero one million dollars or

I'm going to destroy your files so kind of uh resolve this kind of issue between privacy and uh kind of like illegal use of these privacy features we can introduce this auditability into the system where we would have an authority and this Authority can be actually multiple authorities who might be sharing this kind of like a chapter that we are going to use but I'm going to represent it as a one Authority and this Authority has kind of like a chapter information that allows them to see you know the revoke anonymity of users and they might say okay that's actually what

and they may also kind of use the strap door to see what's inside these commitments or encryptions okay and that's the auditable of the future that we introduced into the next protocols so we allow this adversary sorry Authority uh we give the authority some chapter and with that they might do this uh what the debility functionality okay and then I know it was a Freudian slip of adversary versus Authority but in the crypto Community some people might view the authority as the adversaries they kind of could work in some settings but uh it really interesting yeah yeah I agree so it's a debate that I'm not going to get into it but the good things

of course yeah we can distribute a trust on the authority so it can be like yeah we might ask the police a judge and you know some uh agency to come together to be able to reconstruct the trapdoor and do this auditability picture yeah we talk about sometimes you know this this concept of like if you have a you know a team that's dedicated to kind of looking at maybe a graph of transactions they may not necessarily be the one to see the identities of where the individuals are or who the individuals are transacting and but if there's like a clustering of unusual activity that can be handed off to another Authority that could then view the specific individual yeah yeah yeah all all comes with trade-offs and to you know don't want to distract

from the technical aspects of this talk this is obviously more of a philosophical point but it's interesting that you've included that as a part of the protocol yeah yeah but we actually do get very nice features in terms of what the ability one feature is that we can have multiple Auditors that can edit all the same transaction without revealing their individual substance reason okay and then we can let each user decide uh or maybe we can bet and choose between Auditors or they might even choose not to be audited so we can have some users for being audited by let's

say A1 some users were being audited by A2 and some users who cannot be audited by anyone so if you don't want to auditable the feature then you can choose not to be audited but we can also have a system enforcing all the stabilities so that like illegal activity or analysis users do not uh choose to be should not to be audited by enforcing that they fail in transaction you can learn auditable ones in transects and I think this is a good way to strike a maybe a better balance between this privacy and kind of accountability okay let's now look at the performance

results so this is for the ring and group signatures uh so kind of like the state of the art now in this setting is that the smallest you can really get is kind of like several kilometers like close to 10 kilobytes for both ring and group signatures but you can get kind of like a fully logarithmic size increase for example if you have very small 11 users or 11 as they ring or the group size and we've increased it to a thousand you don't get a kind of like a 10-fold increase but it increases poly logarithmically to something like about 20 kilometers and we also have this another work

called building and this one we can also instantiate in the post Quantum setting but the disadvantage of this is that it's case linearly but so it starts so small but it quickly becomes large but if you have a very small uh if you are looking for a very small anonymity set then this might be useful for that setting and in terms of the Matrix and Matrix plus proof sizes so let's just look at the compressed Matrix plus so we are getting something around 30 to 40 kilobytes depending on how many inputs uh that you have and this is for the anonymity level of 11 which is a setting

that Monero uses we have about like three and a half kilobytes of the keys so the serial numbers are quite small 22 bytes and the modulate system modulator that we use is less than 30. which is good because we can fit into the variables can fit in the public registers which allows you to do the fast computation and we can also use what's called a publicly compression technique to reduce the public key sign but we have this kind of like a rather standard technique and there is also a concurrent work that appeared in crypto if I remember correctly and they start off at very similar efficiency levels like we have 29 and

they have 26 slightly smaller but when we increase and the number of inputs they quickly become large because they scale linearly in the number of inputs while the Matrix plus constraint construction is the only one that scales up linearly in the number of input accounts um just a second the units in this graph so so for example the the 47 what what you necess that it's kilobytes a kilobyte okay thank you yeah unfortunately it's of course much bigger than what you can do in the prep Quantum setting but yeah this is kind of like and what we can do

uh wait in the in the last page did you have inputs specified is that for like a fix for the ring technology yes this is going from two inputs to so the first column in the previous slide ah sorry oh yeah this is a typical setting this is two I'm not sorry this is ring signature which input which one is that foreign foreign yeah wait so which part of it okay there's multiple ring signatures I guess sorry what fully makes up the proof in

the next slide then ah yeah so this one has the ring signature balance proof and binary proofs and some other uh proof of them from the opening flows and so on okay so this is just a little bit more than just an institution okay yeah so but you mostly just explained the balance proof yeah that's right yeah I didn't talk at all about the what is uh rings okay sure do you know how uh for larger values of n how um your scheme like the ring signature comparison then

yeah So eventually it's LNS 21 becomes smaller than our construction because our construction skills uh and it's like a bit faster than look it's called look and the construction exactly really important and after I think a thousand our construction or something like thousands our construction becomes slightly larger than lls21 yeah the Gap would not be like exponential because they are both scaling over it quickly but still in terms of practical numbers LNS 21 scales better to larger values uh-huh yeah I guess I asked because I'm not super

familiar with the transaction graph analysis work the last stuff I've really looked at on it was from like 2019 like um works by like Michael John at all and uh it seems like this sort of like n equals 11 size is really bad basically in practice and that to get uh anything that's like practically hard to trace you really would have to get uh into the thousands or above yeah yeah around thousands board schemes are uh kind of very similar but if you get to I don't want to ten thousand or a hundred thousand and so on then LNS 21

would perform it um yeah 11 is the setting that's used in one hour that's why we're kind of focused on that setting yeah I mean yeah just a given ring size um it makes more sense to use a zero cache style protocol where your your uh approving um sort of membership in an accumulator like a medical tree yeah yeah the the kind of like a limitation or uh an inherent limitation of brainsticknesses is that the signature generation

the overall public key size that you use in your verification and the verification time they are all linear in the size of the anonymity because you need to go through each of the public key in both verification and signing and you also need to use all of them in your for example if you need a complete some hash or something like that so you need to translate all of the public keys for this linear this linear limitation cannot be overcome and therefore I mean you may not be able to work with something like millions of users because you need to travel millions of public keys for each of them and you need to run real computation in the order of millions for each

verification which is a significant implementation yeah so so the the competing system there would be to use um basically is decache with plunky 2 or something like that a journal purpose um yeah uh uh post Quantum um CK proof system yeah yeah um so this one I talked about and in terms of runtimes this is what we get for Matrix and Matrix Plus so everything is under uh Second and these are the the units are in milliseconds uh the longest one is a transaction

generation would step up like 100 to 200 milliseconds but the verification is very fast and in fact it's even faster than when there are about like six times faster and transaction generation is only slightly slower than whenever so in terms of computation uh it's very good yeah okay and if you look at the auditable settings you see that there are slides increases in terms of proof size but it was like three percent increases in all cases so public key size Remains the Same and the system modules we need to increase it slightly improvements

and we can do it we can do a similar contest but Matrix plus specific Matrix but again we see small increase in the proof size and small increase in the system modules now in terms of run times again auditability versus non-auditable again we are getting very similar runtimes uh but slightly less efficient but it's it's not some open questions and then I'm going to conclude and of course we would be looking for more efficient Solutions in perhaps one way to get this is to rely on more

stronger security assumptions and recently people have been looking at these lattice problems with leakage of Revenue you might reveal maybe you're leaving a part of the error when you're making a bit of the information do we get security in this case can you construct more efficient Solutions in this case and another thing is of course looking at to build more efficient XFX proofs so that we can get rid of all these relaxations and we can maybe run things more smoothly and you can try to exploit these things being structure even further and I I guess forgot to mention everything that we are talking about is in the random Oracle model so we need to

look at the security analysis in the quantum random molecule model and there is plenty more open questions out there and yeah anyone is more very well encouraged to work on them and here are a few references if you want to call them and have a look and with that I'm going to conclude and I'm really happy to take any questions awesome well thank you Muhammad I don't think we have time for questions because we're a little bit over time and I know folks have to go but this is a very important session thank you very much for presenting thank you yeah