"Simulation Extractable zkSNARKs" by Dario Fiore

Transcript

okay so just to give a really brief introduction uh we have a new learn sh session today with DAR F who acceded to accepted to give Ault latest work which is related to simulation extractability uh on different in one of the most relevant protocols that that we commonly use in the in the knowledge landscape um the talk is going to be more or less oriented on giving explanation so what simulation extractability is how does it work how do we analyze it and how we basically check it for protocols and this is where I think uh that will link it to his latest work uh which you

cannot check in the description of the video in the invitation or basically anywh you want INR and print so that thank you very much for attending and whenever you want you get start yeah thanks for the nice introduction um yeah so I'm Dario from in there um I mean for those who don't know me I'm a a cryptography researcher um here at MD software Institute and I work on zero knowledge in general and snar Vector commitments um okay so I think Carlos already gave more or less you know what's the outline of the talk so um I'll start by giving an introduction to

security definition of non-active Zer knowledge so this is something very very basic but since I'm assuming that you know maybe people here could be familiar with constructions but maybe a bit less familiar with the formalism to Define security of constructions I will try to spend some time on this and then I'll uh I'll introduce the notion and the problem of malleability of proofs uh in zero knowledge and why they're important and um and then the next second part of the talk will be about how can we construct this simulation extractable also known as non malleable zero knowledge narks and I'll talk about our recent

work um all right also feel free to to interrupt me and ask me questions interactively all right so um what are non interactive zled Pro so um so this is uh non knowledge proof is a proof system for uh MP relations um with the uh so n NB relation it's you know it's a it's a relation that about pairs of a statement and witness that you know satisfy in certain relation for example it could be you know the um I don't know X could be uh certain strings of 256 bits and then in the relation we have all pairs for such that you know xw such as the as of w is X right that's that's

an example okay so now let's assume that um uh right there are these two parties the prover and verifier and the goal of the prover is to show that there exist a witness so that x w such that xw is in the relation okay um so for example I mean maybe to to pick something which um in which sometimes the witness does not exist let's say that X is an integer and you want to show that it factors into prime numbers and W is the U the the two prime numbers um so um more formally an easy can interactive proof consists of three algorithms there is a setup algorith that given the security parameter

produces what we call a common reference string so think of them as a public parameters um and using this common reference string that is generated once and for all um the prover uh can use the statement X and the witness W to generate the proof right so then the verifier simply given the statement and the proof will say say accept or not okay so uh what is important is and what they're called non interactive is that um once you have generated this CRS the approver has to send a single message to the verifier okay so they don't have to uh to interact now what um properties do we

want from non-interacted zero knowledge uh proofs the first one is completeness essentially says that if everybody's honest uh then the verifier accepts so in particular if there exist a witness for X um then when you verify a proof generated um for X the proof must pass verification okay so no nothing special here um okay then there are two more properties that U um formalize the security of non interactive knowledge zero knowledge and sness so let's start with zero knowledge okay so in words zero knowledge means

that the verifiers learn nothing about the witness beyond the fact that the witness exists right so the verifier gets to know that it exists but it doesn't know which witness you used and and and nothing more now how is this um uh formalizing cryptography terms and in this is like so pay attention to this because this is going to be relevant to understand how do we Define simulation extractability so in order to um um to model the fact that the verifier lears nothing uh we're comparing to uh two games so here can you see my cursor moving yeah yeah we can okay good so in one game we generate the CRS using setup and then there is

this adversity we call D so it's the one that has to decide has access to an Oracle and this Oracle think of it in this game is is the Oracle where it can sense uh a statement and a witness and it gets back a proof generated by the proof algorithm um but and then we want to compare this against the experiment where uh instead the CRS is generated by another algorith that is a simulation uh simulated setup algorith that generates the CRS together with the tror and then like the proofs are um generated using a simulator for the prover that is an algorith that uses the tror in order to generate the proof

given only the statement right um now pictorially we can think that this guy the verifier submits xw and then it doesn't know what happens inside the box so either you know it could be that the proofs are generated using the proof algorith or maybe it could be that the witness is like discarded and the proofs are generated using the simulator the simulator um so what we want is that this guy the verifier should not be able to tell these uh um words aparts and formally this means that if we measure the probability that he outputs one in the game where he plays with the simulator and the probability he outputs one when he plays with the real prover

these two probabilities must be uh close Okay so I actually forgot to say that you know their difference must be negligible um okay so uh again to recap uh we say that an EIC is zero knowledge if in addition to the um the seta Pro and verification algorithm there exist two other algorith that are Sim set up and Sim proof such that these two probabilities are close to each other okay okay any question on this okay so I mean the intuition is that uh if proofs can be generated without the witness using some tror of

course then this means that the you know and if these proofs are indistinguishable from the real ones then it means that the real ones don't don't convey information on the weakness all right so um the other uh property soundness which in the um in English terms we could say that it means that a malicious prover cannot make a verifier accept false statements so assume that here there is the our adversary that has a um a statement X for which there is no witness you know no witness that makes it in the relation uh then it should not be able to produce a valid proof that is accepted by the verification algorith um well that's it so right so this is this

mean soundness so in cryptographic uh formal is this means that um for every adversary that is probabilistic polinomial time so know it's bounded in in time resources it cannot uh come up with the statement and the proof that is valid and for which there is no witness so here it's important that the CRS is honestly generated for this two um you know for this property to to hold okay so now um an an important observation at this point is that um like um you know for some relations soundness is not sufficient as a

condition okay why because think of a relation for which there exist always a witness so essentially every X could be in in r or or let's say for every X there could be a w in r i mean an example is let's say that the relation is checking sh to 56 pre images maybe you know with overwhelming probability an X as a pre image um so in that case soundness is not sufficient as an option right so what we we actually want is a stronger notion that is called knowledge sness that actually uh says that if the approver is successful in convincing the

verifier then she actually must know the witness W for that statement and um in cryptographic terms this is uh saying this is formalized by saying that if the adversary managed to to create a proof that um convinces the verifier then there exist an extractor uh that can uh output the the witness W such that you know the W is the right is a good weakness for for X now in in the more precisely the definition is model the opposite the probability the opposite happens more precisely means that we say that anic has knowledge soundness if for every

adversary a there exists an extractor such that you know when we look at the experiment where the adversary produces statement and proof and the extractor outputs the witness then we want that there is negligible probability that verification outputs one so and the witness is a bad one right it's not the it's not a witness for X okay so um to recap here the the the message for about knowledge soundness is that um if you manage to create a proof that is accepted then the intuition is that you should know the witness now let's see what happens when you uh use uh anic in the wild right so

in in real systems um so what happens is that an adversary that normally no sness is supposed to receive the CRS and produce a statement and a proof in in the real world may actually happen that she has seen several uh uh proofs generated by other people right so there could be other provs that she can have access to that are producing statements and and proofs now let's say that we are in this environment now what's the guarantee that if this adversary produces a valid proof she really knows the witness for this

proof so we cannot be convinced about this because you know for example a trivial thing that the adversary can do is to just copy paste one of these statement and proofs that she has seen right so and that's unavoidable right so we cannot prevent this what we could do however is to say okay look maybe this we have to accept this fact and we can have a a definition that says look in if you are in this let's say distributed environment then uh when you return a proof I will check that this is not a proof that you have seen okay for now I'm I'm staying high level all right um the problem is that perap like seeing a

proof for uh you know one of these X1 X2 X3 could help the adversary to create a proof for a new statement X and this is what is called a malleability attack so for example to think about example let's say that you have seen a proof about X maybe X is some um you know is the result of a computation and then uh you have another proof for uh let's say you know let's say you have a proof for X1 and a proof for X2 and this allows you to create a proof for X1 plus X2 right it's actually something that you know in some proof system it is possible um so and that's what we call a

