Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions - Roberto Parisella

Transcript

hi everyone uh thanks a lot for joining us today at uh Lear and share today we're going to have a talk by Roberto Parisa on Conant si zik in Rome from F cable assumptions so thanks a lot Roberto for uh coming here and giving this talk I'm think about it uh we had a few talks on uh uh kg uh Sun Ness and so I'm reallying looking forward to this talk thanks um so thanks for the introduction um can you hear me right yeah okay so this is a joint work with helar Lima and yanim and the paper

has accepted to the next eurocrypt and this is I think the first presentation of this paper uh so let's uh jump into it um the talk will be divided into uh four different chapter let's say I will start with some preliminaries and also explaining the main motivations for our work and why should we care uh then I will present uh the main result of this uh paper which is a new um security proof for the uh kids AG extractability uh of course I will I will Define uh the kids AG commitment scheme in the torque and also explain

what is uh its exportability property then I will briefly present uh what we built on top of our first result so second result uh how we actually construct the cant size Nar in the random Oracle model provided in the title and lastly I will briefly mention some open questions and uh uh some of them actually we have found some solution which will come um in the form of a follow-up work okay so let's jump into the first uh

section um when we think about this uh circuit satisfiability problem uh that are actually the problem underlying most of um today's Nar application we can think of having a public arithmetic circuit as the one uh here in the slide and then we have a public statement uh uh X and uh uh a witness W for X which is usually private uh and W is a witness for X if uh we plug W into the circuit we evaluated it and we get back uh X so the public statement uh there is a flourish branch of cryptography which study uh

equivalence between this kind of problems and other problems that comes in the form of constraint systems so uh many different constraint system exists um here I just want to give you some intuition of what is uh a constraint system and uh um why I would like to do so because like then we can understand what is the problem underlying snarks that are deployed by Industries and use it and constraint system is none other than a set of public equations such as maybe we can think about them as polinomial equations of a certain

forms uh then we have this public statement X and witness W and W is a witness for X if uh we plug uh X and W in this constraint system and we get that all the equation are satisfied so usually it's an equivalent form of writing arithmetic circuit for instance each gate of the circuits Define uh an equation in the constraint system uh then uh moving on what is a zero knowledge argument um it's a protocol basically engaged by uh two parties uh Alis the prover and Bob the verifier and I Define it directly into

the SRS model using a constraint system as a um an language example or an application example for this zero knowledge argument so um SRS stand for structured reference string uh and uh it means that we suppose the existence of a trusted third party that comput this SRS and uh makes it available to both Pro and verifier as an input then those two parties also have the public statement Tex the approver as uh the private witness W and uh um they start to interact and exchange messages according to what the

protocol prescribed and at the end the verifier output accept or reject and it should output accept if and only if it is convincing that the approver knows the witness but the point is that um the interaction should not reveal any information any additional information about the witness beside the fact that the approver should indeed know it if on top of that uh we require uh no interaction from the verifier so we require that the approver compute the proof in one message and send it to the verify then we have an eix so a non interactive zero knowledge

argument formally um zero knowledge has to enjoy uh three security properties so complete winess means that honest Prov will always convince the verifier which means that if W is a witness for the public constraint system under the statement text then the verifier accept knowledge soundness um means that if the verifier accept then the prover must indeed know a valid witness what does it means well we can image a sort of malicious bler with having some auxiliary information deviate to what the protocol prescribed and try to make the verifier accept by knowledge soundness we want to be sure

that the witness can be computed by this auxiliar information and this is formalized by requiring the existence of a touring machine called extractor which can interact with this uh malicious Pro and eventually extra W such that given the fact that the verifi accept uh W will be a valid witness and last we have zero knowledge uh which is the security property against a malicious verifier so now it's Bob that is trying to act maliciously and learn something about the witness deviating from what the protocol prescribed by the zero knowledge we have that no matter what is Bob strategy he will fail and learn um information about

the witness on top of these three security properties we also require uh some efficiency property and part particularly in this um work we care about strong Suess um guarantees um requiring that um the proof sides so um the sides of the exchange uh of the total Exchange in messages as well as uh the complexity of the verification algorithm they should be constant in the witness sides so independent from the witness sides and uh hopefully uh of a small constant and this is the case for uh uh protocol

