Zk Snarks A Gentle Introduction-Free Books

zk SNARKs A Gentle Introduction
26 Mar 2020 | 12 views | 0 downloads | 42 Pages | 850.04 KB

Share Pdf : Zk Snarks A Gentle Introduction

Download and Preview : Zk Snarks A Gentle Introduction


Report CopyRight/DMCA Form For : Zk Snarks A Gentle Introduction



Transcription

1 Introduction, The goal of this survey is to introduce zk SNARKs to provide a broad overview of these protocols starting. from explaining the motivations for proof systems in cryptography and giving some early context then. recalling the zk SNARK history from the first plausible construction through successive improvements to. today most efficient instantiations Finally the more technical part of this introduction will formally define. the notion of zk SNARK and the security requirements of these schemes and dive into the details of some. celebrated constructions,1 1 Proof Systems in Cryptography. A proof system in the cryptographical sense is an interactive protocol by which one party called the prover. wishes to convince another party called the verifier that a given statement is true In zero knowledge. proof we require further that the proof does not reveal anything more than the truth of the statement At a. first glimpse it sounds counter intuitive being able to prove something is correct without revealing any. extra detail Let s see that it is perfectly possible by a very simple day to day example. Example 1 1 Playing card Imagine that we pick a card A from a complete deck of playing cards and we. want to prove to an adversary that we have a red card in our hand We can prove that by revealing more. information than expressed in the statement just by showing our card A Alternatively we can choose to. prove nothing more than the colour of our card by revealing to the adversary all the black cards left. in the deck Our opponent should now be convinced we have a red card in our hands but it did not learn. anything else about the value of our card, Researches in zero knowledge proofs have been prompted by authentication systems where one party. wants to prove its identity to a second party via some secret information such as a password but doesn t. want to disclose anything about its secret password to the second party This is called a zero knowledge. proof of knowledge, A proof of knowledge is an interactive protocol in which the prover succeeds in convincing a verifier. that it knows something a password the steps of a computation etc associated with the statement For. example if the statement is I am Alice the prover should show knowledge of the secret password of. Alice if the statement is I computed the function f x and obtained y then the prover must convince its. verifier that it knows all the steps of this computation that lead to the result y. What it means for a machine to have knowledge is defined formally in terms of an extractor As the. program of the prover does not necessarily spit out the knowledge itself as is the case for zero knowledge. proofs we will invoke another machine called the knowledge extractor that by having access to the prover. can extract this witness the knowledge, The next step is the introduction of non interactive proof systems which reduce the number of rounds.
of interaction between the prover and the verifier to only one Some non interactive protocols consist in. only one message from the prover to verifier others need the verifier to generate some setting information. called CRS that can be made publicly available ahead of time and independently of the statement to be. proved later To enforce security and avoid cheating from the verifier this CRS is often generated by a third. trusted party,1 2 SNARKs, In the class of non interactive proofs a particularly interesting concept for proving integrity of results for. large computations is that of SNARK i e succinct non interactive argument of knowledge By this term we. denote a proof system which is, succinct the size of the proof is very small compared to the size of the statement or the witness i e the. size of the computation itself, non interactive it does not require rounds of interaction between the prover and the verifier. argument we consider it secure only for provers that have bounded computational resources which. means that provers with enough computational power can convince the verifier of a wrong statement. knowledge sound it is not possible for the prover to construct a proof without knowing a certain so called. witness for the statement formally for any prover able to produce a valid proof there is an extractor. capable of extracting a witness the knowledge for the statement. SNARK systems can be further equipped with a zero knowledge property that enables the proof to be. done without revealing anything about the intermediate steps the witness We will call these schemes. A zk SNARK protocol as any other non interactive proof system is described by three algorithms. that work as follows, Gen is the setup algorithm generating a necessary string crs used later in the proving process and. some verification key vrs sometimes assumed to be secret to the verifier only It is typically run by a. trusted party, Prove is the proving algorithm that takes as input the crs the statement u and a corresponding.
witness w and outputs the proof, Verify is the algorithm that takes as input the verification key vrs the statement u and the proof. and returns 1 accept the proof or 0 reject, The SNARK schemes can be used for delegating computation in the following way a server can run a. computation for a client and non interactively prove the accuracy of the result The client can verify the. result s correctness in nearly linear time in the size of the input instead of running the entire computation. Organisation Section 2 is rather informal and it gives some high level intuition and the historical evolution. of zero knowledge proofs and arguments, Then in Section 3 SNARKs are formally defined and the security requirements for these schemes are. stated Then the focus lies on presenting the most outstanding constructions in the recent years PCP based. schemes in Section 4 QAP based schemes in Section 5 and LIP based SNARKs in Section 6 This part. contains many simplifications and examples to help the reader understand step by step the frameworks. of diverse SNARK constructions,2 Proofs and Arguments. Proof systems introduced by GMR89 are fundamental building blocks in cryptography Extensively studied. aspects of proof systems are the expressivity of provable statements and their efficiency. Complexity Classes In order to better understand the role of proofs and their classification we will briefly. and informally introduce some basic complexity notions The complexity classes will be defined by the. type of computational problem the model of computation and the resource that are being bounded and. the bounds The resource and bounds are usually stated together such as polynomial time logarithmic. space constant depth etc We will introduce the main two fundamental complexity classes P and NP. They are used to classify decision problems, P versus NP On the one hand the class P is the class of languages L such that there exists an algorithm.
that takes as input a bit string x and that can decide in polynomial time in the size of x whether x L. We generally consider this class as the class of easy to decide languages and call them polynomial time. algorithms efficient algorithms, On the other hand the class NP is the class of languages L such that there exists an algorithm that. takes as input two bit strings x and w and that can decide in polynomial time in the size of x whether w. is a valid proof or witness that x L We suppose that for any statement x L there exists such a witness. w while otherwise x L no such witness exists A formal definition is stated as follows. Definition 2 1 The Class NP A language L is in the class NP if there exists a polynomial time algorithm. RL such that,L x w w poly x RL x w 1, By restricting the definition of NP to witness strings of length zero we capture the same problems as. those in P While the class P is clearly included in NP finding whether NP is included in P is one of the. most important open problems in computer science, It basically asks whether being able to efficiently check a proof of a statement is equivalent to being. able to check if a statement is true or false efficiently Even if we don t have any clear evidence for that. most researchers strongly believe that P 6 NP, In cryptography considerable atention is given to the NP hard complexity class NP hard is the defining. property of a class of problems that are informally at least as hard as the hardest problems in NP. We will often talk about NP complete decision problems the ones belonging to both the NP and the. NP hard complexity classes, Example Satisfiability Problems SAT As an example for a problem in NP let us consider the problem of.
boolean formula satisfiability SAT For that we define a boolean formula using an inductive definition. any variable x1 x2 x3 is a boolean formula, if f is a boolean formula then f is a boolean formula negation. if f and g are boolean formulas then f g and f g are boolean formulas conjunction and. disjunction or,The string x1 x2 x2 would be a boolean formula. A boolean formula is satisfiable if there is a way to assign truth values to the variables so that the formula. evaluates to true The satisfiability problem SAT is the set of all satisfiable boolean formulas SAT f 1. if f is a satisfiable boolean formula and 0 otherwise. The example above x1 x2 x2 is not satisfiable and thus does not lie in SAT The witness for a. given formula is its satisfying assignment and verifying that a variable assignment is satisfying is a task that. can be solved in polynomial time, The attractive property of this seemingly simple problem is that it does not only lie in NP it is also. NP complete It means that it is one of the hardest problems in NP but more importantly and that is the. definition of NP complete an input to any problem in NP can be transformed to an equivalent input for. SAT in the following sense, For any N P problem L there is a so called reduction function f which is computable in polynomial. time such that,L x SAT f x, Such a reduction function can be seen as a compiler It takes source code written in some programming.
language and transforms it into an equivalent program in another programming language which typically is. a machine language which has the same semantic behaviour Since SAT is NP complete such a reduction. exists for any possible problem in NP, Computational problems inside NP can be reduced to each other and moreover there are NP complete. problems that are basically only reformulations of all other problems in NP. 2 1 Interactive Zero Knowledge Proofs, By Definition 2 1 the class NP contains all languages for which an unbounded prover can compute. deterministic proofs where a proof is viewed as a string of length polynomial in the statement x. An interactive proof relaxes these requirements in two directions first the prover and the verifier are. allowed to use random coins second the output of a proof verification should only match the actual truth. of the statement with some reasonable enough probability and obviously there is interaction between. First Interactive Proofs In two independent seminal papers that won a G del prize Babai Bab85. and Goldwasser Micali and Rackoff GMR85 introduced the notion of interactive proofs also known as. Arthur Merlin proofs, Both works studied complexity classes where a computationally unbounded prover must convince a. polynomially bounded receiver of the truth of a statement using rounds of interactions The main difference. between the notions studied in these papers is regarding the random coins of the verifier in the work of. Babai the verifier was required to reveal to the prover all coins that he used during the computation Such. interactive proofs are referred to as public coin interactive proofs as opposed to private coin interactive. proofs in which the verifier might keep its internal state hidden. The complexity classes corresponding to public coin interactive proofs were denoted AM f n by. Babai where AM stands for Arthur Merlin n is the input length and f n is the allowed number of rounds. of interaction The complexity classes corresponding to private coin interactive proofs were denoted. IP f n by Goldwasser Micali and Rackoff, Zero Knowledge As pointed out by Goldwasser Micali and Rackoff in their seminal paper GMR85 an. essential question about interactive proofs in cryptography is whether the prover reveals more information. or knowledge to the verifier than the fact that x L Indeed in cryptography we often want to hide. information A proof that does not reveal any information to the verifier besides the membership of the. statement to the language is called a zero knowledge proof A way to formally define this property is to. consider a simulator that is able to behave exactly as the prover in the protocol and to produce a fake. proof without knowing the witness This should be done in a way that a verifier will not be able to tell if it. interacts with the real prover or with this simulator Intuitively we can then argue that a honestly generated. proof looks indistinguishable from a simulated value produced independently of the witness meaning that. the proof reveals as much information about the witness as this value so basically zero knowledge This. concept might seem very counter intuitive and impossible to achieve However in GMW86 Goldreich. Micali and Wigderson constructed zero knowledge proofs for any language in NP under a very weak. assumption namely the existence of one way functions. Succinct Arguments Related to efficiency and to optimization of communication complexity it has. been shown that statistically sound proof systems are unlikely to allow for significant improvements in. communication BHZ87 GH98 GVW02 Wee05 When considering proof systems for NP this means that. unless some complexity theoretic collapses occur in a statistically sound proof system any prover has to. communicate roughly as much information as the size of the NP witness The search for ways to beat. this bound motivated the study of computationally sound proof systems also called argument systems. BCC88 where soundness is required to hold only against computationally bounded provers. Assuming the existence of collision resistant hash functions Kilian Kil92 showed a four message. interactive argument for NP In this protocol membership of an instance x in an NP language with NP. machine M can be proven with communication and verifier s running time bounded by p M x log t. where is a security parameter t is the NP verification time of machine M for the instance x and p is an. universal polynomial, Such argument systems where the communication complexity and sometimes the work of the verifier.
sublinear in or even independent of the witness size are called succinct. Zero Knowledge Proofs and Arguments A zero knowledge proof or its relaxed version argument is a. protocol between a prover P and a verifier V for proving that a statement x is in a language L Informally. such a protocol has to satisfy three properties, Completeness An honest verifier always accepts a proof made by an honest prover for a valid word and. using a valid witness, Soundness No unbounded PPT adversary can make an honest verifier accept a proof of a word x L. either statistically for zero knowledge proofs computationally for zero knowledge arguments. Zero knowledge It is possible to simulate in polynomial time the interaction between a potentially. malicious verifier and an honest prover for any word x L without knowing a witness w. Honest Verifier Zero Knowledge Honest verifier zero knowledge arguments or proofs are similar to the. ones defined above except that we assume that the verifier is not malicious The zero knowledge property. applies only to verifiers that behave honestly and follow the protocol This relaxation enables to construct. even more efficient schemes,2 2 Interactive Arguments of Knowledge. The proofs and arguments we discussed in the previous section are tools used for membership statements. i e proving membership of an instance x in a language L Restricting our attention to NP languages such. statements can be phrased as existential statements of the form w RL x w 1 Proofs of knowledge. strengthen the security guarantee given by classical zero knowledge proofs While a zero knowledge proof. suffices to convince the verifier of the existence of a witness w for the statement a proof of knowledge. additionally shows that the prover knows such a witness. Several remarks are in order here First we have to define what it means for a prover to know such. a witness Intuitively to make sure a prover has used the witness it should be possible to extract this. knowledge from that prover Informally this is done as follows we say that an efficient algorithm A knows. a value w if we can build a simulator Sim that for any such A that produces an accepting transcript Sim. can extract the witness w from its interaction with A. Second an important property of proofs of knowledge is that they can make sense even for statements. that are trivial from an existential point of view i e for trivial languages for which a membership witness. always exists but can be hard to compute We illustrate this with a classical example. Example 2 2 Discrete Logarithm Language Let LDLog G g denote for a cyclic group G with a gener. ator g the following language,LDLog G g h G x Z g x h. As g is a generator of G this is a trivial language all elements of G belong to LDLog h G x Z. such that g x h and this exponent x is not unique However computing such an integer x can be. computationally infeasible because of the discrete logarithm assumption see Assumption 2 3 Therefore. while asking a prover to show the existence of the discrete logarithm of some word h is meaningless. convincing a verifier that a prover knows the discrete logarithm of h in base g gives him a piece of non. trivial information, Assumption 2 3 Discrete Logarithm Assumption Given a cyclic group G of order n N with a generator.
g the discrete logarithm assumption over G states informally that it is computationally infeasible given a. random group element h G to find an integer x Zn such that h g x. Hardness of Discrete Logarithm Generic algorithms to solve discrete logarithm which are independent. of the particular structure of the underlying group G have a running time proportional to n In spite of. more than four decades of intense cryptanalytic effort there exist certain groups in which we still do not. know any algorithm with better efficiency than the generic algorithms. Sigma Protocols In this part we will describe a specific class of zero knowledge proof systems to which. very efficient zero knowledge protocols from the literature belong protocols CDS94. Definition 2 4 Sigma Protocol A protocol for a language L is a public coin honest verifier zero. knowledge proof of knowledge with a particular three move structure. Commit Phase P sends to V some commitment values to some randomness. Challenge Phase V sends to P a uniformly random challenge e. Response Phase P sends to V an answer f w r e where f is some public function and w is the witness. Example The Schnorr Protocol In Example 2 2 we were mentioning the possibility to prove knowledge. of the discrete logarithm of some group element h in some base g where g is the generator of some group. G We now elaborate on this example by describing a protocol for proving knowledge of a discrete. logarithm The protocol is given in Figure 1 It was first described in Sch90 and it is commonly used as an. authentication protocol given a public value h the prover authenticates himself by proving his knowledge. of the secret value x associated to this public value i e x is such that g x h for a fixed generator g. Prover Verifier,ex r g he a,Figure 1 Schnorr Protocol for DLog Language. Rewinding The standard solution to prove the security of protocols is to use a technique called. rewinding The simulator will run the code of the prover feeding it with the verifier inputs it requires and. then rewind it to some previous state so as to feed it with different inputs By doing so the simulator will. be able to get several outputs of the prover with respect to different verifier inputs starting from some. common state of the prover Intuitively this allows the simulator to cancel out some randomness that had. been introduced by the prover to mask its witness, Security Analysis Sketch We show that the protocol given in figure Figure 1 is perfectly complete. knowledge extractable and honest verifier zero knowledge. Perfect completeness It follows immediately by inspection if ex r mod p then g g ex r. g x e g r he a, Honest verifier zero knowledge Let Sim be a simulator which is given the common input G g h and. the code of the verifier Sim selects a uniformly random tape for the verifier algorithm and runs it. with this random tape on a random input message a G Once the Verifier outputs a challenge. e Sim restarts the protocol feeding Verifier algorithm with the same random tape and setting the. input message a to g r h e for a uniformly random r Note that a is distributed exactly as in an honest. execution of the protocol After the verifier outputs the challenge e the verifier is assumed honest so. it uses only the coins of his random tape Hence this challenge is the same than the one extracted by. Sim in the previous run of the verifier Sim answers with r Observe that the equation g he a. is satisfied for the chosen values of and a and that the answer is distributed exactly as in an honest. run hence the honest verifier zero knowledge property. Knowledge extraction Consider a prover that runs in time T and produces an accepting answer with. non negligible probability and let Sim0 be a simulator which is given the code of the prover as input. Once the prover outputs the first flow a Sim0 writes a random e Zp on its message input tape. and gets an answer Then Sim0 rewinds the prover to step 2 of the protocol feeding it with a new. random e0 and receiving a corresponding new answer 0 Observe that if both 0 are accepting. answers it holds that g he a g he a which gives g he e g x e e In this case. Sim can obtain x by computing 0 e e0 1 mod p as we have e 6 e0 with overwhelming. probability We argue the simulator Sim0 for a prover that runs in time T and has success probability. runs in O T the simulator repeats the rewinding procedure at most 1 times. 2 3 Non Interactive Proofs and Arguments, As we have seen previously interactive proofs can be understood as a relaxation of the standard non. interactive proofs captured by the class NP where we allow interaction as well as random coins between. the verifier and the prover In this section we will focus on protocols that do not require more communica. tion than a sole message from prover to verifier In a non interactive proof or argument the prover just. sends one message called the proof to the verifier and the latter can check it in order to accept it or not. This proof is similar to a witness of an NP language except that sending a witness often gives too much. knowledge to the verifier, Non Interactive Zero Knowledge Zero knowledge proofs are randomized interactive proof systems.
satisfying a specific zero knowledge property All the results mentioned previously relied on interactive. protocols with strong security guarantees without making any trust assumption whatsoever This is known. as the standard model and it provides the highest real world security guarantees in an adversarial context. In this model of computation the adversary is only limited by the amount of time and computational. power available, However the absence of any form of trust strongly narrows the range of feasibility results several. desirable properties either related to the security or to the efficiency of interactive proof systems are. proved impossible to achievable in the standard model Consider the important question of building zero. knowledge proofs with a small number of rounds of interaction We know that there is no hope of building. a zero knowledge proof system in the standard model with a single round of interaction for non trivial. languages GO94 and strong limitations are also known for two rounds of interaction GO94 BLV03. A natural theoretical question is to ask whether there are zero knowledge randomized proofs that are. completely non interactive no round of interaction is needed Such systems are called non interactive. zero knowledge proof systems NIZK This question is also very interesting from a practical point of view in. the real world interactivity means exchanging information over some network which raises some latency. issues Other motivations for NIZK proofs are their applications to numerous cryptographic primitives. Common Reference String In light of the strong limitations discussed above an interesting research. direction is to find the minimal trust assumptions one could make that lead to a model in which practically. efficient NIZK proof systems can be built Some impossibility results and studies of lower bounds were. shown for various models we refer to Wee07 for more details. The common reference string CRS model introduced by Damg rd Dam00 captures the assumption. that a trusted setup in which all involved parties get access to the same string crs taken from some distri. bution D exists Schemes proven secure in the CRS model are secure given that the setup was performed. correctly The common reference string model is a generalization of the common random string model in. which D is the uniform distribution of bit strings The common reference string model has proven very. convenient to use for constructing a large variety of efficient primitives with strong security requirements. In this model the prover and the verifier both have access to a common bit string chosen by some trusted. party In practice such a bit string can be generated by a multi party computation between users who are. believed not to collude, First NIZK Schemes Blum et al first study the non interactive zero knowledge proof system and present. the common reference string model that is generally applied at present BFM88 DMP90 This first. construction of BFM88 is a bounded NIZK proof system meaning that for different statements in NP. language the proof system has to use different CRSs and the length of the statement is controlled by the. length of CRS Later Blum et al DMP90 presented a more general multi theorem NIZK proof system for. 3SAT by improving the previous one which allows to prove many statements with the same CRS. Both BFM88 and DMP90 based their NIZK systems on certain number theoretic assumptions. specifically the hardness of deciding quadratic residues modulo a composite number Feige Lapidot. and Shamir FLS90 showed later how to construct computational NIZK proofs based on any trapdoor. permutation, Much research has been devoted to the construction of efficient NIZK proofs Dam93 KP98 BDP00. but back then the only known method to do so has been the hidden random bits model This hidden. random bits model assumes the prover has a string of random bits which are secret to the verifier By. revealing a subset of these bits and keeping the rest secret the prover can convince the verifier of the truth. of the statement in question Improvements in the efficiency of NIZK proofs have come in the form of. various ways to set up a hidden random bits model and how to use it optimally. Groth Sahai Proofs For a long time two main types of NIZK proof systems were available efficient but. heuristically secure proof systems in the random oracle model and inefficient proof systems in the hidden. random bits model FLS90 Dam93 KP98 BDP00 which can be instantiated in the standard model under. well studied assumptions This changed with the arrival of pairing based cryptography from which a. fruitful line of work starting with the work of Groth Ostrovsky and Sahai GOS06b GOS06a introduced. increasingly more efficient NIZK proof systems in the standard model. The Groth Ostrovsky Sahai proof system was the first perfect NIZK argument system for any NP lan. guage and the first universal composable secure NIZK argument for any NP language This resolved a. central open problem concerning NIZK protocols The mechanism was dramatically different from the. previous works such as Blum Feldman Micali proof system BFM88 and Blum Santis Micali Persiano. proof system DMP90, This line of work culminated with the framework of Groth Sahai proofs GS08 which identified a. restricted yet very powerful class of languages for which efficient pairing based NIZK could be designed. with security based on essentially any standard assumption on pairing friendly groups This framework. greatly improved the efficiency and practicability of NIZK and created a new line of research on the. applications of NIZK, Nevertheless these schemes pose a limitation on the length of the proof statement in order to achieve.
adaptive soundness against dishonest provers who may choose the target statement depending on the CRS. Since the common reference string is public it would be more natural to define soundness adaptively. The first adaptively sound statistical NIZK argument for NP that does not pose any restriction on the. statements to be proven requires non falsifiable assumptions see AF07 Abe and Fehr AF07 have. demonstrated also an impossibility result no adaptively sound statistical zero knowledge NIZK argument. for an NP complete language can have a direct black box security reduction to a standard cryptographic. assumption unless NP P poly,2 3 1 Fiat Shamir Heuristic. The Fiat Shamir heuristic FS87 is a heuristic method to convert protocols see Section 2 2 into non. interactive zero knowledge proofs It proceeds as follows to prove the membership of an instance x to a. language L the prover first computes the first flow the commitments of a protocol for this statement. Let a denote this first flow Then the prover sets e RO x a where RO is some hash function modeled. by a random oracle and computes the last flow step 3 of the protocol using e as the challenge While. this approach leads to very efficient NIZKs it cannot be proven to work under any standard assumption. related to hash functions Instead the above methodology can be proven to work only in the random oracle. Random Oracle As already mentioned security proofs are notoriously difficult to achieve in the standard. model so in many proofs cryptographic primitives are replaced by idealized versions. The random oracle model ROM BR93 CGH98 is an idealised cryptographic model and it assumes. the existence of a truly random function to which all parties involved in a protocol have access Since. in reality no such ideal function exists random oracles are instantiated with hash functions and one. heuristically assumes that a hash function behaves well enough to be a replacement for random oracles. Random oracles allow proving protocols are secure while they are still practically efficient On the negative. side this model has its disadvantages as it is seen more as heuristically secure since no truly random hash. functions can be used in practice Some failures of the random oracle methodology when implemented. in practice are shown in CGH98 They show that there exist signature and encryption schemes that are. secure in the ROM but for which any implementation of the random oracle results in insecure schemes. Fiat Shamir Compatible Hash Functions Still an open question is whether there exist concrete hash. families that are Fiat Shamir compatible i e that can guarantee soundness and potentially also zero. knowledge for the transformed protocol Initial results in this direction were negative Indeed Goldwasser. and Kalai GK03 following Barak Bar01 demonstrated a three round public coin argument scheme for. which applying the Fiat Shamir transform with any hash family never yields a sound protocol Furthermore. Bitansky et al BDG 13 show that even when starting with a three round proof soundness of the Fiat. Shamir transform with a concrete hash family cannot be proved via black box reduction to standard game. based assumptions In contrast a recent line of work KRR17 CCRR18 HL18 circumvents the BDG 13. impossibility result by using stronger than standard hardness assumptions to construct FS compatible hash. families Kalai et al KRR17 gave the first construction of a hash family that is FS compatible for arbitrary. constant round public coin interactive proofs albeit from complex obfuscation assumptions Canetti et. al CCRR18 then provide alternative families without obfuscation but using complex KDM security. assumptions on secret key encryption schemes It is important to remark that the assumptions made by. KRR17 CCRR18 are non falsifiable and highly complex in the following sense both involve an adversary. that is in part computationally unbounded, In two recent companion articles Canetti et al CCH 18 CLW18 construct explicit hash functions. that are FS compatible for a rich class of protocols and they prove their security under assumptions that. are qualitatively weaker than what was previously known Using these hash families new results can be. obtained for delegation of computation and zero knowledge. 2 3 2 SNARG Succinct Non Interactive Arguments, Starting from Kilian s protocol Micali Mic94 used the Fiat Shamir heuristic to construct a one message. succinct argument for NP whose soundness is set in the random oracle model New more efficient systems. followed in the CRS model they are called succinct non interactive arguments SNARGs GW11 The area. of SNARGs became quite popular in the last years with the proposal of several constructions in the CRS. model some of which gained significant improvements in efficiency Gro10 Lip12 BCCT12 GGPR13. PHGR13 BCG 13a DFGK14 Gro16, Non Falsifiable Assumptions Noteworthy is that all SNARG constructions are based on non falsifiable. assumptions Nao03b a class of assumptions that is likely to be inherent in proving the security of. SNARGs without random oracles as stated by Gentry and Wichs in their work GW11 They show that no. construction of SNARGs can be proven secure via a black box reduction from any falsifiable assumption. unless that assumption is already false, Most standard cryptographic assumptions are falsifiable e g hardness of factoring DLog RSA CDH.
etc in the sense of the formal notion of cryptographic falsifiability introduced by Naor Nao03a Roughly. speaking a computational hardness assumption is said to be falsifiable if it can be formulated in terms of. a challenge an interactive protocol between an adversary and a challenger verifier where an efficient. adversary can convince the verifier to accept if and only if the assumption is false meaning that if the. assumption were false then it would be possible to prove it. Intuitively assumptions that are not falsifiable are more laborious to reason about and therefore we. have significantly less confidence in them, The knowledge assumptions are the most common non falsifiable assumptions that we use in cryp. tography They are considered non standard assumptions Knowledge assumptions capture our belief. that certain computational tasks can be achieved efficiently only by essentially going through specific. intermediate stages and thereby obtaining along the way some specific intermediate values. A number of different knowledge assumptions exist in the literature most of which are specific number. theoretic assumptions Abstracting from such specific assumptions one can formulate general notions of. extractability for one way functions and other basic primitives see CD09. Knowledge Soundness SNARGs have also been strengthened to become SNARKs succinct non interactive. arguments of knowledge BCCT12 BCC 14 SNARKs are SNARGs where computational soundness is. replaced by knowledge soundness Intuitively speaking this property says that every prover producing a. convincing proof must know a witness On the one hand knowledge soundness turns out to be useful in. many applications such as delegation of computation where the untrusted worker contributes its own. input to the computation or recursive proof composition Val08 BCCT13. On the other hand the formalization of knowledge soundness in non interactive protocols is a delicate. point since rewinding techniques mentioned in Section 2 2 do not apply anymore Typically the concept. that the prover must know a witness is expressed by assuming that such knowledge can be efficiently. extracted from the prover by means of a so called knowledge extractor In SNARKs extractors are inherently. non black box and the definition of knowledge soundness requires that for every adversarial prover A. generating an accepting proof there must be an extractor EA that given non black box access to A e g. by getting the same input including the random coins and the code of A outputs a valid witness. SNARKs Framework The framework for constructing SNARKs starts with finding a good characterization. of the complexity class NP and take advantage of its specific properties for applying some compression. techniques on top, Indeed by choosing a suitable NP complete problem representation see Section 2 we are able to. construct generic SNARK schemes for NP complete languages. For example many SNARKs have as a departure point the circuit satisfiability Circ SAT problem. Circ SAT problem is the NP complete decision problem of determining whether a given circuit has an. assignment of its inputs that makes the output true A very important line of works focuses on building. SNARKs for circuit satisfiability GGPR13 PHGR13 Lip13 DFGK14 Gro16 GMNO18 and have as a central. starting point the framework based on quadratic span programs introduced by Gennaro et al in GGPR13. This framework will be discussed in details in see Section 5. Another very useful characterisation of the NP complete class are the Probabilistically Checkable Proofs. PCP Using this characterisation we can give a framework for constructing SNARKs that was exploited. by many works in the field Mic94 CL08 GLR11 BCCT12 DFH12 BSBHR18. Other possible clasifications for SNARK frameworks can come from the building blocks used in the. construction, PCP Merkle Trees e g CS Proofs Mic94 see Section 4 3. Linear PCPs e g Zaatar SBV 12 BCI 13 BCG 13b see Section 6. IOPs PCIPs e g STARK BSBHR18 Aurora BSCR 18,MPC Based e g ZKBoo GMO16 Ligero AHIV17. Discrete log Based e g BCC 16 Bulletproofs BBB 18 Hyrax PPY19. For this gentle introduction we will give an informal overview of some preliminary constructions and. then in Section 5 we will focus on the SNARKs constructions for circuits. GOS06b GS07 GS08,GMW86 Sch90 DFGK14 Gro16,BISW17 BISW18.
IP ZK ARG KNL NIZK SNARK Post Q,KW18 BBC 18,BFM88 DMP90. GGPR13 PHGR13 BCC 14, Figure 2 Proof systems Some of the results mentioned in this chapter Interactive schemes starting. with proofs IP zero knowledge proofs and arguments ZK ARG arguments of knowledge KNL then. non interactive zero knowledge NIZK SNARKs and post quantum schemes. Post Quantum Proof Systems Almost all the proof systems mentioned so far1 are based on discrete log. type assumptions that do not hold against quantum polynomial time adversaries Sho99 hence the. advent of general purpose quantum computers would render insecure the constructions based on these. assumptions Efforts were made to design such systems based on quantum resilient assumptions. Some more desirable assumptions that withstand quantum attacks are the lattice problems Ajt96. MR04 Nevertheless few non interactive proof systems are built based on these Some recent works. that we can mention are the NIZK constructions for specific languages like KW18 LLNW18 BBC 18. and the two designated verifier SNARG constructions BISW17 BISW18 designed by Boneh et al using. encryption schemes instantiated with lattices The first lattice based designated verifier zk SNARK was. proposed by GMNO18 and uses weaker assumptions than the work of Boneh et al and additionally. achieves zero knowledge and knowledge soundness, Recent Efficient SNARKs In the past few years SNARKs got a lot of attention and many efficient new. constructions and implementations have emerged To mention just a few of them in the preprocessing. setting as state of the art we have Marlin CHM 19 a verifier efficient universal proving system based. on algebraic holographic proving systems AHP Sonic MBKM19 for applications that use batched. verifications Libra XZZ 19 or Plonk GWC19, Some other constructions of SNARKs do not rely on trusted setup Spartan Set19 Halo BGH19 and. Hyrax PPY19 However the cost of transparent SNARKs can generally be seen in the proof sizes and. verification time, Other works relying on Random Oracle Model plausibly post quantum secure that are equally worth.
1 We note that the original protocol of Micali Mic94 is a zk SNARK which can be instantiated with a post quantum assumption. since it requires only a collision resistant hash function however even in the best optimized version recently proposed in BSBHR18. the protocol does not seem to scale well for even moderately complex computations. being mentioned Aurora BSCR 18 based on Interactive Oracle Proofs IOPs a notion of multi round. PCPs achieves efficient proofs for Rank 1 Constraint Satisfaction R1CS or the scalable and transparent. STARK BSBHR18 and Fractal COS19,3 SNARKs Definitions. The Universal Relation and NP Relations A difficulty that arises when studying the efficiency of proofs. for arbitrary NP statements is the problem of representation Proof systems are typically designed for. abstract NP complete languages such as circuit satisfiability or algebraic constraint satisfaction problems. while in practice many of the problem statements we are interested in proving are easier and more. efficient to express via algorithms written in a high level programming language Modern compilers can. efficiently transform these algorithms into a program to be executed on a random access machine RAM. CR72 AV77 Therefore we choose to define SNARK protocols that efficiently support NP statements. expressed as the correct execution of a RAM program. We recall the notion of universal relation from BG08 here adapted to the case of non deterministic. computations, Definition 3 1 The universal relation is the set RU of instance witness pairs u w M x t w where. u w t and M is a random access machine such that M x w accepts after running at most t steps The. universal language LU is the language corresponding to RU. For any constant c N Rc denotes the subset of RU of pairs u w M x t w such that t x c. Rc is a generalized NP relation that is decidable in some fixed time polynomial in the size of the instance. Universal Arguments vs Weaker Notions A SNARK for the relation R RU is called a universal argu. ment An universal SNARK typically supports any circuit up to a given size bound In the definition of RU. we can replace the RAM machine M by a Turing machine or by an universal circuit depending on the. wished applications, A weaker notion that we will also consider is a SNARK for the relation R Rc for a constant c A SNARK. can also be defined for a specific efficiently decidable binary relation R or for a Boolean or arithmetic. 3 1 Universal SNARKs, We choose here to introduce the very general definition of universal SNARKs as stated in BCC 14 only. parametrized by a time bound T An universal SNARK is a proving system in which a single trusted setup. could be used across all applications and that parameters could be stored in a general purpose library. Definition 3 2 SNARK for NP A SNARK is defined by three algorithms. Gen 1 T vrs crs on input a security parameter N and a time bound T N this algorithm. outputs a common reference string crs and a verification state vrs. Prove crs u w given a prover reference string crs a statement u and a witness w s t u w R. and t T this algorithm produces a proof, Ver vrs u b on input a verification state vrs an instance u and a proof the verifier algorithm.
outputs b 0 reject or b 1 accept, satisfying completeness succinctness knowledge soundness as described below. Completeness For every time bound T N any relation R with t T and any PPT adversary A. A Pr COMPL A true negl,where COMPL A is the game depicted in Figure 3. COMPL A KS A EA ZK Sim A,crs vrs Gen 1 T crs vrs Gen 1 T crs vrs Gen 1 T. u w A crs u w AkEA crs z crs td Simcrs 1 T,Prove crs u w return R u w 0 b 0 1. return R u w 1 Ver vrs u 1,if b 1 Prove crs u w,Ver vrs u 0.
if b 0 Simproof crs td u,return b b0, Figure 3 Games for completeness knowledge soundness and zero knowledge. Succinctness There exists a fixed polynomial p independent of R such that for every large enough. security parameter N every time bound T N and every instance y M x t such that. t T we have,p log T for a fully succinct SNARG,Gen runs in time. p T for a pre processing SNARG,p M x t log T for fully succinct SNARG. Prove runs in time,p M x T for pre processing SNARG. Ver runs in time p M x log T,a honestly generated proof has size p log T.
Knowledge Soundness For every PPT adversarial prover A there exists a PPT extractor EA such. that for every large enough N every benign auxiliary input z 0 1 poly and every time. bound T N for the relation R such that t T it holds. A EA Pr KS A EA true negl,where KS A EA is defined in Figure 3. We call a zk SNARK a SNARK for which the zero knowledge property holds. Statistical Zero knowledge There exists a stateful interactive polynomial size simulator Sim. Simcrs Simproof such that for every large enough security parameter N auxiliary input z. 0 1 poly time bound T N and relation R and for all stateful interactive distinguishers A. Sim A Pr ZK Sim A true negl,where ZK Sim A is defined in Figure 3. Adaptive Soundness A SNARG is called adaptive if the prover can choose the statement u to be proved. after seeing the reference string crs and the argument remains sound. SNARG vs SNARK If we replace the Knowledge Soundness with the following weaker property adaptive. soundness we obtain what we call a SNARG a succinct non interactive argument. Adaptive Soundness For every PPT adversarial prover A there is a negligible function such. that for every time bound T N,crs vrs Gen 1 T,Ver vrs u 1. u 6 LR u A crs, The adaptive soundness is a weaker security notion than the adaptive knowledge soundness. Publicly verifiable vs Designated Verifier In the same line of past works DFGK14 ABLZ17 Fuc18 we. will assume for simplicity that crs can be extracted from the verification key vrs. If security adaptive KS holds against adversaries that also have access to the verification state vrs then. the SNARK is called publicly verifiable otherwise it is designated verifier. 4 SNARKs Construction from PCP, In this section we provide some high level intuition for some notable SNARK construction in the literature.
introduced by the work The hunting of the SNARK BCC 14. This methodology to construct SNARKs is based on PCP characterization of NP and it is first achieved. in the random oracle model ROM which gave only heuristical security The idea is to apply the random. oracle based Fiat Shamir transform to Kilian s succinct PCP based proof system Kil92 achieving loga. rithmic proof size and verification time, Later the construction is improved by removing the use of the random oracles and replacing them with. extractable collision resistant hash functions ECRH. We first informally introduce Probabilistically Checkable Proofs PCP a characterisation of the NP. 4 1 Probabilistically Checkable Proofs, The original version of the PCP Theorem ALM 98 states that proofs for any NP language can be encoded. in such a way that their validity can be verified by only reading a constant number of bits and with an error. probability that is upper bounded by a constant The class PCP is a generalization of the proof verifying. system used to define NP with the following changes. Probabilistic Verifier The verifier is probabilistic instead of deterministic Hence the verifier can have. different outputs for the same inputs x, Random Access to the Proof The verifier has random access to the proof string This means each bit in. the proof string can be independently queried by the verifier via a special address tape If the verifier. desires say the i th bit in the proof of the string it writes i in base 2 on the address tape and then. receives the bit i, Constant Number of Queries We are interested in probabilistic verification procedures that access only. a few locations in the proof ALM 98 and yet are able to make a meaningful probabilistic verdict. regarding the validity of the alleged proof Specifically the verification procedure should accept any. valid proof with probability 1 but rejects with probability at least 1 2 any alleged proof for a false. Adaptiveness Verifiers can be adaptive or non adaptive A non adaptive verifier selects its queries based. only on its inputs and random tape whereas an adaptive verifier can in addition rely upon bits it. has already queried in to select its next queries, The fact that one can meaningfully evaluate the correctness of proofs by examining few locations in.
them is indeed surprizing and somewhat counter intuitive Needless to say such proofs must be written in. a somewhat non standard format because standard proofs cannot be verified without reading them in full. since a flaw may be due to a single improper inference In contrast proofs for a PCP system tend to be.