malleability attack so uh in contrast what we would like is in some sense is nonability that informally we can say that it's the guarantee that copy pasting is the proof is the best possible attack that um you can do so um let's now see how this concept is formalized in um you know in I I have one question uh yeah when you say we haven't seen this proof before who is who who keep who has the bookkeeping of all of the proofs that have far good question so we're going to see this in this slide but it's like it means that we will define an experiment

where we actually bookkeep what uh what the adversary ask makes sense okay so um right so to model simulation sound and or simulation extractability the idea is that um first of all like the adversary has access to a CRS and this CRS is generated by the uh the simulator algorithm okay um and then the adversary can ask uh proofs on statements of her choice right so and she can do this as much as she wants uh but here the point is that these proofs are generally using the simulator and the tror so this models the fact that the adversary is seeing proofs for which she

may not know the witness right because she may even ask for example false statements here um now after this process is over uh the goal of the adversary is to come up with a new statement xar and a proof P star and we are going to check that this is valid so it passes verification but also that the pair xar Pi star is not in the set of pairs that um have been like asked and received from the Oracle okay so that's exactly the bookkeeping so it means that you know if more formally we would accumulate all x i Pi I in some set and

you check that xar P star is not in this set now uh again we want to model extractability we want to model knowledge soundness um so to do this what we uh essentially the idea is is is the same so we're assuming that we look um no way so we require that for every adversary a that plays in this game there exist an extractor that uh you know given the view of a I mean here I'm not using the full formance because it would be a bit more complicated but think about that the extractor has access to every input of a including the the transcript of the queries that she has made um then this extractor will output a witness W star

and then again we check that the um statement xstar and proof P Star Pass verification that they are a new pair and that uh like the um uh the witness that was extracted is a bad one right so we uh in this case we say that the adversary and the extractor win and we want to what we want is that the probability that this happens is negligible all right so this is the ENT the the definition of um right of simulation extractability um right I I want to mention that there is also a weaker version of this definition in which instead of uh checking that the pair X star Pi star is

new we may be enough with the fact that uh like the um only the statement is new so in in this mod for example could be useful to model schemes where proofs are randomizable so in that case it's kind of easy to uh obtain a new proof for the same statement but uh weak simulation extractability extractability models the fact that you cannot do better than this um okay so if you have question on definition this could be a good moment I move on can you hear me yes okay okay I have a question in regards this weak simulation extractability concept that

you mentioned what's the exact trade-off that it brings uh if we analyze I don't know plun or whatever proving system based on uh simulation extractability or weak simulation extractability what can we say about it depending on on which way we analyze it um but you mean what what kind of trade do you mean a tradeoff in terms of security or in terms of the tradeoff in the like if you have these two ways of analyzing it I assume you win something or something is better than the other depending on what you choose to what method do you choose to an no these are two I mean it's not that okay these are two different definitions

like and one is definitely stronger than the other because full-fledged simulation acceptability says like look the only thing you can do is copy paste the per statement and proof weak simulation accessability says if you have seen proof for X1 X2 X3 you cannot come up with the proof for a different X star yeah okay uh but you may come up with a different proof for X1 for example right so we're going to see that I mean some schemes have this property and sometimes this can be eff ficial because uh in some context having the possibility of taking a proof for some statement and just randomize it and getting and get a fresh proof for the

say statement could be useful when uh you know for example if you have to let's say authenticate yourself for anonymity reasons like you don't want to expose the same proof uh several times definitely uh is there any other use case aside from rerandomization of proofs where this can be useful you mean weak simulation EX yeah exactly I think it's up to the application so like in some applic yeah I don't have something in mind but like yeah it really depends on the application like if sometimes I mean let's say randomiz ability is a good use case where uh

sorry yeah where anonymity is a good use case where R randomiz ability is useful makes sense makes sense let say that maybe strong simulation extractability could be uh easier to um to use in some applications if you can exclude that something has been let's say seen and you want to discard proofs that are copy pasted let's say okay so if you have a mechanis to keep track of what has been produced for example thank you okay so okay why why do we care about simulation acceptability um I mean first because this notion actually implies the proofs are non malleable I mean

essentially it's really intrinsic in the fact that it implies the fact that you cannot uh given a proof for X you cannot come up with a proof for X Prime without knowing a witness and that's what for example like you know Sai that introduced this notion of simulation soundness uh um you know wrote in this sentence like essentially it this implies that whatever one can prove after seeing an easy proof one could also have proved that without seeing it except for just duplia the proof so there are two maybe uh important reasons for no malleable proofs one is that of that some real protocols may require this and

actually I'm going to give you an example in the next slide and another reason is more if you okay if you're a cryptographer and you care about provable Security One realizes that um you know the need of this in real protocol comes from a provable security reason that often when you have to prove security of a scheme you will have you will be in the situation where your adversary does not just receive let's say the CRS and produce the proof but is seeing simulated proofs uh so and that shows the need of uh having a stronger notion that and not just knowledge soundness okay so um I'll give you an example of U you know why would do care

normal ability with something that maybe is um you know some example it is close to maybe people in this uh in this audience uh which is the need of noral ability in some blockchain protocols in particular in Anonymous cryptocurrencies so what I I'm describing in a slide is a very like part of a to example of the zero coin crypto currency um which um it works like this so there is a u essentially a coin what we call a coin is actually a commitment to a serial number with some Randomness R okay so the coin is the commitment um and if you know own a coin it means that you know this serial

number and this secret are now the blockchain keeps track of two sets the set of minted coins so coins that have been produced and accepted to be valid and we'll see how you you accept to be valid and then some set of pent serial number so serial numbers that have been already used and you cannot reuse anymore otherwise you would have a double spending adap now um how do you spend a coin in such uh a protocol so we have our uh friend here our edog that has a coin a and in order topend this coin anonymously um what it does is to create a transaction that contains uh you know

the set minted coins and the set spent serial numbers or if you want maybe ashes of these sets um the um serial number of e coin s n a uh and a new coin B okay so the idea is that now the the user is spending a coin a and is transferring the value to coin B and notice that the serial number of a now becomes public so in order to to make this transaction he attaches a a proof pile that is a proof for the fact that he knows um a coin right so the coin is secret so he knows a coin he knows the uh

randomness of of this coin of this commitment such that uh essentially this relation is satisfied which says the coin is in the set of minted coin so I don't show you which coin I'm spending but it's there and the coin a is a valid commitment to some Randomness that I know right and to the serial number that I'm exposing now uh what happens now is that what the validators will check they will check that the proof is valid so that this conditions Al so this coin is in the set of minted coins and it's you know it's a coin with this serial number and then they will additionally check

that the serial number has not been already spent okay so if this is uh oh sorry so if this happens what you uh what they do is to progress so the state of the blockchain changes by adding coin B to the set of minted coins and then the serial number a now is a burn serial number and it gets into this set okay so let's now see how you could use malleable proofs to uh essentially break security of this cryptocurrency so um let's say now we are in this state where um this guy has produced this transaction so he has spend the coin a

so coin a should not be valid anymore um and then there is this adversity have just observed uh this transaction to happen so he know she knows the transaction statement and she knows the the proof now what she can do in with the malleability attack you know if the scheme is malleable uh she could for example now create a new statement that contains the um you know the updated sets of coins so minted coins Prime and spend serial number primes she can come up with a new serial number s and prime a and some other coin c and a proof that essentially I test that this is a valid