deployed by Industries in real applications if on top of this four requirement we add that we need the uh non interactiveness then we have a snark so snark stand for succinct no interactive argument of knowledge and it's a protocol that satisfy those uh four conditions in our case we there are also non size Nars but uh we do not care about them today and we actually Focus about knowledge soundness under the uh efficiency requirement that we have introduced here because completeness and zero knowledge will actually be trivial

for the construction presenting uh here so um I will just focus on proving the knowledge soundness of our snarks which will achieve this suxus requirement um there exists uh a popular framework uh that has been successful in design uh those kind of snarks which is for instance the one used in Blanc lunar and Marlin and this framework uh consists in taking two Primitives the first one is an information theoretic proof model such as iops interactive Oracle proofs but others can be used the second one is to

use an extractable polinomial commitment scheme such as the kg commitment scheme that uh we care about today um and we use the kidg because it it achieves um Conant sides um group and verification complexity and then we take these two Primitives and we compile them into a suin Interactive zero knowledge argument um now we can compile this interactive argument again using the famous Fiat Shamir transort to remove the need for interactiveness and uh we end up with a

snark so um if this framework is uh so successful uh what is the problem because we actually end up with a very good snark in this framework um the problem is the security proof in order to show that the kg commitment scheme is extractable uh we need to rely on ideal model uh to model cryptographic groups uh such as for instance the AGM the algebraic group model or the ggm on top of that in order to show the security of the Fiat Shamir transform uh we rely on a second different ideal

model so uh the random Oracle model uh which means that um the results snark as security that is based on uh two different ideal model which is already uh like not an ideal security proof not a desirable security proof but uh we also have another issue um I will show uh soon uh that the way those ideal cryptographic groups here are used to prove exportability of kid a in construction such as plon and lunar is actually um questionable in

itself um particularly um it result in a proof that do not translate um in the standard model directly so we really need uh a better security proof for this kind of construction and uh since our construction will also use uh the F transform and random Oracle model as this last step during this talk I will only present this uh intermediate step so um I will only um achieve this sucin interactive zero knowledge argument and then one can apply the fatr transform and obtain the

snark okay is there any questions so far uh no we're good thanks okay then I will move on and Define uh polinomial commitment schemes so polinomial commitment scheme is a tole of four algorithm we have a key generation algorithm which takes as input some public parameter and an integer and and output a commitment key we can think of this n as a bound of the degree of the polinomial that we can commit uh with uh this commitment

key then we have a commitment algorithm which takes a public key and polinomial F of degree up to n and output a commitment uh the third algorithm is the opening algorithm which takes this uh commitment key then the couple of commitment and secret committed polinomial F and also an evaluation Point Alpha and output uh EA and Pi where EA is supposed to be the evaluation of the polinomial F at the evaluation Point Alpha and Pi is a proof that the evaluation have been performed

correctly so uh please just try to remind this uh notation because I will uh use it in the pap extensively Alpha here they will be evaluation points ITA uh they will be evaluations of the polinomial so this should be F of alpha in the honest case and Pi uh is the proof to prove that ITA is equal to F of alpha uh which means that the fourth algorithm is amp verification algorithm that takes uh the commitment key the commitment evaluation point and uh evaluation and proof and output zero for reject one for accept and the

point is that this verification should accept uh if it is convincing that ITA is equal to F of alpha for the polinomial F ofx that is committed in C and F ofx should be of degree up to n so let's try to formalize this security guarantees we have usual completeness property which means that if everyone is honest then the verifier accept we have the iding property which I will only Define at very level which means that public information so commitment evaluation Point evaluation and proof does not reveal any information about the polinomial F

beside the fact that F of alal to and then we have this evaluation binding which says that which model the informal fact that the commitment is bound to only one polinomial uh and it's defined by the fact that uh if some like Mage someone that can try to um open the commitment the same commitment at the same evaluation point at two different evaluation ITA different from ITA Prime uh then uh this should be art so no uh efficient St machine should be able to to Output this two different

valid evaluations uh and we do not care about iding because uh like iding is used for zero knowledge and I said already that uh here we only focus about knowledge soundness but those three properties um the the KY commitment scheme as uh all of them under a standard and good security proof what is the problem that uh when we want to use a polinomial commitment scheme for a snark we need um a stronger uh security guarantees uh we need uh that if the verifier accept then the pro must know the committed

