# cct

## Transcript

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 suces, 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 ecen 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 ecien 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 diculties. 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 suce 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 suces. 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 ecien 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 eciently 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 suciently 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 suces 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 ecien 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 ecient 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 ecien t pro v er pro implies existence (for an y NP-relation) of a man y-theorem NIZK pro of system (with an ecien 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 ecien 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 ecien 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 ecien 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 eciently 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 ) jj 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 ecient 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

### 10749

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...

### Controller Tool Help

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 ...

### Dialight led highbay techspecsheet UL

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

### roll call getting children into school

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...

### Cree Venture J Series 2835 High Efficacy LED Data Sheet

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...

### Main Street Marketplace Complete Application August 2018

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...

### Baculovirus Expression Vector System

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

### BioDoc.pdf

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...

### mph specsheet

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...

### PowerPoint Presentation

ITT Inc. Q1 2019 Results 05.03.2019

### What Works in Girls' Education: Evidence for the World's Best Investment

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...

### BDPStaffDraft 051415 FINAL sm

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

### 70430

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...

### Is Say on Pay All About Pay? The Impact of Firm Performance

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...

### Lumark NFFLD L Night Falcon Large

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...

User Manual

### Network and IT Guidance Technical Bulletin

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