transaction now if the proof is valid and this serial number is not in the set of spend transaction then the validator will have no other choice than adding coin c to the set of minted coins so which means that now you have created a coin out of iner So You Know by if you want like sort of double spending coin a uh but in some sense it's about creating by creating a fake proof now I'm not saying that you know for now I'm just assuming a general malleability if you want some very strong malleability attack on this proof system but the idea is that if you have seen a proof and if you can come up with another proof without knowing the

witness U on a different statement then this is a problem now in the uh zero coin or zero cach that use this approach this is not possible because there are additional uh checks in the relation that you proof um but you know if the proof system would be uh non malleable that you know you could get for free this um this property all right so this is to motivate why do we care about noral proofs um now I'll move to the second part of the talk which is um how can we construct um simulation extractable Pro system in particular simulation extractable

SNS okay so I have to uh I want to mention like that um uh you know the in in his first works I when introduced the notion of simulation soundness and uh and also extract was introduced by grow in 2006 uh they gave specific constructions of schemes satisfying this these Notions and I there I have to say that there is a large body of research on this and it's not my goal here to talk you about in general about simulation sound and set of the art of simulation soundness or simulation ability for for ning uh the focus that I want to uh put here is on just simulation cability for zik Nars that are this class of Nik

where proofs are succeed right and these are very you know popular nowadays for their appealing properties for example for um decentralized protocols so um okay what can we say about simulation extractability of zero knowledge snars um you know one obser observation is that most uh Z that are out there are only proof knowledge sound okay um and this is one could say okay why why this is the case I mean first of all because in a normally in a research um path I would say like that's the first thing you want to obtain right so the first

non-trivial property is how to obtain that something is sound um but there there is more to it so another observation is that actually many of these uh of the many well some of these existing constructions are malleable for example Pinocchio and gr 16 that were this uh first um popular zik nuts have randomizable proofs um but then also another reason is that proving simulation acceptability is extremely challenging um because it's a complex property and uh so often it does require like uh uh additional additional work that you know it essentially it's

worth probably like additional research so it's a sort of a second step in the in the research on Z NS um okay so let me now go to the question of how do we construct simulation extractable Zig nuts so there there you know on the good side uh we I have to mention that there are generic ways to go from U just a niic to a simulation sound niic this has been proposed since the early days of when this notion was proposed by the sanos in 2001 where they gave a a compiler um the drawback of this compiler and some more recent and

efficient uh variant is that still it blows up the proof sides so this is not a problem for nisic but it's a problem for snars because like you go from a scheme where proofs are uh let's say logarithmic in the length of the WID to now something that is linear that is usually what you don't want um so now let me analyze what happens to the first generation of Zig SARS that you know I call first generation like the skines that have thrust heads and circuit dependent setup like for example Pinocchio gr 16 so these teams have R randomizable proof so strictly speaking are not um simulation extractable um so so uh and that

actually motivated uh growth and merer in 2017 to propose the um the first efficient simulation extractable znar with with short proofs um which essentially was I mean it's a it's a scheme that is a bit less efficient than than growth 16 uh well maybe no it's less efficient right not only a bit U because it's also a scheme for um a language that is not just um quadratic arithmetic programs um and another thing I want to mention is that actually like um in a uh I mean I would say yeah in a more recent result um bageri and wov have proved

that gr6 uh has R randomizable proofs but actually that's the best uh malleability that you can do so in the sense that it is weekly simulation extractable okay so this require I mean it's weekly simulation extractable in the AGM in the algebraic group model but uh it does require some additional properties that I mean I'm not going to to discuss but I refer you to the paper if you're interested about it okay so what about you know what we can call the second generation zik knut uh I mean I have to say also in the first generation there are other other schemes that are simulation extractable but this is let's say the what are maybe

the the very first ones okay so um let's now consider like skins with this Universal and transparent or maybe updatable uh setup um algorithms so in that in this case there are some recent results that show that for example bullet proof simulation extractable in the AGM um a more recent result shows that Spartan and bullet Pro are simulation extractable but now under the very same assumptions under which they are knowledge extractable uh knowledge s um and finally another War by ganes kosak K NES and Zak from 20122 shows that um Sonic CL and Marlin are

simulation extractable and they do this by showing a framework based on two Notions called unique response and trapless Z knowledge um and uh you know the drawback I mean this is what I want to say in general about the state of the art is that as you can see all these results are quite so even this recent one um that gives some framework uh has to introduce new properties that you have to show for each scheme such as distruptor zero knowledge or um unique response that essentially required to reanalyze the security of each of each scheme so um so this stateof thee art is what motivated uh our work um that is this paper um that is going to appear at

ECC 2023 um called from polinomial IOP and commitments to noral Zig Nars so U essentially the question we asked in this paper is um let's consider um all these Universal zik Nars that are obtained using this modular framework consisting to taking the polinomial iops polinomial commitments and putting them together using the F Shamir transformation and the question we ask is under what condition are they simulation extractable okay um so uh you know very in very briefly spoiler of our results

of our contributions is that um we actually Define a notion of a weaker notion of simulation acceptability for polinomial commitments that we call policy based simulation acceptability we show that kcg satisfied this notion for some some policy um five uh we give a notion of compilation safe polinomial so essentially some conditions on the polom P that F2 Al and then we show that if you compile uh um you know if you use Z Nars using these two objects you obtain simulation extractable Z Nars and this allows us essentially to imply the um simulation

acceptability of uh Marlin plong lunar ambassades but although I mean I I will explain not exactly the schemes the more optimized schemes okay so that's actually an interesting um open problem okay so um okay maybe like to a quick breath to uh I mean just just to brief and this is the outline how I'm going to present this result okay so I'll uh first give a quick introduction to what are polinomial iops polinomial

commitments and what is this modular uh compiler uh that allows to build ZK narks um using F Shamir um then I'll describe that actually uh this approach is vulnerable to some malleability attacks um uh and then I will discuss how we can patch them and I will also mention that you know we will study the malleability of casg and and finally I will give what is our recipe to obtain simulation exceptable Zars all right so um okay so polinomial interactive Oracle proofs uh are um an information

theoretic um proof system that uh uh is defined actually know precisely I would should have said polinomial holographic interactive Oracle proofs so it's a proof system for U index relations so these are essentially NP relations that u in which um the relation consists of three uh elements an index a statement and a witness and you can think that the index is like uh an index of a relation so it's a way to model so-called Universal relations a classical example is that R could be the um um you know the fam of relation that contains all uh circuits of a certain

size and all you know statements for which the circuit is is satisfied right so in the index models which circuit you are going to use the statement is the input of the circuit and the W is the private input of the circuit for example okay so in a polinomial IOP um uh what the first algorith that you have is the so-called indexer so the indexer what it does is to take the description of the relation that you want to prove think that you Tak the description of the circuit and outputs a set of pols um that uh oh sorry a set of polinomial that uh describes describe the circuit okay um and that's something that okay

it's maybe I I should have not put it like this in the in the slide it's not generated by the approver so this is something that is for example generated by the verifier okay so but it can be done in an offline phase then the protocol between prover and verifier um consists of several rounds so it's an interactive protocol at um the verifier is just So-Cal public coin verifier so at every round the verifier simply samples a random uh field element let's say Row one and sends it to the approver and the approver answers with a polom um now this polom is not really given to the verifier but is a is an oracle right so it's sort of a polom is