polom and this property is called blackbox extraction and it's again uh formalized by requiring the existence of an extractor uh IM men the extractor playing in the following game so we have an adversary the adversary see the commitment key uh and output a commitment and some auxiliar information then someone let's say the extractor output this um uh random evaluation point and then um the Prov um like sorry uh then uh this information like the commitment and auxilary information and

the evaluation Point are user to run a deterministic pro uh which output um um openings and proof If this deterministic Pro makes the verifier accept uh then um we have this extractor that can interact with the deterministic pro and eventually output a committed polinomial so this is the definition of blackbox extraction for a committ scheme uh then I will introduce some notation for uh cryptographic groups it's the bracket notation so uh we have additive ailan group the generator is

this one in bracket the element of Order X is x in bracket and the group operation is the addition which means that this scalar multiplication is the exponentiation those group are cryto graphic meaning that there is some uh hardness uh for instance the discret logarithm holds so given X in bracket it's hard to recover the discret logari X uh but also multiplication should be hard this is the cth Assumption and uh find the element of order inverse should be R this is known as s assumption but uh many different AR assumption are defined for cryptographic

groups and um here I just want to give you uh some intuition of the reasonable hardness that we can assume in this group uh particularly the one that we need to understand our um the construction we use and our security proof so let's say that we have an adversary that receives as input uh group elements of order Sigma to the various powers and this adversary should output a group element of order F of Sigma um we would like to know for which kind of function this is an easy task and for which kind of function this uh can be assumed to be an art

task well for instance if f is a polinomial degree up to one then it's easy to see that this is an easy task because uh the element of order F Sigma can be computed using a um scalar multiplication and addition so or lit operations on the other hand if f is a polinomial of degree more than a uh then this should be an our task because intuitively this is morally equivalent to compute the element of order Sigma M uh which can be considered as a special case of the multiplication which is hard and the same holds if f is a rational function a proper rational

function so the first uh task should be added as a variation of a CDH assumption and the second task should be add as a variation of an S assumption and lastly uh actually groups used uh in um today's application in the state of Arts they have some additional structure so we suppose the existence of three groups G1 G2 and G3 Target of the same order uh p with p is a big Prime uh group elements are indicated with the uh pics on the brackets or their respective groups and then we have this uh bullet here which is a pairing operator defined

as here in the slide so take the element of Order X in group one pair with the element of order Y in group two and we get the element of Order X time Y in Target group but this is basically a way to perform one and only one uh multiplication and to check the result in a third group and lastly uh we require that it is hard uh to compute Isom morphins between the two groups so this is the structure that we have for state of art Bing based cryptography if there are no questions I will move on and present finally the kids polinomial commitment scheme

so I have to uh give you the four algorith the key generation algorith uh sample a random integer and then uh output the commitment key which is on the form of uh group element in group one of power of order Sigma to the valus power up to the chm n and uh the generator and the element of order Sigma in group two uh then the commitment algorithm um just compute the group element in group one of order F Sigma where f is the committed polinomial and sigma is the trap door in the CRS of

course since f is a polinomial degree up to n and um the commitment key contains all element of order up to Sigma n in group one then this is an easy task and we can compute the commitment the open algorithm is a little bit more complicated more elaborated uh first we compute the evaluation honestly so it is equal of f of alpha as it should be and then we Define this rational function H ofx defined here as in the slide so remember that in the Hest case this EA is equal to F of Alpha and the proof is the group element

of order H Syma uh where uh H is this rational function uh lastly the verification equation just uh check that everything has been computed correctly so uh the numerator year of H ofx computed in Sigma which is a variable to the verifier should be equal to this uh H ofx computed at Sigma which is the order of this p uh times the denominator at Sigma okay uh now what is the point of why this uh commitment scheme works and it is secure um it relies on the fact

that H ofx which is in general rational function is actually a polinomial function if and only if EA is equal to F of alpha so um remember the variation of the S assumption that I talked before um if uh the Prov was honest then uh H ofx is defined as a polinomial function and the prover can compute it otherwise if the prover try to compute a valid proof for any other point ea uh then this is equivalent to compute uho rational function and this should be art and from this we can show the evaluation binding property and this

is done in the original paper where they presented the scheme under a nice security proof the point is that we want to show the extractability property for this commitment scheme and uh uh prior to this work it was only known how to do so using ideal models for cryptographic groups such as the algebraic group model AGM that I will briefly describe here so uh the AGM is the model where we assume that each adversary is algebraic in the the sense that um when adversary receives group inputs and uh uh output some group elements such as this C in bracket uh

