1 App ears Journal of Cryptology , V ol. 9, No. 1, Win ter 1996, pp. 149{166. Preliminary v ersion in Adv ances Cryptology { Crypto 92 Pro ceedings , Lecture Notes in Computer Science V ol. 740, in in k Bric ed., Springer-V erlag, 1992. E. ell P utations: Non-In teractiv e Zero-Kno wledge Certifying erm on an y T rap do or P erm Based utation y Moti Yung Mihir Bellare Abstract In proto cols it is often necessary to v erify/certify the \to ols" in use. This w ork cryptographic or certain in treating a family of trap do subtleties p erm utations in this con text, demonstrates noting the necessit yto\c hec k" certain prop erties of these functions. The particular case w e il- lustrate is of non-in teractiv e zero-kno wledge. W e p oin t out that the elegan t recen t proto col that F ving Lapidot and Shamir for pro of NP statemen ts in non-in teractiv e zero-kno wledge re- eige, p an certi cation of the underlying trap do or additional erm utation, and suggest a metho d quires for certifying p erm utations whic h lls this gap. Departmen of Computer Science & Engineering, Mail Co de t Univ ersit y of California at San Diego, 9500 0114, Gilman Driv e, La Jolla, California 92093. e-mail: [email protected] y Bo h Division, IBM T.J. W atson Researc h Cen ter, PO Researc x 704, Y orkto wn Heigh ts, NY 10598. e-mail: [email protected] 1

2 1 In duction tro es suc as the RSA function, the discrete log function, or, more generally ,an y trap do or or Primitiv h y function, v e applications o v er and ab o v e the \direct" ones to public-k ey cryptograph y . one-w a ha are in (widely) used as \to ols" they the construction of (often complex) cryptographic Namely , also second pap This oin ts to the fact that in this er kind of application, some care m ust cols. proto p in the manner in whic h the \to ol" is used. Chec ks migh t be necessary that are not be exercised public-k applications. in necessary ey for suc h c hec ks arises from the need to consider adv erserial b eha vior of parties in The need cannot proto ypically , the problem is that one T trust a part y to \correctly" cryptographic col. a to ol in question. F or example, supp ose a part y A is supp osed create giv e another part y B the to mo N pro duct of t w o primes, and an RSA dulus onen t e , to sp ecify an RSA function. On a exp of a n um ber N receipt an exp onen t e , it migh t b e imp ortan t that the receiv er kno w that e is and indeed RSA exp onen t (i.e. relativ ely prime to the Euler Phi F unction of N ). This is b ecause an not use the proto col migh t b e suc h that making e in an RSA exp onen t could giv e A an RSA of the tage (suc h applications do exist). On the other hand, the secrecy of the prime factorization adv an prepared is imp ortan t to A , and she is not probably to yield the prime factors of N whic h N of 1 enable B to c hec k the correctness of e w y himself. ould b Proto address this issue in sev eral w a ys. Often, they incorp orate additional sub-proto cols cols These h the \to ol" used is indeed \correct." that sub-proto cols will usually need to whic \certify" zero-kno wledge ones. Since the \correctness" of the to ol can be be form ulated as an NP usually assertion, h sub-proto cols can in some cases be realized, suc y using, sa y , the general in teractiv e b proto cols of [GMW , BC] whic h enable an y NP statemen t to be pro v en in zero-kno wledge. But not alw ys. One reason is that that these proto cols yield only computational zero-kno wledge, and a e ma be in terested in stronger forms suc h as statistical. (One suc h example o ccurs in [BMO ] w y use problem the certi ed discrete log assumption is crucial.) Or, as for the the w e are where of that in w e ma y terested an t a non-in teractiv e solution, so here, again the ab o v e men tioned in w tec hniques are precluded. general particular instance of this issue that w e fo cus on in this pap er is the use of trap do or The erm non-in in p teractiv e zero-kno wledge (NIZK) pro ofs. W e p oin t out that the elegan t utations [FLS] t col of F eige, Lapidot and Shamir proto mak es the (implicit) assumption that recen NIZK trap do or p erm utation is \certi ed." W e note that this assumption is not v alid for standard the trap do or p erm utations lik e RSA or those of [BBS ], and so their proto col cannot (conjectured) or instan with an y kno wn (conjectured) trap do tiated p erm utation. W e suggest a certi cation be metho d to ll this gap, so that any trap do or p erm utation truly suces, and RSA or the construction of [BBS ma y b e used. Our certi cation metho d in v olv es a NIZK pro of that a function is \almost" ] of p and migh t b e utation, indep enden tin terest. a erm w w e b egin b y recalling the notions of trap do or p erm utations and NIZK pro ofs. Belo e then W discuss FLS proto col and indicate the source of the problem. W e then, brie y the discuss our , solution. sections sp ecify the de nitions Later our solution in more detail. and 1.1 T rap do or P erm utations (w Let egin b y recalling, in some detail, the de nition of a trap do or p erm utation generator b e us follo [BeMi]), and seeing what it means for w h a generator to b e certi ed. suc 1 Suc h a problem is not presen t in public-k ey applications. If I wish to publish N and e to sp ecify an RSA digitial e signature heme, there is no question of m y incorrectly c ho osing sc b ecause it isn't to m y adv an tage to do so. 2

3 A tr do or p ermutation gener ator is a triplet of p olynomial time algorithms ( G; E ; I ) called ap gener the and inverting algorithms, resp ectiv ely . The generating algorithm is ating, evaluating , n pair of n -bit strings ( f input ; outputs f a ), describing, resp ectiv ely , a on 1 probabilistic, and and its in v trap If x; y are n -bit strings, then so are E ( f do ;x ) and I ( or f p ;y ). erm utation erse. n n f 0 ; Moreo g v !f 0 ; 1 g er, sp eci ed b y f ( x )= E ( f the ;x ) and maps f ( y ) = I ( f; f 1 ;y ) are f : n 1 v g utations , and f f = f 0 ; . Finally , f is \hard to in of ert" without kno wledge of 1 f . (W e p erm more reader x 2.2 for to precise de nitions). the refer trap do or p erm utation generator ( G; E ; I ). W e call an n -bit string Fix a a tr ap do or p ermu- f -bit string tation f there suc h that the pair ( f exists ; some f n ) has a non-zero probabilit yof if n eing e run G on input 1 obtained . It is imp ortan t to note that not ev ery n -bit string f w b when whic trap or p erm utation. In fact, the set of n -bit strings do h are trap do or p erm utations ma y is a n v ery sparse subset of f 0 ; 1 g be , and p erhaps not ev en recognizable in p olynomial a If it is time. recognizable p olynomial time, w esa y the generator is c erti e d . in ask e ecen t recognizabilit y is a lot to that for. Consider our t w o main (conjectured) W note of trap do or p erm utation generators: examples [RSA], and the factoring based generator of RSA Blum, and Sh ub [BBS]. Neither is lik ely to Blum certi able. This is b ecause, in b oth cases, be certi cation w ould need the abilit y to recognize in p olynomial time the class of in tegers whic h are a pro of (exactly) t w o (distinct) primes. duct imp ortance certi cation arises, as will see, from the use of trap do or p erm utations as The of v in T ypically , one part y (for example, the pro cols. er) giv es the other part y (for \to ols" proto eri er) a string f p whic h is supp osed to be a trap do or example, erm utation. F or securit y the v ma wish to rev eal (as pro of that it is indeed one) the string y f not , but ma y nonetheless reasons he do the v eri er that f con is indeed a trap vince or p erm utation. This is clearly easy if the need to generator is certi ed. Otherwise, the proto col itself m ust address the task of giving underlying con that f suitable is really a trap do or p erm utation. viction for a Do es the same certi cation issue arise also trapdoor. one-w a y p erm uta- versus One-w y dep ends on what w e call one-w a y p erm utations. Tw o kinds of de nitions are used. In tions? It one-w a y p erm utation is a single ob ject, namely a map f the f 0 ; 1 g rst, ! f 0 ; 1 g a ; since it : is single map, no certi cation is needed. But candidate one-w a y p erm utations t ypically o ccur, a est e do or p erm utations, as families; the b lik example is the discrete log, where a mem ber of trap the family is sp eci ed b y a prime p and a generator g . No w, the certi cation issue arises just as b efore. or discrete log it is usually addressed b y usage of the certi ed discrete log assumption. (F k one also the prime factorization of p 1, whic h enables one to c hec vides that g is indeed Here pro generator.) a teractiv e 1.2 wledge Pro ofs Non-In Zero-Kno setting w e fo cus on in this pap er is that of non-in teractiv The zero-kno wledge (NIZK) pro of sys- e tems. is an imp ortan t notion for cryptographic systems and proto cols whic hw as in tro duced NIZK De b F eldman, and Micali [BFM ] and Blum, Blum, San tis, Micali and P ersiano [BDMP ]. There y are n umerous applications. In particular, Naor and Y ung sho w ho w to use NIZK pro ofs to im- plemen t ey cryptosystems secure against c hosen-ciphertext attac k [NaY u ], and Bellare and public-k asser pro tano v el paradigm for digital signatures based on NIZK Goldw ofs [BeGo ]. presen eri er mo is as The ws. The pro v er and v del ha v e a common input w and also share a follo random string (of length p olynomial in the length of w ). W e call this string the r efer enc e string, some and denote it b y . The pro v er m ust con vince the v eri er of the mem b ership of w in usually er xed NP language L . T o this end, the pro v underlying is allo w ed to send the v eri er a single 3