there in the sky that later the verifier will be able to to query in in some way um but the pro is essentially sending it okay so again remember this is a sort of an ideal proof system where we are assuming that yeah the Prov can later we can see is can be arbitrary but then like you know these oracles are are there in the sky so the verifier will trust that things with the Oracle will be done correctly okay so this goes on for several rounds so every round the Prov sends a polinomial uh then later the verifier responds with a challenge and so on now uh when these rounds end uh what the verifier outputs is a um what we

call a polinomial check so uh it will output a multivar polinomial g and a set of other pols V1 and VN and you know you can output K of them I mean or several of them um and the idea is that uh the verifier accepts if this equations so if for every Cas this polinomial GK uh is identically to zero when GK is computed on x and the evaluation of each of the Oracle pols on the I VI polinomial on on X okay so this is a very general way to for

example model different type of queries that you can do uh for example if you want to model that the verifi wants to test evaluation of P1 on know Point Z then it would Set uh V the polinomial V1 to be the constant polinomial uh with constant term Z and that you know and then maybe you can put in the coefficient of G the fact that you test that something is equal to one okay so this is a uh in fact this this not this way to model uh verifiers is um is the notion of polinomial holographic proof that was I mean we propos in lunar that generalizes the

notion of uh algebraic holographic proofs and um and uh I ldp you know ldp from respectively Marlin and and Blanc okay so in terms of security in in a polinomial LP we want knowledge soundness and I mean I will describe it only uh informally it says that there exist an extractor such that for any Prov that convinces the verified extractor by interacting with the pro can extract the witness and then onest verifier zero knowledge uh that means that there is a a simulator that can simulate the view of an honest interaction between Pro and verifier

without knowing the weakness of course um okay so remark again what the remark here is that this is an ideal um an ideal protocol in the sense that when the verifier uh outputs this decision you know this way to decide whether to accept or not which is this G polinomial um this test is not performed by the verifier it's performed by let's say trusted party that has access to the Oracle polinomial and can do this okay so and that is that then we you know we will replace this ideal part with the polinomial commitment so very briefly polinomial commitment is a um

okay it's a sort of a proof system that allows you to generate first a CRS you know with a setup algorith and then you can commit to a polinomial p um so and produce a commitment C and then what you can do is to um prove evaluations of this polinomial on the given point x okay so um it will the proof algorith produces a proof for example about the fact that Y is p of X where Little X is is an evaluation point and then there is a verification algorithm that given a commitment and two values X and Y and a pro Pro accepts or rejects so uh one important observation

that we are going to use in our work is that this Pro and verifier algorithm um essentially are a commit and bruar for the relation that says C is a commitment to p and p of X is y right so because requiring that the proof is suced essentially is uh is equivalent to to um to saying this that the polyal commitment we can see in in this way all right so how now can we use polinomial IOP and polinomial commitments in order to um to build a sar so the idea of this um of this compiler that you know this does is not

our work so this has been uh used essentially in in many uh many previous works is that the way you know the CRS of the snark that we produce is actually the CRS of the polinomial commitment um now the derivation algorith so what is the derivation algorith the now in N so it's this algorith that can uh produce a verification key that is just specific for a circuit let's say Okay so this this derivation takes the CRS and the index so think of it that it takes a description of the circuit and produces a verification key for that circuit and this is a deterministic algorithm

and IDE is that he runs internally the indexer of the polinomial IOP gets the polinomial P Zeros and it commits to them and that's your verification key now uh how do we generate proofs the um the prover of the snar on input the index the um statement and the witness will run internally the polinomial IOP prover um with the difference that the instead of calling the verifier interactively he will uh use the random Oracle to replace the the the interactive part of the verifier so for example it means that Row one instead of

being given by the verifier is actually produced by the random Oracle on the transcrip that starts with the verification key for the um relation and the statement then um the prover uses this challenge to produce the first polinomial P1 using the polinomial IOP Prov commits to it and then again gives it to the random Oracle and and so on and so forth and this goes for our rounds so there is no interaction so the Prov essentially interacts with just the random Oracle which in fact in practice then it will be an as function okay so um then the next the last step uh consist into um intuitively into proving

to that the polinomial IOP Val fire would accept if with these pols P1 P so uh so in uh when we use polinomial commitment to do this um we do this in the following way so recall that the goal is to prove that for all K this polinomial is zero and this is a polinomial equation so there is an indeterminate X so in order to prove that this alss we will sample another random Point uh you know row r + one um I mean again it will be given by the random Oracle um and and then we prove that evaluation of this polinomial on

row + one is zero and however how do we do this by uh essentially Computing each input so each VI K of R plus one which is the input of the polinomial pi in this um In This Very ific ation test that's the input and then we compute the output and then you add an evaluation proof that y i k is equal to Pi of X Ki you know for every ink or for every ink that are involved in the in the test um GK okay so this is the the you know if maybe if you want to link it to something that

you may know like if you know PL for example in that case uh all these VI pols are essentially the uh identity function polinomial for example it's just X and in some one in one case actually you do it on this Omega time x so where Omega is this root of unity maybe this allows you to you know for those familiar with PL to to U Le to what you know okay so [Music] um okay so that means that the proof of the snar consist of all the commitments that you send that you produced right so the commitments to the polinomial IOP uh polinomial and then uh the outputs of

the evaluations of all the polom that are involved in this test and the respective uh evaluation proof of the polinomial commitment what the verifier does the verifier uh will be able to just um you know by reconstructing the transcript of the random Oracle will be able to produce the same um test polinomial right and then you will check that um the evaluation on row r + one is is is zero given this promise is given by the pro the Y Ki values but in order to uh you know since the verifier does not

trust the prover it will have also to check that um the evaluation proofs are correct right that for each um uh you know that if CI is a commitment to polinomial Pi when you evaluate it on VI K of R plus one which is the input of the polinomial then you get y Ki right so that's essentially this you want to prove this statement all right so this is the the the compiler okay and the you know several Works um have proved that essentially this compiler um gives you knowledge sounds snars right if the polinomial is knowledge

sound and if the polinomial commitment is um essentially like knowledge sound as well okay so the question we ask here is that whether these Z Nars are simulation extractable okay so uh and I'm going to show that actually in a universal sense they are not so there are actually three potential attacks that you can mount okay so [Music] um okay so the first attack um this is more like a visibility attack okay so

maybe it's not the a natural one but it shows that something may may go wrong um consider the following relation so it's a very simple relation that uh for example test for asper images of two values so in the public statement we have two value X1 and X2 and you test that you know W1 and W2 are as images of X1 and X2 respectively um and assume now that you have a polinomial IOP to just prove uh you know one execution of the ash right so piop is a polinomial IOP protocol that can prove that X1 is Ash of W1 and or X2 is I mean any X is as of of some

W okay so uh and for some reason this is maybe the artificial part assume that in order to U design a protocol for proving the conjunction of these two um Ash computations you compose this polinomial IOP with itself in a sequential manner okay so it means that you first run the polinomial p on input X1 W1 and then you run the polinomial on input X2 W2 so you know this is what is in the picture and we are assuming any polinomial op and it's a good one right so it's not that we are assuming like an insecure polinomial P now when you plug this in the

compiler uh your proof is something like this so you have um I mean here I'm just using what uh we have in the previous slide so the proof consist of all the polinomial C1 CR for the first execution along with whatever are the evaluations that you need to test this polinomial op and the evaluation proofs of the polinomial commitment and then you will have another set of commitments and evaluations and evaluation proofs for the second uh uh part of the protocol that is the second execution of the Pol Val P but on the other statement okay are you are you with me on yeah yeah yeah yeah okay