then uh adversary should know a linear representation of the output uh in terms of um linear combination of its input so we should know this Alpha Gamma and beta integer such that the output T is obtained by this linear representation and this is once again formalized by the existence of an extractor that can uh we can think of this as a very powerful extractor that reverse engineer the code of the adversary and give back the coefficient of this linear representation uh and maybe many of you have already noticed that using AGM it is actually almost trivial to prove the

exportability of the kids AG commitment scheme uh because say that we give a commitment key to the adversary and then the adversary outut a commitment which is in the form of uh some polinomial uh the group element of order F of Sigma where f is some polom when now we can invoke the AGM extractor which recover the linear representation obtained uh us it to compute uh this group element but since the adversary has Sigma to the Val power uh as only elements available in of one then those coefficient are trivially the coefficient of the committed polinomial so we have recovered the

polinomial and note that this is a very powerful and useful extraction technique technique because we can prove that the commitment scheme is uh extractable only um once we see a commitment we don't need to see a valid opening so we see a commitment we extract the committed polinomial and this is how the K G exr ability is proven in plon and lunar for instance and they um um non-trivially rely on this very strong stability property uh to prove on top of that the security of uh many useful and interesting optimization that they use

uh for the snarks such as batching commitment together or uh many of you may know the linearization trick so what is the point uh the point is that does not this not translate to um a security proof of kg in the standard model and the this is true because um algorithm in the sard model can perform oblivious sampling so they can sample group element without knowing their discrete logar uh particularly let's say they sample a seed from a super polinomial me entropy distribution and then they use um a wise

choosen encoding function to encode this s into a group element X then if they choose this en code function wisely to recover X even given the seed is as art as solving the standard discrete logarithm assumption for instance we can use a class of function known as encodings on elliptic CES as this encoding function uh which uh translate to uh one result from our previous paper uh publishing uh the last TCC uh which states that the extraction from the T commitment only without seeing a valid open does not hold in the standard model

so hopefully this convinced you that uh we need a new security proof for theability of the kid AG commitment scheme and if so far if you have no question then I move on to the uh second part of the talk and actually present our new k a security proof you can continue no question SAA okay cool hope because it's clear not because I've lost all of you okay so um the first things that I will present here is the assumption that we use uh to prove the extractability of

the kids AG scheme uh also I should mention um the this um security proof will be in the standard model so we will not use uh any ideal model to prove the acceptability of K AG okay let's say that we have an adversary that receives this input which is uh none other than a k commitment key and this adversary has to Output a set of integers and two group element uh G and S this adversary wins uh the game uh underlying the RS assumption

if uh s is a set of integer of sides M plus1 uh G is not zero uh then let's define this ing polinomial which is the polom of degree n that has a root all element in s so the adversary wins the game if um the order of G and satisfy this uh ping product equations and the IRS assumption um states that um it is impossible for any efficient adversary to win these games with more than negligible probability

and why this is a reasonable assumption uh this assumption is a variant of an already known assumption from Gonzalez and Raffles is the uh RS RS stands for rational strong Def elment and um this suggests the reason why we should believe on this assumption it's because if an adversary is able to win then it has computed this uh five of x which is uh a rational function so it's G of X over Zs of X evaluated in Sigma and as we have mentioned it already a couple of

times uh this should be ar for um cryptographic groups uh but I say A variation because uh in our assumption we give a slightly more power to the adversary so the a in a RS stands for adap uh which means that uh the adversary can choose the set s uh however uh whatever is choose is set as uh if the adversary is successful this c will always be a rational function so even with this additional Freedom uh this adversary should not be able to to win this game and this is just an intuition on why um this is a reasonable um under

looking assumption um I think many of you who are familiar with ping based cryptography can see that the assumption is actually uh quite nice uh those of you who are not in the paper we have some uh um security guarantees on why this is uh like a good assumption and a reasonable assumption to use and to show uh xability we rely on um an intermediate result which is quite standard in zero knowledge field in general uh which is uh showing this special soundness property for the kyg

commitment scheme so let's define this property uh say that we give an adversary the kg commitment key and this adversary is required to Output a commitment and N plus1 accepting proof so all of them should be accepted under uh different uh evaluation points Alpha so this Alpha should be n plus1 different Alpha I if this is the case uh then um special soundness means that there exist an extractor which takes as input um this output of the adversary so the