Related Books

Institute for Market-Oriented Management

Institute for Market Oriented Management

is Assistant Professor of Marketing at the University of Mannheim. Prof. Dr. Wayne D. Hoyer is Professor of Business Administration and Marketing at the McCombs School of Business, The University of Texas at Austin. Institute for Market-Oriented Management Homburg, Ch. / Wieseke, J. / Hoyer, W. D. Social Identity and the Service Profit Chain

Performance analysis for DFIG Feeding a Stand-alone ...

Performance analysis for DFIG Feeding a Stand alone

The control system is based ... The Doubly fed induction machine ... Performance analysis for DFIG Feeding a Stand-alone Unbalanced Load for a doubly fed ...

For Peer Review - UJI

For Peer Review UJI

For Peer Review 2 technology, there has recently been a urry of activity to design appropriate interfaces for assistive robotic devices so human robot interaction can be made more efcient.

Performance Analysis of DFIG Based Standalone 2.2 kW ...

Performance Analysis of DFIG Based Standalone 2 2 kW

system is based on a Doubly Fed Induction ... Performance Analysis of DFIG Based Standalone 2.2 kW Laboratory ... speed double fed induction machine for wind ...

207-nm UV Light - A Promising Tool for Safe Low-Cost ...

207 nm UV Light A Promising Tool for Safe Low Cost