so now uh one crucial observation uh is that if you compile this uh this this aop obtained by the sequential composition in a standard way uh what one would observe is that all the evaluation of the pooms in of the first execution will depend on a random challenge that uh is uh chosen even with the random mocol will is only depends on the first part of the protocol right so uh because you know if you compile it in a standard way like you would stop here and then the test of you would run the the verifier on X1 and

you test at this point so but the this verifier doesn't know this other execution so we'll just give you like test that depend only on the uh on the first um you know the first part of the protocol so with this observation we can mount the following weak malleability of do okay so um so consider an adversary that uh chooses uh like an X1 at random right so this means that it's a string for which you know possibly she doesn't know uh the the preimage and then chooses X2 so that she knows the preimage W2

um then she asked a simulated proof on X1 and X2 and she gets it and this proof is you know we can pass it as two portions like Pi one which is the you know is exactly as in my slide so it's the proof for the first part of the polom P protocol and then pi2 now the um observation is that let's say that she uh comp she can compute another pi to Star by running the polom IOP prover for the second statement but with fresh Randomness and I'm speaking about the randomness of the Prov right the random you would use to make it zero knowledge so that will cause um the

following thing so at some point if this polinomial IOP is zero knowledge some of the polinomial in the second execution of the protocol like here in the red part will differ from the Pol in the other execution even if you reuse the same weakness W2 right because it's simply you are using uh you know for example you randomize the polinomial in using different Randomness so the moment the pols change like also the commitments will change so this Str ret will diverge so this proof Pi that it's why this proof pi two star is different from PI 2 and um but the concatenation of Pi 1 and pi2 St will be accepted because

essentially the verification of the two parts is independent and in particular the first part the random Oracle like sorry the the polinomial of the first part of the proof are not um are going to be evaluated on points that do not depend on the second part of the proof so the random challenges essentially that here are the same as in this proof so if this Pi one passes this one will pass here as well so uh and that shows how you can create a new proof for uh the same statement that you for which you have seen a proof um okay so that's one um yeah I see a question uh go ahead yeah uh sorry

wouldn't be actually an attack because uh we didn't perform F shamia correctly and we didn't put all of the witness in as input ofam but so it's not necessarily because we have two piop we could have the same uh we could have the same error if we uh if we don't commit to all of the witness right okay let me clarify this so in F you don't Ash the witness right because the the verifier will not have the witness you ask the statement yeah yeah sir and that's why like if you notice in in my example attack the statement is going to be the same so when you run this x so in the first and the second execution you do it on the

same X yeah sorry my so but it's a good question I mean it's in some sense this shows that it's only a weak malleability attack and it's not trivial to to uh you know to extend it to let's say to change statement okay um now one good question that this is let's say a warm up because I'm showing that uh an attack for a polinomial IOP that maybe it's not so natural right because it's okay I mean actually this would be very unnatural to do sequential composition if you are just proving two statements that are this joint you would actually probably parallelize it um but now I'm going to show what uh that actually it's similar

attack would apply to polinomial iops that are very natural because actually there are the polom that are underlying Marlin and dunar um so so in this attack I'm considering a broad class of polinomial I that I call to have um a delegation round so what's a delegation round so we say that the Pol is a delegation round is if at some point of the polom IOP protocol uh you have you are sending com a commitment or in general you're sending a polinomial that uh only depends on the index pooms and the random and the previous random challenges and that's actually something

that happens in some polinomial IOP because the last round typically is about essenti having a polom that is a compression of the description of the circuit of for examp of R1 CS matrices and the verifier would actually know this polinomial but it doesn't want to to evaluate it because it's too it's too large for for the verifier so it's delegating the the uh um the evaluation of this polinomial to the Prov okay so so important thing here crucial is that the Prov is sending a commit to a polom that is public and the polom is going to be evaluated well actually no and that's it

so the important thing is that it's public okay now um and um but another observation that actually is important to for the attack is that all the polinomial that come that were sent before this delegation round will be queried on points that depend only on challenges before the delegation round okay so that means that these pols V1 of K are constant polinomial in the in their input and again this is a property that Pol such as those in Marlin and lunar satisfy okay so it's not this is to claim that it's not something unnatural now but again for such the compilation

of such poal IOP we can break the proof in two parts in two parts so there is the part you know for the first R minus one rounds and then there is the part about the last round now the attack would go as follow so um the um the pro would ask a proof for uh for X for a statement X you know again the attacker doesn't know the weakness for X but she gets this proof Pi 1 pi two and then she uh computes uh a different Pi 2 part uh by Just For example Computing a freshh commitment to PR of x okay so here I'm assuming assuming that we are compiling this with the Ning

polinomial commitment okay so uh so you can commit again to the polinomial the polinomial is the same in both executions but when you generate a commitment with fresh Randomness the commitment is going to differ now the moment you send a different commitment the the randomness that comes after it so the random Oracle computed on this commitment will give you a a randomness uh raow r+ one star which is different from the one of the you know of the other execution so um and then like the the important thing is that since the polinomial is public the adversary can compute honestly evaluation proof for with

respect to this fresh commitment because she knows the polinomial right there is nothing hidden in there um and and that's essentially the the you know the the new proof so you have xstar is actually X so again this is a weak malleability attack because we are not creating a new statement is a statement that we have already seen but we came up with a uh with a new proof for the same statement okay so is this clear and I I will recap about maybe what we can learn about these attacks I think everything has been clear so far yeah yeah okay so and then I want to show a third

attack that uh is an attack that would work regardless of the polinomial IOP protocol um and it would be based on the fact that you know on the possibility that the polom commitment is malleable I'm not saying that Pol commitment have to have this malleability but is to show that if they are malleable or then this is a problem so so first of all what does it mean polinomial commitment malleability for this slide we're assuming that given an evaluation proof Pi uh that is accepted for uh commitment C point x and output y then you can compute another commitment C star and

another proof P star that are valid for C star xar and Yar where xar is different from X and Y star we don't care maybe the same maybe not okay so if you have any polinomial IOP and you compile it with such polinomial commitment um uh you know the proof would be the usual proof it consists of all the r commitments and the corresponding evaluation uh proofs now what the adversary can do is to first ask a proof for um X right so for some statement X that for which she doesn't know the weakness she gets the proof and then she executes the protocol again um for

another statement xar so she tries to like essentially execute this protocol uh um U following the the honest execution but she does the following so whenever she has to send a commitment she actually sends a commitment c i that is obtained by using this Mal ability attack so you know I'm not saying how to do it it's just that you know it's possible to get given C it's possible to get some commitment C star I and that's what she she plugs in the um in the protocol she gets like um random challenges right so uh the random challenges are going to be different from the ones of the um you know of the

proof that she has received because commitments are changing um and also because actually the the statement is different and then she can use this malleability attack in order to come up with a different proof uh for U for this new statement and you know this this of course is possible if it is possible to break malleability of the polinomial commitment because she has seen these blue proofs for um you know for for these other statement X um but there is a simpler way if you wantan like to to see that this is malleable like in terms actually is weekly malleable if the polom commitment

admits randomizable proof then it's actually trivial you just get the proof uh for x and you randomize just evaluation proof and this gives you a different proof for the same uh statement okay um okay let me recap what I've shown so in case you you got lost so um I showed three attacks um to uh against the uh simulation ract ability of Zs obtained using this Paradigm of compiling polom IOP with Pol commitments and F Shamir um the um right so what lessons can we learn about these attacks because there could there are important

observations that we can make so in the the uh so if you remember the first uh attack is this sequential polinomial IOP composition um and there are the and I mean okay this is also so a common issue in attacks one and two is that there could be polinomial iops in which some polinomial are going to be evaluated on points that don't depend on the last round or they only depend on certain rounds let's say right so um and this is a source of issue so it's it was a source of issue in the sequential composition but one could say okay look maybe sequential composition is