4 message, computed function of w and (in the case where w 2 L ,w e also giv e the pro v er, as as a input, a to the mem b ership of w in L ). W e usually denote this message b y p . an auxiliary witness as (who olynomial time) decides whether or not to accept p a function of w; and eri er is The v e ask that there exist a pro v er who can con vince the v p to accept w 2 L , for all random . W eri er (this the c ompleteness condition). W e ask that for an is pro v er, the probabilit y(o v er the strings y of ) that the v eri er ma y b e con vinced to accept when w 62 L is small (this is the soundness c hoice ,w pro ask the the pro of Finally vided b y the pro v er of the completeness condition (in condition). e w the ) b e zero-kno wledge, b y requiring the existence of an appropriate \sim ulator." F or 2 case L system, sp complete what it means to b e a NIZK pro of eci cation w e refer the reader to a more of . 2.3 x will fo cus here on proto cols with ecien t pro W ers. That is, w e w an t the pro v er of the e v condition e call it the \honest" pro v er) to run in p olynomial (in n = j w j (w time. completeness ) e that w e are considering what are note \single-theorem" or \b ounded" NIZK pro of W called The primitiv e of imp ortance in applications is the \man y-theorem" pro of system (cf. systems. , [BFM Ho w ev er, the former is kno wn to imply the latter, giv en the existence of one-w a y BDMP ]). former. u ]. So w ema y , wlog, stic k to the FLS functions [DeY , Need Certi cation in the for Proto col The 1.3 FLS Lapidot and Shamir [FLS] recen tly presen ted an elegan t NIZK pro of system based on the F eige, trap implicit or p erm utations. The assumption, of in their analysis, is that the under- existence do do the p erm utation generator is certi ed. Here w e indicate whence arises trap need for this lying or will w v Once iden ti ed the source of the problem, w e eha discuss ho ww e prop ose to certi cation. e e it. solv L b e a language in NP , and let ( G; E ; I ) b e a trap do or p erm utation generator. Fix a common Let n w ; 1 g input , and let denote the reference string. W e will describ e ho w the pro v er and v eri er 0 2f w to erate under the FLS proto col. First, ho w ev er, op e need some bac kground and instructed are notation. some ev en if f is First, not a trap do or p erm utation, w ema y assume, wlog, that E ( f note ;x ) that n n ; us, f n do es sp ecify (via E ) a map from f 0 -bits 1 g long. to f 0 ; 1 g Th ; sp eci cally , the map is b y x 7! E ( f e ;x ). W giv call this map the function sp eci ed b y f en under E , and will denote it b Of course, if f y is a trap do or p erm utation then f is a p erm utation. f . duct, and n -bit strings then H ( x; r ) denotes the dot pro are o v er GF(2), of x and r (more x If r L n x; r ) = precisely , H a x is r H ). The ( of Goldreic h and Levin [GoLe ] sa ys that theorem i i =1 i the ( G; E ; I ). V ery informally , this \hard-core" predicate follo wing. Supp ose w e run G for means n n get ( f input ; 1 f (on ), select x and r at random from f 0 ; 1 g ) , and let y = f ( x ). Then, giv en to equally and the task of predicting H ( x; r ), and the task of nding x , are , hard. r y e no w ready to describ e are proto col. W the n that the pro v er P run G on input 1 The to obtain a pair ( f proto ; col f rst ). P is then asks f instructed to V (while k eeping to f send to himself ). And the is righ t here, in this rst step. The analysis of [FLS] assumes that the problem e v erforms this step correctly . This ma y b p justi ed under the assumption that the trap do or pro er erm utation generator is certi ed. If the generator is not certi ed, a p heating pro v er could, when c w L , select, and send to the v eri er, an n -bit 62 whic his not a trap do or p erm utation. As w e string will see, this could compromise the soundness of the proto col. Let us pro ceed. as v er has supplied f Once , the reference string is regarded pro a sequence = y r r y ::: the 1 1 l l of l blo c ks of size 2 n , where l = l ( n ) is a (suitable) p olynomial (blo c k i consists of the pair of n blo bit y eri er r v ). W e sa y that the pro v er \op ens strings c k i with v alue b the " if he pro vides i i i 4

5 with an string x n suc h that f ( x -bit ) = y certain and H ( x ens ;r op ) = b w . The pro v er no i i i i i i pro of string (and the proto col sp eci es ho w an honest random v er should c ho ose whic h ks the blo c to op en). Based on the v alues blo the op ened blo c ks, their relativ e lo cations in the reference c ks of the input, the v eri er decides whether or common to accept. Exactly ho whedoes and string, not not relev an t to our discussion. Exactly ho w the honest pro v er is supp osed to decide whic h this is ks op c en (whic h he do es as a function of the blo c k, the common input, and his witness to the blo to tto ership common input in L ) is also not relev an the our discussion. What is imp ortan t b of mem that the soundness condition relies on the assumption that, with f to xed, there note is exists unique a y to op en an y giv en blo c k. If it is p w for the pro v er to op en a blo c k with v alue a ossible 0 or 1, then the soundness of the FLS proto col is compromised. either assumption is (one and) only one w a y to op en a blo c k is justi ed if f The is a that there or erm utation, b ecause, in this case, f is a p erm utation. Ho w ev er, if f a is not do trap do or trap p exists utation, f ma y not b erm a p erm utation, and in suc h a case, the p ossibilit y then that blo c ks p e y e op ened with v alues b the pro v er's c hoice. ma of e note that the gap is not an academic one. Considering concrete cases, suc h as the use of W [BBS or do or p erm utations based on quadratic residuosit y that are suggested b y trap ], w e the RSA that pro v er ma the indeed c heat. see y solution that rst suggests itself is that the pro v er pro v e (in NIZK) that he really got f b y The ho the (this is an NP statemen t). The problem is, G w ev er, that to pro v e this generator running statemen t itself requires the use of a trap do or p erm utation, and w e are only c hasing our tail. new that in the ab o v e NIZK pro of, a (c heating) pro v er ma y c ho ose f Note as a function of the random string. as p oin ted out in [FLS], this causes no diculties. W e ma y assume, in the But, that string is c hosen after f the is xed; later w e apply a simple transformation analysis, reference results the pro of system b eing secure ev en if f as w as c hosen h a function of . W e will whic in this with explicitly when it arises. deal issue un et. [FLS] also consider the eige of a computationally al b ounded pro v er, where they F case a one-w a y , rather than trap do or, p erm utation. As w esa wabo v e, the certi cation problem still use just b efore. arises as 1.4 Our Solution Let denote the n -bit string pro vided b y the pro v er in the rst step of the FLS proto col, as f es ed v e. As that discussion indicates, soundness do o not really require that f be a describ ab do or p erm utation. All that it requires is that f b e a p erm utation. So it w trap suce to certify ould this fact. n n g a map from f 0 ; 1 g o to f 0 T 1 certify that is a p erm utation seems lik e a hard task (it is a ; coNP statemen t). What w e will do is certify it is \almost" a p erm utation, and then sho w that this suces. n , let us call f an -p erm utation if at most an fraction of the p oin ts in f 0 ; 1 g More ha v e precisely than pre-image under f . W e sho w that on common input f to , and access more a common one 1 e, length reference of n , the pro v (random) can pro vide the v eri er with a non-in teractiv string er zero-kno pro of that that f is an -p erm wledge F or a more precise statemen t of the theorem utation. and its pro of w e refer the reader to x 3. W e sho w that adding this step to augmen t a m ultitude of indep enden t FLS proto col in- then language) yields NIZK pro of system (for an y NP a giv en the existence of an y (not necessarily stances certi ed) trap do or p erm utation generator. A complete pro of of this fact is in x 4. W e note that can this of is in fact quite indep enden t of the details of the FLS proto col and pro be understo o d tec without deep kno wledge of the a hniques of that pap er. 5

6 Our solution applies for the usage of one-w a y (rather than trap do or) p erm utations in the also proto col an un b ounded pro v er. [FLS] with 2 Preliminaries egin b y summarizing some basic notation and con v en tions whic h are used throughout the e W b what W discuss trap do or p erm utations and sa y then it means for them to b e \certi ed." er. pap e e recall the de nition, and some basic prop erties, of non-in Finally e zero-kno wledge pro of ,w teractiv systems. and Con v en tions 2.1 Notation algorithms use and con v en tions for probabilistic notation that originated in [GMR ]. e the W emphasize the n W b er of inputs receiv ed b y an algorithm as follo ws. If algorithm A receiv es e um one input w e write \ A ( )"; if it receiv es t w ow e write \ A ( ; )", and so on. If A is only probabilistic a algorithm for an y input i the notation A ( i ) refers to the probabilit y space whic h to the string then, assigns the y that A , on input i , outputs . probabilit elemen is probabilit y space w e S its supp ort (the set of a ts of p ositiv e probabilit y) b y If denote S ]. [ f ( ) and g ( ; ) are probabilistic algorithms then f ( g ( ; If is the probabilistic algorithm )) obtained y comp osing f and g (i.e. running f on g 's output). F or an y inputs x;y;::: the asso ciated b y g is denoted f ( probabilit ( x; y ; )). space R denotes a probabilit If space then x S S is the algorithm whic h assigns to x an elemen t y randomly selected according to S . In the case that [ S ] consists of only one elemen t e w e migh t also write x e . or F S;T;::: , the notation probabilit y spaces i h R R ; ) p x ( S x; y y T ; ; Pr : probabilit y that the predicate p ( x; y ; ) is true after the (ordered) execution of the denotes the R R , y algorithms S , etc. x T b e a function. The notation Let f R R x; f ; ): x f S ; y ( T ; g y denotes probabilit y space whic h to the string assigns the probabilit y the i h R R : x; y ; ) : x = Pr ; y ( T ; f S When e sa y that a function is computable w p olynomial time, w e mean computable in time in p olynomial in the length of its rst argumen t. tly W e in terested in families of ecien b computable functions of p olynomial description. will e follo wing de nition will b e a con v enien tw a y of capturing them. The time 2.1 et E ( ; ) b e a p olynomial L c omputable function. We say that E sp eci es an De nition n family of functions if for e ach n> 0 and e ach f ;x eciently 2f 0 ; 1 g computable it is the c ase that n j ;x ) j = n . L et n> 0 and f ( 2f 0 ; 1 g f . The function sp eci ed b y f E under E is the map fr om n n 1 g f to f 0 ; 1 g 0 given by x 7! E ( f ; ;x ) . 6

7 2.2 T do or P erm utations and Certi ed Ones rap us Let precise de nition of trap do or p erm utations and see what it means for them to b e presen t a Micali that is from Bellare and ws [BeMi]. de nition \certi ed." The follo rap do o r P ermutation Generato r) L et G b e a pr ob abilistic, p olynomial time algo- De nition 2.2 (T trap let b ep olynomial time algorithms. We say that ( G; E ; I ) is a I do o r p ermutation rithm, and E; if fol lowing c the hold: r generato onditions n or every n> 0 , the output of G on input 1 is a p air of n bit strings. Generation: F n ar ( f ermutation: ; or f every ) 2 [ G (1 n )] , the maps E ( f > ; ) and I ( 0 f and ; ) F e P n ( g of which ar e inverses of e ach other (that is, I f 0 f ; ;E ( f 1 ;x )) = x and p ermutations n ( E f ( ;y )) = y for al l f y 2f 0 ; x; g ;I ). 1 y: F or al l pr ob abilistic p olynomial time (adversary) algorithms A ( ; ; ) , for al l c onstants Securit and suciently ge n , c lar h i R R R n n n c )= G (1 y ); y : f 0 ; 1 g ( f x f ( A (1 ; ;f E ;y ) f n ;x ) : Pr ; c l G; E ; I the generating, al and inverting algorithms, r esp e ctively. We evaluating standard (conjectured) \trap do or p erm utations," suc h as RSA [RSA] and the factoring based The ones of Blum and Sh ub [BBS ], do t this de nition, after some minor transformations (the Blum, um for arises from the fact that these n transformations ber theoretic functions ha v e these need n e details). f 0 ; 1 g Z ;w than refer the reader to [BeMi] for domain rather N n f erm utation generator If G; E ; I ) is xed and ( trap a ; do f or ) 2 [ G (1 p )] for some n> 0, ( in informal e call f then, a trap do or p erm utation. It is imp ortan tto note that not discussion, w f n is a trap do or p erm utation: it is only one if there exists some ery f string suc h that ev bit n strings ) 2 [ G (1 f )]. In fact, the set of ( ; bit f whic h are) trap do or p erm utations ma y be a ( n n subset of f 0 ; 1 g in , and, in general, ma y not b e recognizable fairly p olynomial (in n ) time. sparse sp a or p erm utation generator do es ha v e the do ecial prop ert y that it is p ossible to recognize trap If trap do or p erm utation in p olynomial time then w esa y that this generator is c erti e d . The more a de nition ws. follo formal 2.3 L et ( G; E ; I ) b ea tr ap do or p ermutation gener ator. We say that ( G; E ; I ) is certi ed De nition the language if [ n n n g 2f 0 ; 1 g )] : 9 = f g 2f 0 ; 1 L (1 such that ( f G ; f f f ) 2 [ ;I G;E 1 n in BPP is . utation note (conjectured) trap do or p erm standard generators are (probably) not certi ed. e that W RSA In (probably) not certi ed, and nor is the trap do or p erm utation generator of particular, is Blum and Sh ub [BBS Blum, This is b ecause, in b oth these cases, the (description of ) the trap do or ]. utation f p includes a n um ber whic h is erm pro duct of t w o primes, and there is (probably) no a p olynomial time pro cedure to test whether or not a n um b er is a pro duct of t w o primes. The imp of certi cation stems, as w e ha v e seen, from applications in whic h one part y ortance example, pro v er) giv es the other part y (for (for the v eri er) a string f example, whic h is the supp osed to b e a trap do or p erm utation. F or securit y reasons he ma y not wish to rev eal (as pro of y one) the string that f is , but ma it nonetheless need to con vince the v eri er that f indeed 7

8 is indeed trap do or p erm utation. In particular, the (implicit) assumption in [FLS] is that the a do or erm utation generator b eing used is certi ed. As the ab o v e indicates, this means that trap p heme their instan tiated with RSA or the trap do or p erm utations of [BBS ]. In later cannot sc be will an w ho w to extend their sc heme so that e y (not necessarily certi ed) trap do or sections w sho y utation (so that RSA or the generator of [BBS] ma suces in fact b e used). erm p generator n n ( G; E ; I ) is a trap do or p erm utation generator, f W 2 e 0 ; 1 g note , and x 2 f 0 ; 1 g that if f y assume, without loss of generalit y , that E ( f w ;x ) is an n -bit string. Hence E ( f ma ; ) then e n n ,ev from f 0 ; 1 g sp to f 0 ; 1 g some es en if f map is not a trap do or p erm utation. That is, do ecify the terminology of De nition 2.1 , w ema y assume, without loss of generalit y , that the algorithm in sp an ecien tly computable family of functions. Of course, the map E ( f E ; ) need not b e eci es n p on f 0 ; 1 g erm . a utation teractiv Zero-kno wledge Pro of Systems Non-In 2.3 e will consider non-in teractiv e zero-kno wledge pro of systems for NP . It is helpful to b egin with W e follo wing . the terminology We L ( ; ) b ea binary 2.4 elation. et say that is an NP-relation if it is p olynomial De nition r c omputable and, mor e over, ther e exists a p olynomial p such that ( w; time w ) = 1 implies j w j w j ) . F or any w 2f 0 ; 1 g p we let ( w )= f w 2f 0 ; 1 g j : ( w; w )=1 g denote ( witness set of the We let L for = f w 2f 0 ; 1 g w : ( w . 6 = ;g denote the language de ne d by . A witness selecto r ) is a map W : L . !f 0 ; 1 g W with the pr op erty that ( w ) 2 ( w ) for e ach w 2 L . a is in NP i there exists an NP-relation suc h that L = L language L Note that the de nition of computational indistinguishabili t recall ensem bles. First, recall that W e yof : g 0 ; 1 function ! R is ne gligible if for ev ery constan t d there exists an in teger n f suc h that a d d j w j ( ) for all w of length at least n . w d A n ensemble indexe dby L f 0 ; 1 g ction is a c ol le De nition f E ( w ) g 2.5 es ac of pr ob ability sp L w 2 supp ) one for e ach w 2 L . L et E nite = f E ensembles ( w (of g ort), e b and E g = f E ) ( w 2 2 w 2 L L 2 1 1 w a c ommon index set L . We say that they ar e (computationally) indistinguishable if for every over the f family g function D algorithms, of non-uniform, p olynomial time L w 2 w i h h i R def R D E ( v )=1 : v = ( ( w ) w Pr Pr D ) ( v )=1 : v ) E w ( 2 w w 1 ne gligible. is tis, that ws is based on that of Blum, The San follo Micali and P ersiano [BDMP ]. Ho w- de nition De er, w e state the zero-kno wledge condition di eren tly; sp eci cally ,w e ev the notion of a witness use selector state the zero-kno wledge condition in terms of the standard notion of computational to zero-kno indistinguishabili , whereas in [BDMP ] the y wledge condition mak es explicit reference to t \distinguishing" algorithms. The t w o form ulations are, of course, equiv alen t (but w e feel this one is a simpler b ecause of its \mo dularit y .") little 2.6 elation et b e an NP-r De nition and let L = L L . L et P b e a machine, V a p olynomial time machine, and S a pr ob abilistic, p olynomial time machine. We say that ( P; V ; S ) de nes a a non-interactive wledge p ro of system (NIZK pr o of system) for if ther e exists zero-kno p olynomial lowing l ) such that the fol ( thr e e c onditions hold. 8

9 Completeness: or every w 2 L and w 2 ( w ) , F h i R l ( n ) V f 0 ; 1 g w; ;p )=1 ; p P ( w; w; ) : = 1 ; Pr ( n = w j . wher e j b F or P and every w 62 L , Soundness: machine every i h R l ( n ) 1 b V ; 1 g ( w; ;p ; p )=1 P ( w; ) Pr : f 0 ; 2 n j w j . e wher = wledge: L et W b e any witness sele ctor for . Then the fol lowing two ensembles ar e Zero-kno ly) indistinguishable: (c omputational ( (1) ) g S f w L w 2 R l ( j w j ) ; 0 ; 1 f ;p ) : ( f p P ( w; W ( w ) ; ) g (2) . g L 2 w c al l P the p rover , V the veri er and S We simulato r . The p olynomial l is the length of the the reference . We say that P is ecient if it is p olynomial time c omputable. string e call the \common random string" or the \reference string." W not hoice = 2 as the error-probabilit y in the soundness condition is 1 essen tial. Giv en c of The k ( n ) an the error-probabilit y can be reduced to 2 y p olynomial k ( b y running k ( n ) indep enden t ), of the original pro of system in parallel and accepting i all sub-pro copies are accepting. ofs b de nition (cf. [BDMP ]) asks that in the soundness condition the adv ersary A P be stronger w ho to select a w 62 L as a function of the reference string. This de nition is, allo w ev er, implied ed S y one ab b v e. More precisely , giv en ( P; V ; the ) satisfying the ab o v e de nition, one can construct o 0 0 0 ;V ( ;S P ) satisfying the more stringen t de nition, b y a standard tric k. Hence, w e will stic k to the simple de nition. e note e are considering what ha v e b een called \single-theorem" or \b ounded" NIZK pro of W w v is, en reference string can be used to pro giv e only a single theorem. The That the systems. imp ortance in applications (cf. [BeGo , NaY u]) is the \man primitiv pro of system. eof y-theorem" w er, De San tis and Y ung [DeY u ], and F ev Lapidot and Shamir [FLS], ha v e sho wn that the Ho eige, (for some NP-complete relation) of a b ounded NIZK existence of system with an ecien t pro v er pro implies existence (for an y NP-relation) of a man y-theorem NIZK pro of system (with an ecien t the en v long as one-w a y functions exist. Hence, giv as that the (b ounded) NIZK pro of systems pro er), e construct do ha v e ecien t pro v w w ema y , without loss of generalit y , stic k to the b ounded case. ers, 3 NIZK Pro of that a A is Almost a P erm utation Map Supp ose E sp eci es an ecien tly computable family of functions (cf. De nition 2.1 ), and supp ose n f 0 ; 1 g f for some n > 0. W e address in this section the problem of pro viding a NIZK pro of 2 E eci ed b y f the under sp is \almost" a p erm utation. that function e note that although this problem is motiv ated b y the need to ll W gap in the FLS proto col the (cf. 1.3 ), the results of this section migh tbeofin terest in x o wn righ t. Th us, w e prefer to view their them indep enden tly , and will mak e the link to [FLS] in the next section. the task of pro viding a NIZK pro of that the function sp eci ed b y f In under E addressing is \almost" a p erm utation, w e m ust b egin b y clarifying t w o things. First, w e need to sa y what n n 0 a function f : f 0 ; 1 g it ! f means ; 1 g for to be \almost" a p erm utation. Our de nition, of 9

10 an erm utation, follo ws. Second, w e m ust also sa y what w e mean, in this con text, b y an NIZK -p of pro problem is not one of language mem b ership). This is clari ed b elo w and in the (b ecause the Theorem . of statemen t 3.2 egin with the de nition. It sa ys that f is an p erm utation if at most an fraction of the Let us b n f 0 ; 1 g in ha v e more than one pre-image (under f ). More formally ,w eha v e the follo wing. p oin ts n n n > 0 and f : f 0 ; 1 g set ! f 0 ; 1 g De nition . The collision 3.1 of f , denote d C ( f ) , is L et n 1 n 1] : j f 1 g ( y ) j > 1 g . L et 2 [0 ; ; . We c al l f an -p ermutation if j C ( f ) j 2 2f . 0 f y will no w turn to the NIZK pro of. The formal statemen t and pro of of the theorem follo w. Let W e w egin, w ev er, b ysa ying, informally , what ho eac hiev e, and giving the idea. b us E sp ecifying an ecien tly computable family of functions, and w W x a map : f 0 ; 1 g e x ! e (0 1]. W e consider a pro v er and v eri er who share a (random) reference string and ha v e as common ; n a 0 ; 1 g string . If f (the function sp eci ed b y f 2f under E ) is a p erm utation then the input f er vince con v the v eri er to accept (this is the completeness condition). If f is not an can pro usually n erm utation, then the v eri er will )-p reject (this is the soundness condition). ( e note the gap bet w een these t w o conditions: w e are guaran teed nothing if f is an ( W )- n p utation (but not a p erm utation). This is one w a y in whic h this \pro of system" di ers from erm o ofs mem b ership, where there are only t w language p ossibilities: either the input is in the pro of (and completeness applies) or it is not (and soundness applies). language v addition, f is a p erm utation, the in teraction yields no (extra) kno wledge to the In eri er. when This formalized, as usual, b y requiring is existence of an appropriate \sim ulator." the The idea is v ery simply stated. Let b e the reference string, whic hw e think of as divided in to blo c of size n . If f is not an ( n )-p erm utation, then eac h blo c k has probabilit y at most 1 ( n ) ks 1 b range of f . So if w e ask the pro v er to pro vide the in v erse of f on eing the ( n ) di eren t in of 1 ( n ) probabilit y at most (1 ( n )) then ks, he can succeed with 1 = 2. Moreo v er, a collection c blo pre-images of f on random p oin ts pro vide no information ab out (the easily computed) f ,sothe of of zero-kno wledge. pro is 3.2 L et E sp e cify an eciently c omputable family of functions. L et : N ! (0 ; 1] , and Theorem 1 is p olynomial ly b ounde d and p olynomial c omputable. Then ther e is a p olynomial assume time or acle machine A ,ap olynomial time machine B ,andapr ob abilistic, p olynomial time machine time such that the fol lowing thr e e c onditions hold. M n et 0 and f Completeness: 2f 0 1 g et . L L f denote the function sp e ci e d by f n> under E . ; Supp ose f is a p ermutation. Then h i 1 1 R ( n ) n f ;p ; )=1 f 0 ; 1 ; p A g ( ( f : ; ) f = 1 : B Pr 1 f 1 A with or A f e denotes . Her acle n n > 0 and f 2 f 0 ; 1 g Soundness: . L et f denote the function sp e ci e d by f L under E . et b , is not a ( n ) -p ermutation. Then for any function ose P f Supp h i 1 R n ( ) n 1 b 1 g ( f Pr ; ;p )=1 : ; p f P ( f B ; ) 0 ; : 2 n et et > 0 and f L 2 f 0 ; 1 g . L n f denote the function sp e ci e d by f wledge: un- Zero-kno R , and supp ose f is a p ermutation. Then the distributions M ( f der ) and f ( ;p ) : E 1 1 n ) n f ( ; p 0 A f ; 1 g f ( ; ) g ar e e qual. 10

11 n Pro ecify the algorithm for v eri er. Let f W 2 f 0 ; 1 g sp and let = of: ::: e where 1 1 ) ( n n . Let f denote the function sp eci ed b y f h under length . On input f has ; , and a eac E i 1 eri er B rejects if the length of p is not ) string ( n p , . Otherwise, it partitions p in to the v n blo ks of size n . W e denote the i -th blo c k b y p consecutiv , c that p = p e ::: p B Then . so 1 ( ) n 1 i 1 h i =1 ;::: ; accepts i ( n ) it is for case that f ( p eac )= . the i i n the pro v er A . Let f w 2f 0 ; 1 g ecify and let sp e ::: Next length has h eac where = 1 i 1 ) n ( f denote the function sp eci ed b y f E under n . and supp ose f is a p erm utation. On input Let , 1 1 1 eac f as oracle, A sets p f = f giv and ( and sets ) for en h i = 1 ;::: ; , ( n ). It then i i = p is ::: p true. p condition completeness the that and outputs p . It is easy to see 1 ) 1 n ( n 1 k the soundness condition. Let f no 2 f 0 ; c g hec and let f denote the function sp eci ed W w e 1 n . ) e recall that C ( f )= f y 2f 0 ; 1 g E : j f under f ( y y j > 1 g is the collision set of f . Let b W n 1 b 2f 0 ; 1 g f : j f f y ( y ) j =0 g ( e the set of n bit strings not in the range of f . Note that D )= def n f ) jj C ( f ) j . W e let ( n ) yof = j D ( f ) j = 2 j denote the densit D D ( f ). No w assume f is not a ( n )- ( n or j C ( f ) j ( n )2 erm , and th us ( n ) ( n ). F Then an y xed string = p ::: , utation. 1 1 n ( ) wing the clearly equiv alen t: follo are f exists p suc h that B ( string There ; ;p )=1 a 1 eac h i =1 ;::: ; range ( n ) it is the case that F is in the or of f . i 1 ;::: if is c hosen at random, then for eac h i =1 w ; Ho ev ( n ), the probabilit y that er, is in the i b of f is at most 1 ( n ), indep enden tly for eac h i . So for an y range P , i h 1 1 R ) ( n n ( n ) b ( 0 ; p ; P f f 1 ; ) g [1 ( n )] ; ;p )=1 : Pr ( f B 1 ( n ) [1 ( n )] 1 : 2 n denote ecify . Let f sp 2 f 0 ; 1 g w and let f M the function sp eci ed b y f no under E . e W n is a p erm utation. On input f Supp , the mac hine M pic ks ose ;::: ; random at f g 1 ; 2f 0 1 1 ) ( n 1 and = f ( The ), for eac h i = 1 ;::: ; and sets ( n ). It sets p = ). ::: ;p ( outputs 1 i 1 i ) n ( wledge easy to c hec k. zero-kno is note that, in the ab o v e, w e are thinking of f W as b eing the common input, and the reference e is c hosen at random indep enden tly of f string . Of in our application, the pro v er ma y course, w ho as a function of the reference string. This, ho f ev er, is easily dealt with b y a standard c ose k, and so, for the momen t, w e fo cus on the case tric ted here. When w e put ev erything presen together Theorem 4.4 ) w e will return to this issue and sho w (cf. ho w to deal with it, explicitly giv en what w e establish here. W e note also that no cryptographic assumptions w ere needed for the ab o v e pro of, and the zero-kno wledge \p erfect." is Using Certi cation Pro cedure 4 the this section w e sho who w the In pro cedure of Theorem 3.2 can b e com bined with the certi cation results of [FLS] to yield a NIZK pro of system for an y NP-relation. W e stress that the argumen tw e not presen here dep ends little on the sp eci cs of the proto col of [FLS ], and our pro of do es t presume y familiarit with that pap er. W e b egin b y extending De nition 3.1 with the follo wing terminology . 11

12 n n De nition n> 0 and f : f 0 ; 1 g 4.1 !f 0 ; 1 g et . L et = L ::: ach for some l 2 N , wher e e 1 l g length We say that is f -bad if ther eisan i 2f 1 ;::: ;l . such that n 2 C ( f ) . We denote has i i ( f ) the set of al l ln -bit strings which ar e by C ad. f -b l w state, without pro of, a lemma whic h can be deriv ed from [FLS]. The formal statemen t e W no e since is rather long, let us rst try to giv it an informal explanation of what it sa ys. ws, follo but, w e sho w ho w to \measure" the \additional" error incurred b y the [FLS ] proto col in Brie y , precisely that b eing used is not a p erm utation. More function , w e x a trap do or the the case utation generator ( G; E ; I ) and an NP-relation . In order to mak e explicit the role pla y ed p erm in the used in the pro of, w e consider an in teraction function whic h the common input is a pair b y def )of n -bit ( The pro v er wishes to con vince the v eri er that w 2 L w; = L a f using f strings. as , ol." do not, a priori, kno w whether or not f W is a trap do or p erm utation. \to e assuming w) sa ys that if w 2 L , then, elo f condition really is a trap do or completeness (b The utation, the pro v er can con vince the v eri er that p 2 L . Moreo v er, the zero-kno wledge erm w sa this pro of is zero-kno wledge. The part w e are ys concerned with, ho w ev er, is the condition really condition. soundness soundness condition sa ys that if w 62 L then the The y that a pro v er can con vince the probabilit to accept is b ounded b y a small error (1 = 4) plus a quan tit y that dep ends on f v . Sp eci cally , eri er quan ), y is the probabilit y that the reference string is f -bad (cf. De nition 4.1 this where f is tit function b y f eci ed under E . the sp priori, this quan tit yma y b e large. Once w A v e stated the lemma, w e will sho who wtouse eha the results of the previous section to decrease it. Lemma 4.2 L et ( G; E ; I ) b e a tr ap do or p ermutation gener ator. L et b e an NP-r elation, and let . Then ther e exists a p olynomial time machine L A , a p olynomial time machine = B , L ( olynomial time machine pr M , and a p olynomial l abilistic, ) such that the fol lowing thr e e a p ob hold. c onditions n 2 L , every Completeness: 2 ( w ) , and every ( f F ; every f or ) 2 [ G (1 w )] , w h i R l ( n n ) 0 ; 1 g ( w; ;f f ;p ; p A ( w; w; ;f )=1 ; : f ) Pr = 1 ; B e wher j w j . n = n b machine F P , every w 62 L , and every f Soundness: 2f 0 ; or g every , 1 h i R l ( n n ) b f 0 ; 1 g ( w; ;f Pr ;p ; p )=1 P ( w; ;f : ) B i h R ) n n ( l 1 g : f 0 ; 1 f C 2 +Pr ( ) ; ( n ) l 4 e j w j and f denotes the function sp wher ci e d by f e under E . = n Zero-kno et W b e any witness sele ctor for L . Then the fol lowing two ensembles ar e wledge: omputational ly) indistinguishable: (c R R w j j f f ) ;p G (1 ) : ( ); ( ;p ) f M ( w; ( ; ; ;f f f ) g (1) 2 w L R R l ( j w j ) j j j w j w : (2) f ; ( f f ; 0 f ; ) 1 G (1 g ( ); p ;f A ( w; W ( w ) ; ;f ; ;p f ) ) g . 2 L w lemma, w don't w an t to pro v e Although e some in tuition is easily pro vided. Namely , [FLS] this sho w that error probabilit y less than an y (in particular =1 = 4) can b e ac hiev ed, assuming only not that reference string is not f -bad (i.e. they do the use an ywhere that f is p erm utation). Hence 12

13 the pro can c heat with probabilit yat most 1 = 4 plus the probabilit y that the reference string is v er F f full pro of, w e refer the reader to [FLS]. or -bad. the t to remo v e this extra f sho dep enden w term in the soundness condition b yha ving w who W eno er certify (using the pro of system of Theorem 3.2 ) that the is almost a p erm utation. The pro v f follo pro vides the formal statemen t and pro of, but let us ws sa y , informally , what lemma that rst ening. happ is ( w; f On ), w e ha v e common pro v er giv e the pro of of Lemma 4.2 , and also, using a input the part the reference string, run the pro cedure of Theorem 3.2 . The v eri er accepts i b oth separate of v pro accepted (b y their resp ectiv e are eri ers). The completeness and zero-kno wledge these ofs of y the same as in Lemma 4.2 (except that the reference conditions is longer, indicated b y sta string a t sym bol for its length); clearly , this di eren b ecause the additional pro of cannot h urt using is The soundness condition, ho w ev er, no w b ecomes more lik e a \real" soundness condition in them. the that of Lemma 4.2 has disapp eared. \extra" term to pro the new soundness condition, w e will ha v e of consider t w o cases. First, w e assume the of In is \almost" a p erm utation, and sho w that in this case the \extra" term from the soundness that f Lemma condition is small. Second, w e assume that f is not \almost" a p erm utation, and of 4.2 y) fact w e are guaran teed rejection (with high probabilit the b y the soundness condition of use that 3.2 . Theorem 4.3 L et ( G; E ; I ) b e a tr ap do or p ermutation gener ator. L et b e an NP-r elation and let Lemma 0 0 = Then ther e exists a p olynomial time machine A L , a p olynomial time machine B . , a L 0 m olynomial time machine M ob , and a p olynomial p ( ) such that the fol lowing thr e e pr abilistic, onditions hold. c n f 2 L , every w 2 ( w ) , and every ( f Completeness: ; or F every ) 2 [ G (1 w )] , i h R 0 m ( n n ) f 0 ; 1 g ( w; ;f ;p B ; p A ( w; w; ;f )=1 ; : f ) Pr = 1 ; wher e j w j . n = n b g P , every w 62 L , and every f machine 2f 0 ; 1 every F , or Soundness: i h R n ) m 0 ( n 1 b ; 1 g Pr ( w; ;f P ; p ;p )=1 ( w; : ) B f 0 ;f ; 2 e = j w j . wher n wledge: L et W b e any witness sele ctor for . Then the lowing two ensembles ar e Zero-kno fol omputational indistinguishable: (c ly) R R j w j ( f ) ;f G (1 (1) ;p ) ); ( ;p ) : M ( w; f ( ; f f f ) g ; 2 w L R R m w j ) j w j ( j j w j ) : ; ( f (2) ; f f 0 ; 1 G (1 g f ( ); p A ( w; W ( w ) ; ;f ; ;f f ) ) g ;p . L 2 w Pro A; of: B; Let M be the mac hines, and l the p olynomial, sp eci ed b y Lemma 4.2 . Let ( )= algorithm 1 ( )). W e apply Theorem 3.2 (with the l E b eing the ev aluating algorithm of our (4 = do or family) to get a triplet of mac hines A; B ; M satisfying the conditions of that theorem. W e trap 1 l )= m ( )+ ( ( )=5 l ( ). let 1 ) n ( l =4 n ) n ( bits n If then denotes the rst , n ) n ( m length of string a is [1] Notation: ) denotes the last l ( n [2] n bits. and 0 n w sp ecify the algorithm for the v eri er B 2f . Let f W e 0 ; 1 g no and let be a string of length 1 eri er n . On input f m ; , and a string p , the v ( B rejects if j p j < n ) ( n ) n . Otherwise, it 13

14 accepts if only if and ( ;p [1]) = 1 and f B ( w; [2] ;f ; ;p [2]) = 1 ; B [1] 1 [1] where rst ( n ) n bits of p and p [2] denotes the rest. denotes p the 0 n ; w 2 L and w 2 ( w e Let n = j w j . Let ( f A ecify sp f . ) 2 [ G (1 Let )]. Let b e a string Next w ). 1 0 f input w; w; ;f ; of length f m , the mac hine A ( sets p n = A ) n ( f . ; [1]) (note that On [1] 0 1 can time b ecause, using in f output , it olynomial compute f this obtain in p olynomial A p can outputs p A ( w; w; [2] ;f sets then = f It ). Finally it sets p = p [1] p [2] and [2] p . The time). ; that completeness condition holds follo ws from the resp ectiv the completeness conditions of fact e 4.2 and Theorem 3.2 . Lemma w for the in teresting part, namely the soundness condition. Supp No w 62 L . Let n = j w j and let ose n ; 1 g f . Let f denote the function sp eci ed b y f 2f under E . W e split the pro of in to t w o cases. 0 1: f a ( n )-p erm utation. Case is n )2 ) j ( n f j . So ( By C assumption, i h R l ( n ) n 1 ) : [2] 2 f 0 ; 1 g C Pr ( )= n f ( n ) l ( [2] : ) n ( l 4 b soundness condition of Lemma 4.2 it follo ws that for ev ery mac hine By P , the h i R n l ( ) n 1 1 1 b = : + 1 ;f ; 0 f [2] : ; p [2] 1 P ( w; ;f = ) [2]) ;p g Pr B w; ( 2 4 4 0 condition follo ws from the de nition of B The . Let us pro ceed to the next case. soundness 2: is Case not a ( n )-p erm utation. f b for of Theorem 3.2 implies that The an y function soundness P , condition i h 1 R ) ( n n 1 b B ; 1 g ; [1] ;p [1]) = 1 : ; p [1] P ( f ( ; [1]) Pr f f : 0 2 0 soundness follo ws The from the de nition of B directly . This completes the pro of then condition soundness the condition. of wledge, again, follo ws immediately from Lemma 4.2 and Theorem 3.2 The Let w 2 L zero-kno . n 0 f ; ; and f let ) 2 [ G (1 n )]. On input w; f = j w f j , mac hine M . runs M on input f Let to ( ; [1]). It then runs an M on input w; f ( [1] f ;p to get an output ( [2] ;p [2]). It sets output get = [1] [2] and p = p [1] p [2] and outputs ( ;p ). existence more needed to deriv e from Lemma 4.3 the is of NIZK pro of systems for an y step One (giv en the existence of a trap do or p erm utation generator). Namely , the in teraction NP-relation ust b e on input w (alone); the pro v er m ust b e allo w ed to select f m (whic h in Lemma 4.3 is part of the common not only as a function of w but also as a function of the reference string. Clearly , input) to w ema y simply ask the pro v er condition, select f the b y running the generation in completeness G . An y problems that arise will b e in algorithm soundness condition, where a c heating pro v er the e full adv an tage of the freedom to c tak ose f will as a function of the reference string. ho F or w 62 L , w ema y use the follo wing \tric k" (a standard probabilistic one, used, for the same n 1 ] and [FLS]). F or eac h xed f purp 2 f 0 ; in g [BDMP , w e reduce the probabilit y that the ose, ( n +1) teraction on inputs ( w; f etition. ) to 2 v eri er accepts the , b y parallel rep in It follo ws that n ( there exists a string f the 2f 0 ; 1 g y suc h that the v eri er accepts on input probabilit w; f that ) +1) n ( n 2 most 2 is at =1 = 2. Details are b elo w. 14

15 Theorem 4.4 et b e an NP-r elation. Supp ose ther e exists a tr ap do or p ermutation gener ator. L p a non-inter active zer o-know le dge pr o of system with an ecient pr over. Then ossesses 0 0 0 Let I ) b e a trap do or p erm utation generator. Let A Pro ;B E ;M ; b e the mac hines, and m ( of: G; n sp b olynomial, Lemma 4.3 . Let l ( n )= m ( n ) n ( eci ed + 1). W e construct P; V ; S satisfying the p y of De nition 2.6 . conditions the is a string of length l ( n Notation: then w e think of it as partitioned in to n + 1 blo c ks, eac hof If ) m n ) n , and denote the i -th blo c kb y [ i ]( i =1 ;::: ;n + 1). length ( 0 h ema loss of generalit y , that there is a p olynomial t suc assume, that B y ( w; ; ;p )=1 W without l ( n ) = t ( j w j ). Let L = L , . W e sp ecify V . Let w 2 L and 2f 0 ; 1 g only if j p . On input w; j ;p 0 f p j6 = n +( n +1) t ( n ). Otherwise, it sets if hine to the rst n bits of p and p j to V rejects mac 0 0 sets p p [ i ]tothe i -th t ( n )-bit blo c kof the rest. ( i =1 ;::: ;n + 1). No w V accepts i for It further 0 0 i + 1 it is the case that B i ( w; [ =1 ] ;f ;::: ;p ;n [ i ]) = 1. h eac l ( n ) ecify P . Let w 2 L and W w 2 ( w ). Let n = j w j , and let 2 f 0 ; 1 g e no w sp . P runs G to n 0 0 pair ) 2 [ G (1 ( )]. It sets p f [ i ]= A obtain ( w; w; [ i ] ;f ; ; (random) a f ) for i =1 ;::: ;n +1, f 0 0 = p [1] ::: p [ n + 1]. Finally it sets p = f p :p and (\." denotes concatenation) and outputs p . sets The completeness condition (as required b y De nition 2.6 ) follo ws from the completeness condition of Lemma . 4.3 n k the soundness condition. Supp ose w 62 L . Let n = j w j and let f hec 2 f 0 ; 1 g w . Let e c Next n ) ( t ( n ) l W esa y that is f ; -bad if there exists an i 2f 1 ;::: ;n +1 g and a string q 2f 0 ; 1 g g 1 2f 0 . 0 implies ( w; [ i ] ;f that ;q )=1. The soundness condition of Lemma 4.3 B that suc h i h R n +1) ( n ( l ) 2 : f : is f 0 ; 1 g Pr -bad l ( n ) that a string 2f 0 ; 1 g No let us sa is bad if there exists an n -bit string f y suc h that is w It follo ws that -bad. f h i R ) l ( n n ( n +1) 1 is f Pr 0 2 bad ; 1 g = : 2 : 2 b implies soundness condition This required the y De nition 2.6 ). (as Finally , w e sp ecify the sim ulator. Let w 2 L and let n = j w j . On input w , the sim ulator S runs n n 0 G (random) pair ( f 1 ; on f to ) 2 [ G (1 obtain )]. F or i = 1 ;::: ;n +1 it runs M a on input 0 0 0 0 p get an output ( [ i ] ;p w; input i ]). It sets = [1] ::: [ n +1] and p f = f ; [1] ::: p to [ n + 1]. [ 0 p = f It :p sets and outputs ( then ). The zero-kno wledge (as required b y De nition 2.6 ) can ;p b e argued based on the zero-kno wledge condition of Lemma 4.3 . W e omit the details. In particular, pro of systems are constructible based on RSA. NIZK bining wing. 4.4 with the result of [NaY u ] yields the follo Com Theorem p 4.5 ose Corollary e exists a tr ap do or Supp ermutation gener ator. Then ther e exists an en- ther cryption scheme se cur e against chosen-ciphertext attack. of Similarly bining Theorem 4.4 with the result com [BeGo ] yields the follo wing. , Corollary 4.6 Supp ose ther e exists a tr ap do or p ermutation gener ator. Then ther e exists an im- plementation of the signatur e scheme of [BeGo]. 15

16 Ac kno ts wledgmen e thank anon ymous referee for commen ts that impro v ed the presen tation. W an Researc ork done while the rst author w as at the IBM T. J. W atson as h Cen ter, This w w wn Heigh ts, New Y ork. orkto Y References Bellare and S. Goldw asser. New Par adigms for Digital Signatur es and Message A u- [BeGo] M. Base Zer on Non-Inter active ation o-Know le dge Pr o ofs. Adv ances in Cryptology thentic d 89 G. ceedings , Lecture Notes in Computer Science V ol. 435, Crypto Brassard ed., { Pro 1989. erlag, Springer-V Bellare and S. Micali. How to Sign Given any [BeMi] r ap do or Permutation .JA CM, V ol. 39, M. T 1, Jan uary 1992, pp. 214-233. No. M. [BMO] S. Micali and R. Ostro vsky . The T rue Complexity of Statistic al Zer o- Bellare, le dge Pro ceedings of the 22nd Ann ual Symp osium on Theory of Computing ,A CM, Know . 1990. Unpr M. Blum, and M. Sh ub. A Simple Blum, e dictable Pseudo-R andom Numb er Gen- [BBS] L. ator . SIAM Journal on Computing, V ol. 15, No. 2, Ma y 1986, pp. 364-383. er M. Blum, A. De San tis, S. Micali, and G. P ersiano, Non-Inter active Zer o-Know le dge Pr o of [BDMP] , 20, Journal on Computing, V ol. Systems No. 6, Decem b er 1991,pp. 1084-1118. SIAM Zer M. [BFM] .F eldman, and S. Micali, Non-Inter active Blum, o-Know le dge Pr o of Systems and P Applic ations , Pro ceedings of the 20th Ann ual Symp osium on Theory of Computing ,A CM, 1988. [BC] Brassard and C. Cr ep eau. Non-tr ansitive T r ansfer of Con denc e: A p erfe ct Zer o- G. of le active pr oto c ol for SA T and Beyond . Pro ceedings Inter the 27th Symp osium know dge F oundations of Computer Science , IEEE, 1986. on u] A. De San tis and M. Y ung. Crypto gr aphic Applic ations of the Metapr o of and Many-pr [DeY over Systems Adv ances in Cryptology { Crypto 90 Pro ceedings , Lecture Notes in Computer . V V 537, A. J. Menezes and S. Science anstone ed., Springer-V erlag, 1990. ol. Non-Inter U. [FLS] D. Lapidot, and A. Shamir. Multiple F active Zer o-Know le dge b ase dona eige, Single R andom String . Pro ceedings of the 31st Symp osium on F oundations of Computer Science , 1990. IEEE, ofs O. S. Micali, and A. Wigderson. Pr o h, that Yield Nothing but their V alidity [GMW] Goldreic a and dolo gy of Crypto gr aphic Design .JA CM, V ol. 38, No. 1, July 1991, pp. 691{729. Metho [GoLe] O. Goldreic h and L. Levin. A Har d-Cor e Pr e dic ate for al l One-Way F unctions . Pro ceed- on ings 21st Ann ual Symp osium the Theory of Computing ,A CM, 1989. of [GMR] S. Goldw asser, S. Micali, and R. Riv est. A Digital Signatur e Scheme Se cur eA gainst A dap- V tive A ttacks . SIAM Journal on Computing, Chosen-Message ol. 17, No. 2, April 1988, pp. 281-308. 16

17 [NaY u] Naor and M. Y ung. Public Key Cryptosystems se cur e against chosen-ciphertext attacks . M. on ceedings the 22nd Ann ual Symp osium of Theory of Computing ,A CM, 1990. Pro [RSA] R. Riv est, A. Shamir, and L. Adleman. A Metho d for Obtaining Digital Signatur es and ol. Public-Key . Comm unications of the A CM, V Cryptosystems 21, No. 2, F ebruary 1978, pp. 120-26. 17

Cash transfers: what does the evidence say? A rigorous review of programme impact and of the role of design and implementation features Francesca Bastagli, Jessica Hagen-Zanker, Luke Harman, Valentina...

More info »Controller Tool Help No. LIT-1201 1147 Code 13.0 Release Software 2018 December Issued for the most up-to-date Exchange of this document. Refer to the Knowledge website version 21 Getting ... Started ...

More info »® Dialight LED High Bay Technical Specification Sheet - UL J U LY 2018

More info »bu lle ti n j pal policy bulletin | august 2017 - : g e t t i n g c h i l d r e n i n to r o l l s c h o o l c a l l - : photo iruarriz aga | j fr ancisca pal / ipa de ke y lessons : • Student partici...

More info »CLJ-DS26 REV 1 PRODUCT FAMILY DATA SHEET ® J Series™ 2835 High‑Efficacy LEDs Cree PRODUCT DESCRIPTION FEATURES • J Series™ LEDs extend Cree’s industry‑leading portfolio of Industry‑compatible size : 2...

More info »Main St. Marketplace Lot One Housing Project Application for Major Site Review, Conditional Use & Variance to Maximum Setback Submitted to: Town of Carbondale 511 Colorado Ave. Carbondale, CO 86123 Pr...

More info »Instruction Manual Instruction Manual 6th Edition, May 1999 6th Edition, May 1999 Expression Vector System Expression Vector System Baculovirus Baculovirus

More info »ResourceSmart Schools Curriculum Links Linking sustainability into the Victorian Curriculum

More info »BioEdit version 5.0.6 BioEdit version 5.0.6 . This is the current help file for Copyright ©1997-2001 Tom Hall North Carolina State University, Department of Microbiology This is likely to be the final...

More info »Catalog # : Project : Date : Prepared By : Mirada Post Top - MPH Outdoor LED Post Top The Mirada Post Top (MPH) interweaves modern urban aesthetics and exceptional performance. With superior distribut...

More info »Foreword by Malala Yousafzai With a foreword by Winthrop s Malala Yousafzai p E Student, Nobel Peace Prize Laureate, and Cofounder of the Malala Fund rlin in What Works G Hard-headed evidence demonstr...

More info »thesda Be Downtown Plan energy + ccess + a community habitat + water equity mobility materials identity health Staff Draft May 2015 MARYLAND-NATIONAL CAPITAL PARK AND PLANNING COMMISSION

More info »NARROW LED STRIP 75 CATALOG #: TYPE: LED P RO JE C T: NOTES: EXAMPLE L85 / 835 OPTIONS 4 DIM UNV 75 - - - - - IONS/ NOMI LU MEN CR I & OPT NAL DR IVER VOL TAGE RIES SE LEN GTH PA CKAGE CC T AC CESSORI...

More info »Univ ersit ennsy lv ani a L aw Sc hool y of P eposit aw: L ars hi p R hol ory Penn L egal Sc Faculty Scholarship 2018 Is Say on Pay All About Pay? The Impact of Firm Performance Jill E. Fisch y of P e...

More info »Lumark DESCRIPTION Type The Night Falcon™ high wattage LED floodlight luminaire combines Catalog # high-efficiency, precision engineered optics and energy efficiency in a cost-effective solution. Inco...

More info »Network and IT Guidance Technical Bulletin LIT-12011279 Building Technologies & Solutions www.johnsoncontrols.com Release 10.0 2019-05-03

More info »