commitment key the commitment and also um all the M plus1 um different pet proof and eventually compute the committed polinomial which is a witness for the um PDG commitment but what does it means uh exactly to be a witness for the KJ commitment uh well it means that the extracted polinomial has to be compatible with the commitment so if we plug it back into this commitment algorith he should keep uh C so the commitment we have uh use it to extract it uh it should be of degree up to n and uh it should be compatible

with uh all the evaluation we have seen so F of alpha I should be equal to Beta I and our U most important result is this LMA uh to say that under the a RS assumption the KY a commitment scheme is special sound uh I will just give an intuition on why this is true so we can Define the lrange polinomial for a given set S as the polinomial uh here in the slid so we have n plus one different pols then we have the well-known result of lrange interpolation for uh m plus1

one t so evaluation point and evaluation states that the polom F ofx defined by this formula is the unique polinomial of degree uh n up to n uh that um is uh evaluated at each it each of this point Alp gives e i and the special s instructor just exploit uh this lrange interpolation so given the uh input so a commitment and N plus1 accepting transcript for this commitment uh first compute the lran uh

compute this polinomial using lran interpolation uh then check if this polinomial is actually committed in C if yes very well we have find our witness otherwise uh we show uh in our reduction that that we can use all this information to break the IRS assumption so uh since we can break IRS assumption when this uh do not happen uh this should happens with overwhelming probability which means that the kg is special sound okay and uh this was actually like the the most important idea of this

paper uh from now on is everything is more standard and involv the proof technique that uh are adapted from other cases to our uh case so uh now we go uh from uh proving theability of kids a from the special suus and uh first def find theability game for the kids AG commitment scheme so we have this adversary that output the commitment some auxiliar information um we use this to fit the deterministic prover and then we let this PR um interact with the blackbox extractor the extractor first check uh

if the Prov um gives an accepting proof at the beginning and then start to interact uh with this prover and eventually output a polinomial f which will be a valid witness every times um this first proof computed by the terministic pro is accepted by the KY verifier so to show the blackbox extractability I need first to Define this extractor and I show you this instructor in the next slide oh but first uh we have a f we have like a small technical issue so this instructor is um uh allowed to be uh a toing machine that is a little bit

more powerful than the standard T machine we deal with the cryptography because it does not run in strict polinomial time it runs in expected polinomial times so there should be like a small uh number of run of this is factor that can take exponentially long time this is U Allowed by the the definition uh like it's a standard things that is allowed by definition so um we show that uh special soundness imply stability showing the extractor then proving that the extractor Works uh the extractor is divided into three phes uh first check if the

deterministic pro reliably uh return valid proof if not then by the games constraints we don't have to extract a witness and we return uh about value if yes then the extractor assume that this Pro actually it's quite good in Computing accept impr proof and start quering it to uh random challenges uh sampl without replacement until it get other and accepting proof uh and once it gets n plus1 accepting proof then it just invoke the special sound extractor to compute the wids and note that this second stage here can take um exponential

time uh because because it could be the case that the exelor just try all the exponentially many challenges and maybe even fail to find the N plus one uh accepting transcript uh but we show the proof that even though it can take a long time uh this um second phase runs in time expected po uh why um the extracted F ofx should be a valid witness um first we show that if the first proof is accepted uh then the extractor fails in find other unaccepting uh proof with very small probability and this follow a

technique developed by hat to in 2021 uh and then we show that we can actually invoke the special sound extractor and uh this special sound extractor uh does not fail um with more than negligible probability here we have a more technical issue so um technically special soundness hold against strict polinomial time adversaries because the IRS assumption holds against uh strict polinomial time adversary but uh in the reduction uh we actually have an adversary that run in expected polinomial time because we have this second

phase and we find out that this is not actually a real issue because we also have this result in the form of Al LMA which states that any falsifiable assumption that holds against strict polinomial time adversary holds against expected polinomial time adversary as well and vice versa and this is like a simple Lama that follow from um the definitions of the construction involved and the mark of inequality and with that um we have showed that the kg um commitment scheme is extractable in the standard model under the IRS

assumption uh so if there's there is still no question uh then I will move on to the third part of the Tor which is uh where we present the coant size narc that we can get uh yeah there's no question okay um so we follow the framework of using um an information theoretic proof model and K commitment scheme and as a proof model we use uh P IOP so polinomial interactive Oracle proofs the