artificial but actually it can be an issue in in protocols where you have this delegation round where essentially it's a protocol where you could stop at a certain round if you don't care about efficiency and then you move on just to uh to obtain efficiency but this class of protocols would suffer of the fact that you know the point you would where you would have stopped now you would query the polinomial on points that don't depend on what you send next um now uh the I want to mention this delegation round is not present in PL so actually PL would not suffer this uh vulnerability um and is present in

Marlin or lunar but it is actually fixable in the sense that um you could add an artificial evaluation uh um of these pols on um actually all polinomial on a uh on a fresh Randomness and this would actually uh remove this this vulnerability yeah go ahead I see a question if I Rec correctly the way on how to fix these protocols such that uh these issues do not happen also comes uh together with your work on this paper right yeah yeah right we're going to see yes um okay in some sense we Define a general condition that a polom uh might

have to to not fall in these under under this attacks and is it then explicit proven for such schemes or you just leave it in the general case and anyone canaly it's a no it's um well it's something that it's most most than proven it's something to check right so yes because it's a very simple prob you just need to check that there is a query to all pols on a random point that is sent at the very end okay so it's some sort of recipe that for these past things I mean you can do the analysis there can do it for future uh schemes it's just a recipe that you can include and you just get simulation

extractability or know Sally right right but I will also mention that actually we have another ongoing I mean we have ongoing work to avoid applying this patch okay so yeah maybe one thing that I right so I didn't stress too much is that for this second attack with the delegation round to work the commitment must be an iding commit mment so for example like it's It's Curious that maybe accidentally like for example in Marlin they said okay look since what you commit is to a public Pol you don't have to make it commitment so the the general compiler recipe says that you just use the commitment scheme as it is but then in the optimization paragraphs

they say oh actually you don't need to to use an iding commitment for this round so you use a deterministic commitment and it turns out that if you use a deterministic commitment there and let's say proofs are unique you would not suffer this issue makes sense thank you okay so the third attack which is the one that would rely on this potential malleability of the polinomial commitment is the most devastating because as we have seen you could even make uh appr proov for different statements now an observation that for now we'll keep it high level is that uh this could be fixable if we require the polinomial commitment to be simulation extractable okay so uh this suggest that

maybe the uh tentative goal of that we could achieve uh could be something I youan know a compilation recipe that is the following one which could say okay take a polinomial IOP but not any one any polinomial IOP like one where all pols get evaluated on some challenge that is given at the last round then use a polom commitment is simulation extractable and then use f Shamir as as we described and then what you get is a simulation extractable Z Nar now the U this recipe may work I mean honestly we didn't uh prove it uh in our work um but the problem is that

you know and this was was also our interest is that um it would not capture existing construction why because the many Construction that we know rely on this kcg polinomial commitment that is quite Mal you know and I'm going to show some malleability of tax in the next slides so so that would be a problem because like then you know okay this goal would not stand because this assumption on is not satisfied by several instantiations so okay so to uh I I see that I'm already on over one hour um I mean for us it's no worries like you

can take as much as much you want since I try to maybe keep it in 15 more minutes or something like sure because I guess also people may get get tired and it's harder hard to follow um all right so next steps I I'm going to show you first what malleability or non malleability you have in kcg um and then our trick will be to to see that actually um the attacks that we can mount the malleability attacks against kg that we can Mound uh do not help to break Z Nars and we can do show this provably and uh essentially we would

show a sufficient condition uh that kcg meets and that allows us to to obtain simulation acceptable snars all right so uh um yeah but so is everyone here familiar with kcg uh because maybe this is something that I could um where I can go very fast I think we can just assume it for the sake of time if you want we can just assume it but if I mean okay happy to listen the explanation to be honest but if you you and go faster you can definitely go over it I I'll go very fast so here maybe just to set maybe maybe it's more important to set up the notation that

I'm using uh so that you follow the next slides okay so we are using bilinear groups of prime order P um and I'm using this additive notation and bracket notation for group elements that essentially for some fixed generator so if you have a group let's say G1 and you have each generator little G1 to denote G1 to the power of alpha we're using this bracket notation where we put Alpha inside the bracket and the subscript in you know refers to which group we are in and then I'm using I'm modeling everything as a additive groups and additive operations okay so the CRS of kcg is these powers of a secret Point s uh

given in the exponent so like in group one and then we keep just the generator G2 and G2 tods in group two for some random s how do we compute a PO a commitment to a polinomial p we just compute in the exponent P of s so this can be done by because if you have the coefficients of P you can just do linear operations in the elements of the CRS and then in order to uh prove evaluation in a point Little X what you do is to compute um in the exponent this polinomial Q which is the result of dividing u p minus the result P of x divided by the the polinomial essentially um okay I

use bad notation but it's like capital x minus Little X right and the the the the proof is the evaluation in s of this polinomial q and how do we verify essentially we the verification consist in using the pairing to check that uh Pi is well formed and the interesting uh property of kg is that this proof is unique so there is only one p that satisfy this uh this equation all right so one thing that may maybe not everyone um may be familiar with is how do you simulate proofs uh and what does it mean actually to simulate Pro so let's say that you want to now simulate a proof

for commitment C input X and output y um what the way you would create a simulated proof is by taking C you subtract the encoding of Y in exponent and then you exponentiate to the inverse of s minus X so this is a way to create this unique proof for uh EX for this statement and clearly this requires the knowledge of the trapdor S okay so this is the the simulator the the Sim the simulator for the proof algorithm okay so uh I was saying that kcg is malleable um and I'm going to show you you know some simple attacks so this is not new because it's based on

the fact that kg is I mean as an morphic property that is actually a useful property um so assume that you have a proof Pi for CX commitment C input X and output Y and this means that you satisfy this equation up here then uh it's very easy to create an a a proof which is actually the same proof that the same proof holds for a different commitment C plus some Delta and another result which is y plus Delta this is Trivial and it's if you want the intuition is based on the fact that if you have a proof for evaluation of a polinomial p on y if you shift a constant term by Delta the output will be shifted accordingly by y

so that's and then like you know another way to see is that the um the same essentially plus Delta here and minus Delta will cancel and that's why the same proof alss what is perhaps more interesting is that um you can also create proofs for different points if you can change the commitment so okay let's say that you have seen a proof for commitment C input X and output Y and now you are given an arbitrary Point xstar um and you create C Star as C minus the proof Pi uh multipli by xar minus

X okay um and then uh the okay xar is the the input and Y the same y that was like the output for the other proof uh we we reuse it okay so I'm going to show I mean or you can see actually check the what is in the slide that Pi star so the same Pi star equals 2 pi is a valid proof for this uh fresh statement uh and um notice that you know if you have seen a proof for which you don't know the witness which which means that for which you don't know the polinomial one is able to generate a proof for something for which you don't

know the full polinomial inside uh yet you can generate a valid proof I mean and if follow this equation that tell tells you why that uh you know this is a still a good proof um and yeah I mean okay I can't read it but it's really what you have to do is to uh take the verification equation for pi star observe that you know s minus xar can be written as s minus X Plus xus X Star right and then you use the bilinear property to split this s- X and plus xus xar in you know in two pairings and then you use the fact that

this is equal to C minus y paired with one given the fact that Pi is a valid proof for C and Y and X uh and then here we use the fact that we are redefining the commitment C Star as C uh minus this [Music] um well I me there is a a minus sign that is is wrong here no actually it's correct right so the commitment we redefin as C minus the these you know value times the proof x starus x times the proof okay so