207-nm UV Light - A Promising Tool for Safe Low-Cost Reduction of Surgical Site Infections. I: In VitroStudies Manuela Buonanno1, Gerhard Randers-Pehrson1, Alan W. Bigelow1, Sheetal Trivedi2, Franklin D. Lowy2, Henry M. Spotnitz3, Scott M. Hammer2, David J. Brenner1* 1Center for Radiological Research, Columbia University Medical Center, New York, New York, United States of America, 2Division ...

Spectrometry: Absorbance of Visible Light by a Food Colour ...

Spectrometry Absorbance of Visible Light by a Food Colour

the U.S.was 15, and in 1950 it was 19. At the present time (200 8), there are 7 FD&C (food, drug, and cosmetic) dyes allowedfor food use in the U.S. The same 7 and one other dye are allowed for food usein Canada . Some other dyes arealso allowed insome other countries around the world.

Modelling and Control of Doubly Fed Induction Generator ...

Modelling and Control of Doubly Fed Induction Generator

Modelling and Control of Doubly Fed Induction Generator based stand-alone Wind Energy Conversion System A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR

Le Collezioni Le Collezioni - ANKAR

Le Collezioni Le Collezioni ANKAR

aianca alle proprie consolidate collezioni, la ... committenza con il supporto di una realt produttiva che non ... * Nella selezione del personale di Cielo non esiste ...

340B Information Exchange Reference Guide - NCPDP

340B Information Exchange Reference Guide NCPDP

340B INFORMATION EXCHANGE . REFERENCE GUIDE. Version 2.0 . The NCPDP 0B Information Exchange Reference Guide34 was developed to meet the industry needs for electronic communication between trading partners of an individual prescription or

NON ESISTE LA PRIMITIVA DI e - math.uzh.ch

NON ESISTE LA PRIMITIVA DI e math uzh ch

IL TEOREMA DI LIOUVILLE OVVERO PERCHE NON ESISTE" LA PRIMITIVA DI ex2 ... realt a funzioni fdi variabile reale a valori complessi. Chiaramente una fdi