same used in dark for instance um which are defined in the following way so we have an indexer algorithm that compute some polinomial Oracle we can think of pols involved in this construction as uh trusted oracles that when quered on points always return an honest evaluations of the polinomial at the qual point so then we have IOP appr and verifier equiped with this index and oracles equiped with the public statement and also the pro as the weakness and an IOP round is uh composed by these two move so first the prover

send polinomial Oracle to the verifier and then the verifier replies with some challenges and those challenges are queried uh to um all the oracles uh that the pro the verifier have available so far so the uh F of I already sent and the Oracle in the uh indexer and we can assume that uh since oracles are trusted that the verifier will get correct evaluations of this uh quat point at the quat polinomial so we do that for manyu rounds and eventually uh the two party

sense their interaction and they have the complete transcript of the proof then the verifier just run a verification algorithm which will output zero or one um according to if it's if it's convinced that the pro uh knows the witness or not and we required this classic knowledge on this property modeled by the existence of an extractor which takes us input an accepting transcript and just output the witness um we can take uh an piop and compile them into asnar using the kdg computant scheme so the SRS generator

sample HG commitment key and then um commit to all the indexed polinomial and publish the SRS then prover and verifier uh they have to simulate uh some out the IOP interaction so um when the IOP Pro would have sent a polinomial instead those two parties engage in a three round protocol where the pro start committed to uh the polinomial that uh he would have sent and give the commitment to the verifier and then the verifier open this polinomial to a random evaluation

point or ask for an openings at the random evaluation point and check if this opening is correct now when the IOP verifier would have sent uh challenges to The Trusted Oracle uh here we don't have trusted Oracle so um the Prov has to send um evaluations and to prove that the evaluation has be done correctly it also sends uh kyg uh openings so this five rounds simulates uh the um one of the rounds of the IOP we do that for all the rounds of the IOP and in the end the argument verifiers

just check uh that all the kids openings have been accepted and then use the original IOP verification procedure uh to Output zero or one and we should uh prove uh as we did in the paper that with this construction is knowledge sound the proof scheme is uh similar to the one uh used in dark compiler so uh first since the kyg isable um after we have done this opening at an evaluation point we can extract the committed polinomial and use it to simulate an IOP adversary that

will play with an IOP verifier then we argue that uh the openings provided by the tuer are consistent uh with the uh the polinomial that we have extracted using the PG extractor and lastly we argue that uh when this is the the case we can um at the end obtain um a transcript a IOP transcript that we can fed into the IOP knowledge structor in order to compute the weakness so let's keep Let's uh see this proof more in details okay say that we start with this

uh malicious uh Pro for the argument we use it to define a anop pro and we let this IOP prover play with the IOP verifier so first the prover generate an SRS and in run the argument Pro when the argument Prov return a commitment uh the IOP prover uh ask for this random evaluation and get it uh the opening now at this point since K is aable we can invoke the extractor and extract the committed polom

fi and finally we use this fi uh to Output the polinomial Oracle for the IOP verifier at this point the verifier will reply with some challenges that we forgot we forward to the argument prover and the argument prover will get back uh is uh evaluations with corresponding kids AG proofs but the I Prov at this point can also compute evaluation by itself so it does so and then it checks if the evaluation computed by itself are compatible uh with the evaluation provided by the pro now please note that if all the

extractions suceeded and if all the evaluations are compatible then in the end we got that the IOP verifier will accept if and if the corresponding uh argument verifier on the same uh messages would have accepted and those two conditions the extractor succeed and the evaluation are compatible uh happens except with negligible probability uh this is a consequence of well this uh should fail only with negligible probability because PG is knowledge sound and this should fail only with NE ible probability because otherwise we

can use this malicious Pro to define a successful adversary against the evaluation binding uh this would be an expected polinomial time adversity but this is not the problem because we can rely on our new LMA and show that even if the adversary is expected polinomial time it should not succeed in Breaking evaluation binding so we have defined this um IOP Prov which makes the IOP verifier accept uh with almost the same probability as the I argument verifier accept which means that we are uh we can use the transcript we have obtained to

extract the valid witness and this witness will be a valid witness for X every time the argument verifier accept except with negligible probability okay so uh we are now at the conclusion of my talks I will just have another slide on this uh open questions so can we be satisfied by our construction uh the answer is yes and no yes because it's the first custom size Nars uh in the random Oracle model for this uh um for this Universal framework