um okay the the good news however is that in spite of these malleability attacks these specific attacks are not enough to break the simulation extractability of the zig knars obtained by you know using the uh this poal commitment in the compilation strategy and uh so what why is this the case um so for Simplicity assume that you have a polinomial where the polom are evaluated on directly the output of the random orle okay it is actually the most common case then what happens is that these attacks require to change the commitment so the moment you change the commitment you get a different random challenge so that means that the first

attack does not apply right because the you know the the first attack is about creating a an a proof for a different commitment but on the same point x so now the input is is changed because of f Shamir but another thing that gives us F Shamir is that the you know the moment you you place your commitment you don't know what the random challenge will be right and that uh also defeats attack to because in in C star so even if you can this work for an arbitrary point xar you have to fix this point the moment you choose you fix your commitment in the attack

okay so okay so this defeats both attacks um in some sense this the interesting observation that we will use is the fact that FIA Shamir is of help uh in the fact that we get evaluation points after the commitment but there is another type of malleability that you can mount a malleability attack that you can mount if you are in a full-fledged simulation um extractability experiment where you can ask arbitrary um statements to the to the simulation Oracle so assume that you have asked um a proof for commitment c um and um input X and output y1 and then later another proof for same

commitment C same input X and another different output Y2 so um the simulator will be able to to uh generate these proofs um and if you have these proofs um you can actually create a proof uh yeah maybe I'll go fast on this because this is more Technical and people will be able to um check it on the slides by themselves but the m point is that you will be able to create a commitment that does not depend on the any point that you're going to see in the future but then the moment you know a pointex star you can create a proof P star uh

about evaluation of you know that passes the evaluation on carar for some point why I mean actually whitear is a certain form but if you then apply the attack one you can even do it for an arbitrary start so okay feel free to check it I mean this is actually I think we have it even in our paper but the what is important is that this shows that if you are in a full-fledged simulation tractability experiment uh and you can ask these queries then you can uh create an attack that uh works for any Exar that is chosen after the commitment now um a note is that this

attack is a bit unnatural uh if you want like because it's kind of really asking the simulator to prove something obviously false right because he's you are asking can you prove that if if you have something in this commitment on X gives you y1 and then later you ask oh now prove me that it gives you Y2 on for the same polinomial and the same input so right so this one can everyone can test that this is false so uh and actually this is why you know this attack is of no concern for the simulation extra extractability of znar under the condition that U the polinomial IOP

um way you you know the way you see you uh prove zero knowledge in the polinomial IOP would not create this kind of strange queries so essentially as long as the [Music] um yeah I mean the the view that you simulate is consistent is what we called algebraically consistent it means that you are giving some uh evaluation outputs uh that form a A system that is that admits a solution for which there exist a polinomial uh that um can give you that um those outputs then uh you are not going to run in this in this

strange case go go ahead Carlos I see that is this something that is also uh enforced or or requested in the paper from about simulation in if I remember correctly 1992 or or I don't remember the year exactly but the first paper that you mentioned where simulation extractability is defined is this kind of property something that is also asked uh no because this is a very something very specific of that we are asking for of polinomial IOP or or do you refer to the fact that you don't ask false statement exactly yeah yeah no no actually it's you know if you're interested in this there is a in general in simulation soundness or

simulation extractability you can ask whatever you want even false statements and this does not should not help you to prove false new false statements uh then there is a relax notion called true simulation extractability or true simulation soundness in which you can only ask uh true statements okay but uh yeah okay okay okay thank you okay so an interesting observation is that I mean we um it seems the case I mean we don't have a proof but it's uh it could be an interesting something interesting to check is that essentially any polinomial IOP uh that you want to use in the

compiler would have this you know this property that essentially The View that you generate does not raise this um essentially inadmissible uh uh queries yeah I mean but I'll jump fast on this okay so um based on these attacks so again recall that maybe very fast we have seen three attacks one shows that if you can change the commitment uh you can create proofs for other statements but like it will not work if the evaluation point is chosen randomly after the commitment and then this

attack says okay if you can ask this um sort of dangerous queries you can also like bypass this check of you know essentially it will work you can do attacks even if the point is randomly chosen after the commitment now this suggested us that actually we could uh prove some form of simulation EXT extractability for kcg um and this weaker form uh is a form that con uh um respects the following game so it's a simulation extractability game in which the uh adversary has access to the CRS of kcg can ask simulations of um

simulated proofs for commitments and uh statement uh input and output um and then has to produce uh a proof and the extractor must produce sorry must produce a commitment input output and proof the should produce a polinomial and we check that the proof pass verification and that whether you know the polinomial is either not the PO the committed polinomial or the evaluation is incorrect now we even consider this game in in the presence of a random Oracle um you know in the simulation video game is essentially

simulated um now uh and the restrictions that we use um in order to bypass those attacks uh or actually to not consider those attacks it's not that we bypass them um are the following so first of all uh we give to the adversary a set of points QX um that for now think that it's an arbitary set of points and then a set of simulated commitments U for Simplicity you can think that these simulated commitments are just random group elements in casg chosen According to some distribution um and then the first restriction is that whenever the

adversary ask uh the simulated proof for cixi yi the point XI must be in this set that has been chosen at the beginning okay so essentially we're saying you the adversity cannot ask adaptively um queries on evaluation queries on points over choice Choice she can actually choose these points at the very beginning but not uh adaptively later the uh second check is a okay it's a bit um technical check but and is it's about algebraic group model so if the adversary is in the algebraic group model and whenever he produces this

commitment in the query it must also produce a a group representation so it actually yeah a coefficient representation of this group element CI then this representation can be so this commitment can be written as fi of s plus some linear combination of the simulated commitments so what this is saying essentially is saying that she cannot ask uh simulated proofs on commitments that are in the linear span of um of the simulated proof that she has seen the previous rounds so this sounds kind of an natural restriction but we will see that it's will be you know sufficient

for our compilation and um the last requirement is that all the these simulation queries if you look at all the pairs x i Yi essentially must Define an admissible uh system of equations so it means that for example you cannot ask x y and x y Prime for y Prime different from why like you know this is the simplest example U so you cannot ask things that are obviously um false in a certain way uh and the last uh check that we that we do um like is that the point xar chosen by the adversary essentially it's

randomly chosen after C star and this is formalized in terms of random Oracle in the sense that like um if you the adversary must have query the random Oracle on the commitment and the output of the random Oracle is used to compute xar using some polom H that can be arbitrary as long as it's of degree at least one right cannot be a constant polom so for example this like if you think again about PL this H can be either the identity function so xar is Row the random challenge or it can be you know root of unity times row so now like um what we we want here is to um that

the adversary index trctor win if they play in this game under these rules so this some simulation setability means it's not that you can ask whatever you want and you can give us just something new no it has to be it has to fulfill uh these uh these requirements okay so um the uh okay this essentially tells us what is now going to be the strategy uh is instead of requiring that the poal commitment is just simulation extractable we will require that is more or like some simulation extractable precisely we introduce a notion that we

call policy based simulation extractability which is a generalization of simulation extractability that can capture both full-fledged and simulation acceptability and other variance because it's a parametric notion that depends essentially on the policy that that defines the checks the the winning condition of the game um and the and then we identify specific policy that is sufficient for the compiler to work so to obtain simulation extractable ZN and this uh so sufficiently strong for the compiler and sufficiently weak uh for kcg to to to meet it um yeah okay maybe at this point I'll I'll I'll I'll go I mean fast because I