for constraint system uh but um this Nar is not as good as construction deployed by Industries as plon and lunar for instance um and this is true because those construction apply a bunch of optimization techniques uh of the kids AG commitment scheme uh such as homomorphic properties the linearization tricks and some budget openings and also uh once we apply the Fiat Shamir security to our compiler uh we get something that is um not as efficient as the state of Art snar and not as tight not with as tight security

proof in term of concrete parameters so can we find a better solution to this uh this is what we have keep working on we have some upcoming results so uh hopefully you will see uh some questions to this answer soon some answer to this question soon but I would say an important uh open problem is to find uh a tight reduction from the standard IRS uh that holds against um strict polinomial time uh to uh expected polinomial time adversary of special soundness and evaluation binding because

uh the this uh should be uh used uh as to estimate concrete security parameter if one wants to rely on our U proof for the snarks okay so this is the end of my talks thanks for your attention hopefully I've not lost all of you uh those are the reference of the paper I mentioned and uh please feel free to check out power print uh and if you have any question I will uh happily take them now uh I had a question yes um so I was wondering so you said you had some

argument for why this new assumption is secure sort of briefly what to do yes so um let me share the slide again um when okay no sorry well I can answer without slides um when I mentioned that uh the K uh commitment scheme is not extractable in the standard model by the commitment only uh this was a result of

our previous paper in the same paper we have um a new and more realistic uh ideal model the um algebraic group model with oblivious sampling uh which is a group model that also guarantees security against these kind of attacks when adversary can perform oblivious sampling and the argument we have to believe in our new assumption is a security proof for the Assumption in this uh new and more realistic ideal model so that's this means that the security proof of kid G rely on ideal model as well uh we argue that no uh because it's um it's a very different

usage of Ideal models uh to prove them to use them to prove the security of the Assumption and then a standard reduction from the assump from the for the security proof uh under the assumption uh and on the other hand uh a security proof directly in the ideal model is uh like a less realistic security proof um just one other tiny question that um equivalence between like strict PPT and expected PPT yes or false viable assumptions was that something that was known or is that like I real it sounds relatively straightforward but was it

known ahead of your work it was uh to the best of our knowledge not known before because that's sound very nice um yeah but the problem is that we lose tightness so the LMA is just on the form of if any strict PPT assumption has uh negligible probability of winning some game then there exists a negligible function that will bound the probability of expected PPT to win uh the game and vice versa so the problem here is that we lose tightness okay thank you very much um I also have a couple of

questions so yes uh you already said unfortunately that uh you are working on whether batching linearizations and O optimization tricks uh are possible in in your new model uh do you have um I'm I'm not looking for uh precise numbers but uh um do you know how much the overhead would be not having these optimizations if it's something very significant it will be very significant yes like if you check uh uh I I I don't have the exact numbers now but like if you check Blan paper for instance uh you can really see that the the optimization

that they have there uh really relies on uh those tricks yeah uh yeah yeah I can see it for B so yeah but I don't have concrete numbers so what would be exactly the overhead because of course it will also depend on the concrete IOP that you will use of course uh so I'm not very knowledgeable about these new assumptions I and so yours which is adaptive I I see good that use uh actually implies I is weaker since the adversary has a choice of uh the set yes uh I was just wondering if uh you aware of any

papers who which already relies on this assumption uh no this is an assumption that uh we introduced oh no no no sorry uh not uh well sorry not only I uh a r s the H but also r s the H can you repeat your question maybe I not understood it so if any are you aware of any paper which relies on R sdh assumption no no it's a new assumption that we introduced uh you introduce a r sdh yes and R the standard rsdh was introduced by this paper from 2019 of Gonzalez and Raffles I have the reference in the last

slide and they already relied on this assumption so it's a shorter ping based argument under standard assumption thank you I have a look at [Music] it9 than uh I also had a question yes um so thank you um I was wondering do you think that it's possible to also pre proove uh weak simulation extra ability we haven't looked at that but uh it's on the pipeline of things that we should look at right yeah yeah it seems plausible

yes it seems Seems plausible okay thanks yeah uh I don't see any questions written on the chat uh and no one else uh is asking now so I would like to thank you again Roberto for joining us today and for giving this talk and we're really looking forwards your next iteration with all the optimizations uh for positive or negative results it would be very interesting uh so thanks a lot thanks a lot everyone for joining and have a good

day thanks bye thanks Roberto great