guess it's I'm taking really a lot of time okay so very fast like the notion of policy basic simulation extractability is simulation extractability with these additional checks that consist into um giving to the adversary not only the CRS but also some parameters uh that we fix at the beginning and then in checking that in the winning condition not only something is uh you know the produces a valid proof and the extractor fails but also that whatever the adversary produces satisfy certain condition that generically is you know expressed by a policy a predicate F1 okay so in this sense this is a very

um generic um notion that is parameterized by whatever you put in F1 okay so essentially it says it's simulation acceptability with a additional conditions so for example full flx simulation acceptability says that this condition just checks that xar P star is new right so that's that's an example um yeah okay so maybe I'll um yeah I think I'll I'll I'll I'll go fast on this because it it whatever you prefer no worries yeah I I see that yeah

I think it's it's relevant to jump to conclusions at this point so anyway so the very briefly on this slide is like we Define the compiler uh which is essentially the same compiler but uh then the main point is that to prove U that um if you have a polinomial with some extra requirements if you have a commit and Bru Nar for polinomial evaluation that is simulation extractable according to a certain policy and you combine them using F Shamir we get zik Nar are fully simulation extractable um okay here I'm defining the what are the sorry the what is the policy and what are the requirements um I I'll maybe discuss the requirements of

po p in the last slide better and we show that batch kcg so this batch version of kcg um is simulation acceptable According to some Poli that implies the policy that we need in our compiler so that tells us that we can instantiate the compiler with b casg um okay so this is maybe the the most important conclusive part um you know if you care about results um so so our results and our framework uh imply that uh we can show the simulation acceptability of the following snuts so

of PL basilic I mean basilic is this scheme by um Raffles and zapico from crypto 20 21 um that I mean it has a structure not too different from blong now for these schemes it um we can show simulation extractability if you compile them without the so-called linearization trick uh which is this trick that is used to reduce proof sides uh when you have to uh Pro some equation of this form let's say you have committed polinomial a b and c you want to prove that a of R * B of R plus C of R is Zer something like this and the trick says okay you instead of sending you each

evaluation I can only send you for example B of R and then I prove that this P of X polinomial computed in this way evaluates to zero so unfortunately we cannot capture this because it's uh it's a more complex way to prove um uh essentially this polinomial checks of the polinomial IOP that escapes our analysis so far but the good news is that in terms of polinomial IOP this um the polop underlying this plun and basilic satisfy the requirements that we that we need um that um yeah yeah okay you can probably see the paper for more details about

that unless you have questions that you're interested in and then um the uh about Marlin and lunar that have similar structure uh we cannot capture the full fled protocols because of this delegation round so that means that the original I Pol IOP fail to satisfy this compiler safe property ENT is the property says you have this evaluation in the last round um of all polinomial but if you add this to the Pol P then we can uh again capture them um but again without this larization trick okay so to conclude um what we

covered is an introduction to simulation extractability we have seen what are the challenges of proving simulation extractability uh for um uh you know snacks obtain using this compilation strategy um hopefully I gave you some ideas also so you know what's the challenge related to the fact that kcg is malleable if you care about um um SNS based on kcg and then I showed um you know what is the recipe that you can use to obtain um um simulation acceptability so I mean probably some things are already apparent so our work has some limitations in particular we

still miss to capture the fully optimized variant that people actually use um and and uh this is because of two reasons is because of the linearization trick and because of the delegation rounds that you know this uh schemes may have and we have some ongoing work to um to fix this part um and but on the other hand like the the good part is that we have a general framework to uh because our goal was not just to prove existing simulation cability of existing constructions but to give a recipe so that people can just come up with new IOP and with a few checks they will know that they will be compiled with to something that is simulation

extractable um and another limitation is that our compiler part like is um based on policy based simulation exer ability is tailor to pairing based polinomial commitment because some of the properties that he uses are specific for algebraic adversaries in you know in bilinear groups and with this I thank you than you for the attention and I mean I apologize for taking long time but I hope this is useful to be checked offline you don't need to apologize for anything it was really nice and and really really insightful um I have some questions uh I want to leave room to Rafael in case he wants to ask uh

anything or any any other person still here otherwise I I will ask so I will wait a couple of seconds sure so um May I assume that uh you target uh you targeted or you consider kcg as I at least got the intuition that seems to be the the the less strong uh polinomial commitment scheme in terms of simulation extractability hence you targeted it so that you have enough flexibility for upcoming work such that it can be adapted directly to this uh recipe right right okay that makes sense yeah in some sense it's like you know one easy way

would be okay assume that your PO commitment is already very strong in terms of norali ability and you get something quite easier but then this would leave out uh a lot of existing constructions and in some sense like you know our um motivation that is the fact that you know there are constructions and constructions that are used uh and the question is like are they already simulation extractable because if they already they already have this property we don't have to worry to change them yeah right and [Music] um and following this this this line is this upcoming work and generally the the

trajectory that you're following now to try to come up with a fully genetic and whether do you think it's possible I guess that's the question to come up with a fully generic a recipe for upcoming work such that simulation extractability can just be a list of checks that my polinomial commitment plus my construction needs to pass or do you think this is unfeasible and and there will always be like the need to do some ad do work in order to check these kind of properties um I mean right now like um in terms of polinomial IOP the the checks are very easy so uh actually I mean I didn't spend time to describe

them but the property we ask I would say that they are very natural uh in fact they you know they are met by several construction except this delegation round issue but we do think that this is bypassable I mean in by just changing something in the way we not no actually without any change just by changing going for a different analysis mhm so perhaps the main limitation right now is like yeah maybe capturing a broader class of polinomial commitments um I think it is doable what I find uh challenging and maybe it's my personal experience with this type of work is

that often when you want to be very general uh it um you have to consider a lot of corner cases right because um because yeah like especially it's like when you have to analyze things after the fact right it's probably what happened with many I know sometimes I like to say that what we have been doing is similar to what people have been doing with like TLS protocols years ago like what you know the very first version were not designed with many you know a lot of provable security in mind or with you know they were designed with some basic properties in mind but then people you know developed a lot of theory and

then and it was very difficult to to catch and model them formally and here is something similar like you know people have designed protocol with knowledge soundness in mind which makes perfect sense because it's the you know very first property that you want knowledge sness is very tricky so what with this what I mean is that sometimes we realize that without any further costs if uh you might have add that Pol oped that was likly different and it would have matched our conditions in a more I see um but yeah maybe the two options were equivalent and what would go for

something what what is actually also interesting is that nothing seems to break down right so in some sense like maybe even unconsciously like this design is the designs are resistant to malleability attacks that's fair although it's it's I mean it's it's also true that maybe there's not enough uh research or or I don't know how to say it there's not enough mower to put it on some sense to try to catch up uh these things so that maybe nothing breaks so far but because we haven't done some analysis and I ignore that of course

because I'm not deep into into this topic but uh I don't know how broad and extensive the this person I don't think they you know they don't break because we have not analyzed it because I mean our work for gives evidence that they are simulation extractable maybe still with this caveats but fa enough I think it's more like that they actually what is probably the the reason is that this works really rely on F Shamir that is known there are other words that for in the case of Sigma protocol show that f gives you something that you know gives you simulation soundness um

so it's not a coincidence yeah they they resist to these attacks I see I see I see I see I see but unfortunately what maybe it's the fact that like just F Shamir does not I mean what we have shown for example is that is f Shamir does not give you simulation soundness or extractability for free in the case of these schemes makes sense makes complete sense thank you very much for your for your an and I think we can we can wrap it up here so thank you very much and we're really grateful that you came and and and did this really really good explanation at least to to my perspective of course uh thank you very

much and and you're welcome to come any any other time you you want yeah thanks thanks to you for rting me