WIXLIB

Intuitively, a protocol is zero-knowledge if for anydynamic adversary A acting on it, there is a PPTAwhich could output strings indistinguishable from thoseoutput by A. If all processors have initially blank tapes,then all protocols are zero-knowledge by this definition,since one can construct a PPTA simulating the entirenetwork, including the adversary. Zero-knowledgebecomes meaningful when we allow processors to startwith private auxiliary inputs which are not easily computable functions of the common input. For example,assuming NP is not contained in BPP, one processormay start with a satisfying assignment of a SA T formula, where the formula is given as input to the network.We define zero-knowledge for a non-interactiveprotocol P in which all processors except the leader startwith blank tapes. The leader, i, runs a PPTA Start oninput (k,n), where k is the security parameter and n isthe size of the network. The outputs of Start are thecommon input to P, x, and an auxiliary input for i. Weassume that A may not corrupt i. Let A output stringsaccording to probability distribution Us when P is initiated on input x.Definition: A non-interactive protocol P is t-zeroknowledge if for every dynamic t- adversary A, thereexists a PPTA A' which takes as input xEL and outputsstrings according to Vs such that the families of probability distributions {Us} and {Vs } are indistinguishable.3.VeriflaNeS retSharingWe begin by describing ordinary secret sharing in aframework which generalizes naturally to VSS.3.1. Ordinary Secret SharingOrdinary secret sharing enables a dealer to splitinformation among a network so that a quorum of processors is needed to recover the information. An(n, t, 11,) secret sharing is a pair of PPTAs(Share( ·,.),Recover( . )); Recover takes 11, 1 inputsand is deterministic. The first input of both Share andRecover is xEL for some language L. We callMESs D omain( Share (x,.»themessagespace;IMESs 1 1. ClPHs Range(Share(x,» is the cyphertext space. We consider a particular xEL and omit theargument x. The input of Share is a secret wE MES H. Each di is called a piece, or share,of w. The input of Recover is a u-tuple of ordered pairs«al,cl),···,(au'cuwhere ai E [l,n], ciECYPH, andthe ai are distinct. The output is an element of MES.When the input to Recover is any labelled subset of upieces output by Share on input wEMES, Recover outputs w. Formally,»'Finally, we require that w be hard to compute givenonly t pieces output by Share; no static adversaryshould be able to guess w significantly better than randomly given t labelled pieces.Definition: We say (Share ( ·,.),R ecover( . )) is an(n, t,u) secret sharing if for a language L ,1. V xEL V wEMESs ,( dl, .,dn).-Share( x ,w) V {a 1" ' au}C [I,n 1, Recover( x ,( a I' da1 ) , ,( au, da.)) w.2. V PPTAs A( .), Guess( . ), V c 0,3 k o, Ix l2::k o9Pr[ w Guess(x,(al,da ), ,( at,da,)): (al, . ,at).-A(x);w.-MESs ;( d1,. .,dn).-Share(x,w)] 1/ IMESz 1 Ix 1- c.Later, we shall strengthen property 2, by allowing adynamic adversary to choose which pieces of the secretto take as input.Shamir [S) presents an (n,t,t I) secret sharing forany threshhold t. Let L be the set of prime numbersgreater than n. For pEL, we define Share Share(p,.)as follows. The domain is MES Zp. Protocol Share,on input wEMES, sets yo w and lets (Yl' .'Yt)'-Zp't.Let Q( 8) be the polynomial L; Yis·. Then the output ofi OShare is Q(1),Q(2), . ,Q(n) mod p. Recover is polynomial interpolation, which is used to find Q(O) w.Informally, we argue that t pieces are no help in recovering w. Given the value of Q at any t points, then thevalue at 0, namely Yo w, uniquely specifies a polynomial Q. Since all other coefficients were chosen uniformly, the chance that a particular polynomial waspicked is directly proportional to the probability that itsconstant term was the secret chosen. Therefore, seeing tpieces gives no additional information.An (n, t, u) secret sharing (Share ,R ecover) suggestsa non-interactive protocol in which the leader, or dealer,can "split" a secret among n players in such a way thatonly a quorum of 11 can recover the secret. Namely, thedealer broadcasts x and sends piece di to player i viaprivate channel. When 'U players wish to recover thesecret, each broadcasts his labeled piece, and Recovercan be run to return the secret.Can this protocol be used if t players may befaulty? No! It is true that no set of t faulty players canrecover the secret themselves. However, even if'U n- t, in which case there are enough good players torecover the secret, bad players may interfere. Forexample, a bad player i may broadcast a spurious valuein place of die Good players cannot distinguish goodpieces from spurious pieces. If t O( n), then a randomu-tuple consists entirely of good players with exponentially small probability.{61'.,4,. ). SAare( w) V {cz--t-t.nt,a u }ell,n J, (2.1)-&COt1er{ 61 ,441-h ·'-{ .4 fI ,-aa;,)1 w.429Authorized licensed use limited to: University of Maryland College Park. Downloaded on February 23,2010 at 17:12:39 EST from IEEE Xplore. Restrictions apply.

Indeed, the dealer can prevent this problem byauthenticating the pieces. In this way, good playerscould recognize which pieces truly came from thedealer. However, a more endemic problem is the following: what happens if the dealer is faulty? The goodplayers themselves might get authenticated yet spuriouspieces, and they will not be able to recover the secret.Depending on the behavior of Recover on "invalid"inputs, the good players may not be aware that differentsets of pieces would return different secrets. The secretreturned could depend on which bad players chose tobroadcast their authenticated, spurious pieces. The bestkind of secret sharing would allow any player to verifyduring Share whether or not his piece is valid; moreover, he should be able to check during Recoverwhether or not the piece another player broadcast isvalid.3.2 Verifiable Secret SharingInformally, a verifiable secret sharing protocol mustmeet the following two requirements:1. Verifiablility constraint: upon receiving a share of thesecret, a player must be able to test whether or not it isa valid piece. If a piece is valid, there exists a uniquesecret which will be output by Recover when it is run onany 11 distinct valid pieces.2. Unpredictability: there is no polynomial-time strategyfor picking t pieces of the secret, such that they can beused to predict the secret with any perceivable advantage.This framework allows for an interactive protocolproving validity of the pieces. A VSS protocol is noninteractive if there is a polynomial-time algorithm Checkwhich tests validity of the pieces. Obviously, the samepieces are not valid for different secrets; we introduce aPPTA Encrypt to handle this.Informal Definition: An (n, t, u) non-interactive verifiableisaquadrupleofPPTAssecretsharing(Share ,Recover, Check ,Encrypt) such that1. (Share ,Recover) is an (n, t,u) secret sharing over alanguage L.2. YxEL,VwEMESz,YI .j .n, Y Encrypt(x,w);(d1,···,dft) -Share(x,w)::; , Checlc( x. Y,.t',d.,. ) 1. ·3. VxEL ,V YERange(Encrypt(x,)), 3 wEMESz · ::;-·V {at, .,au }C[I,n],V d1, . ,du EMESz ,(Check(x, Y,ai,d i ) 1 Vl i u) Recover( x,( a 1,d 1), .,( au, du )) w.Remark: Actually, we require that (Share,Recover)remains an (n, t, u) secret sharing even whenY Encrypt(x,w) is given; Share itself may take Y asan input. To formalize the definition, Share itself wouldset Y -Encrypt(x,w) and append Y to each piece.3.3 Applications of Verifiable Secret SharingVerifiable secret sharing enables a communicationnetwork to simulate a simultaneous broadcast network.Informally, every processor is required to share hisround r message before any round r message isrevealed. This trivializes the design of protocols such assecret bidding, leader election, and flipping a fair coin.In the simulation of a simulataneous broadcast network, each processor acts as dealer. For an interactiveVSS such as [GMW] , Chor and Rabin [CR] show thatlogn rounds are sufficient for n processors to prove thevalidity of their pieces; it is not known whether this canbe done in a constant number of rounds. In a noninteractive VSS, all processors may deal secrets in parallel; therefore, our protocol gives constant round solutions to all these problems.Another application is achieving a fast ByzantineAgreement without any preprocessing. The best previously known algorithm which could tolerate a linearnumber of faulty processors, due to Chor and Coan[Ce] ,[C], required expected O( n /logn) rounds. Feldman and MicaIi [FM] show that running non-interactiveverifiable secret sharing without broadcast channels,using Crusader Agreement instead, yields a constantexpected time Byzantine Agreement protocol.Even beyond the protocols which directly followtrom it, verifiable secret sharing now plays a central rolein cryptographic protocol design in a most dramatic way.In [GMW] it is shown that all protocols can be designedto resist t faulty players out of 2t l. Verifiable secretsharing is one of the three main blocks needed for theirsimulation. This highlights even more the need for anefficient verifiable secret sharing, as it may enter as akey subroutine in a large class of protocols.4. Motivation for Our SolutionThe motivation behind our solution is to utilizehomomorphic relationships which may exist betweenvalues and their encryptions. For a certain class ofencryption schemes, which we shall call homomorphic,we can construct an algorithm Check which enables aplayer to verify the validity of his piece.4.1. Probabilistic EncryptionA problem with deterministic encryption schemes isthat it is easy to check whether or not a given ciphertextis the encryption of any given message. Goldwasser andMicali [GM] showed how to overcome this problem byprobabilistic encryption. They define the notion of afamilyofunapproximablepredicates.LetH {Hardz : xEL} be a family of predicates, each Hardzmaps CYPHz -- {O,1}. Elements which map to 0 (1) areconsidered encryptions of 0 (1). Intuitively, such an430Authorized licensed use limited to: University of Maryland College Park. Downloaded on February 23,2010 at 17:12:39 EST from IEEE Xplore. Restrictions apply.

encryption is secure if there is no efficient way of computing Hardz on random elements; H is unapproximableif no poly-size family of circuits can compute H ardz ( y)significantly better than randomly guessing when x and'Yare randomly selected.Let C {Ok: k E Z} be a poly-size family of circuits,C/c{·") takes as inputxEL/c and yEOYPHz and outputsa bit. For xEL k , letP{ C,k ,x ) Pr[ Ok (x ,y ) Hardz ( y): y -CYPH z ].Definition: The predicate H is unapproximable ifVC {Ck : kEZ},V c 0, 3 k o·5·k k09Pr[P(C,k,x».5 k- c : x -L/c] k- c,4.2 Homomorphic Encryption FunctionsOften, a rich alga braic structure underlies anencryption scheme. Relations among cleartext valuesmay imply relations among the encryptions. For exampIe, in RSA encryption, Encrypt( yz) ( yz) e modm Encrypt(y)Encrypt(z). More generally, when boththe domain and range of Encrypt are groups, Encryptmay be a homomorphism of the groups. Benaloh [Be]utilized such homomorphisms in his secret sharing, andpointed out that our VSS extends to such a class ofencryption functions [Be2]. LetMES Domain(Encrypt) be an additive group, andCYPH Range( Encrypt) be a multiplicative group. Thekey property is that for all B,CEMES,(4.1)To probabilistically encrypt a bi·t using HardEH, theremust be a way for the encrypter to find "random" elements which map to 0 (or 1). One possibility is if Hardis a trapdoor function, that is, II ard is easy to computegiven a short string Hint. In this scenario, the encryptergenerates a pair x,Hintz ; he can then compute Hardz onrandom elements of CYPHz , and picks one which mapsto the desired bit.Another method exists if Hard is an easy predicatecomposed with a one-way function, as we now explain.Let MES be a message space, and let Encrypt be aninjection from MES -- CYPH. Informally, Encrypt isone-way if Encrypt is easy to cOJnpute, but Encrypt- 1 ishard to compute. Let Predicat,e: MES-- {O,I} be aneasilycomputablefunction.SupposeHard Predicate(Encrypt- 1 ). Then the encrypter canrandomly pick yE CYPH, and c:ompute z Encrypt( y)and b Predicate(y). By construction, Hard(z) b,hence z is a probabilistic encryption of b. All encryptions we shall consider will be c:omputed by this lattermethod, even though some are also trapdoor schemes.Example: RSA probabilistic en( ryption, developed byRivest, Shamir, and Adleman [R.SA] may be computedeither way. Let m be a product of large primes, and e anumber such that (e, !J(m)) I. Let d e- 1 modt,b(m); d, which is not easy to cOlnpute without knowingthe factorization of m, is the trapdoor hint. We defineCYPH Z:n. For yEZ:n, we define Hard{y) to be theparity of yd mod m. This is easy to compute for anyoneknowing d, but it is believed to be hard to compute otherwise. We shall focus on the mt thod of encrypting bitswithout knowing d. Let Encrypt(y) ye mod m andPredicate ( y) be the parity of y; both are easy to compute. A 0 (1) is encrypted by raising a random even(odd) element of Z:n to the e po,ver mod m.We shall find it convenien't to generalize this notionby enlarging the range of Predica te, and hence Hard, to[1,1]; the value of 1 is a paranleter of the particularencryption function.Encrypt(B C) Encrypt(B)·Encrypt( C)(4.2)ForcEZ,wedefinethescalarproductc·B B B . B with c summands. Induction may beused to show that V BEMES, V cEZ,Encrypt ( c' B) (Encrypt( B)) C Security can only be achieved by picking among afamily of encryption functions. Let Generator ( ',') be aPPTA which, on input k,n, selects x -(Lkn L n ) forsome language L; we define L n cL below. We imposeuniformity constraints by requiring a PPTA Encrypt( ,,.)such that Encrypt(x,.) Encryptz (·)' and similarly forPredicate(·,,). Likewise, there must be uniform algorithms for computing the group operations, uniformlysampling MES, and the following function Divide,whose purpose will first become clear in Section 5.3. Forall BEMESz , Divide(x,n,n!·B) Predicate(x,B). Sincescalar multiplication by n! need not be a 1-1 function,the existence of Divide imposes a certain structure onPredicate. Moreover, this says that Predicatez{B) iseasily computable given only n!'B as input. We defineMES: {BEMESz : Predicate (B) s }.WedefineL n {xEL: (Divide(x,n,.) is well defined) and( IRange( Predicate (x,') I n) }.Ifthesepropertiesaresatisfied,andHard Predicate(Encrypt- 1 ) is unapproximable, we sayGenerator is a homomorphic probabilistic encrypt 'on schemegenerator. Equation (4.1) implies that NP is not contained in BPP, so we will need to make certain unproven complexity assumptions to assert that we have suchgenerators.In Section 8, we construct homomorphic probabilistic encryption scheme generators based on differentproblems. One is based on the difficulty of takingdiscrete logs in a finite field; a suitable restriction of thedomain is required. The same method lets us base agenerator on the difficulty of taking discrete logs on aelliptic curves. Benaloh [Be2] has pointed out that agenerator may be based on the difficulty of distinguishing r-th powers in Z , where r is a prime dividing4 ( m); the nature of these probabilistic ncryptionsdiffers slightly from the description given here. RSA is431Authorized licensed use limited to: University of Maryland College Park. Downloaded on February 23,2010 at 17:12:39 EST from IEEE Xplore. Restrictions apply.

sufficiently homomorphic for our purposes if we definethe "addition" on the domain MES Z:n to be multiplication mod m.Q( h). Player J IS not convinced that the dealerencrypted a real perm utation, but he knows that theh-th piece is designated exclusively for him, since onlyA h can encrypt to Encrgpt( A h ) and Predicate (A h) i.To facilitate the simulation, this step will precede thebroadcast or the encrypted variables.With respect to a static adversary, the simulationmay be done without permuting the shares. We arguewithout proof, in Section Q.2, that the shares need notbe permuted even against a dynamic adversary,although there are problems with the simulation in thatcase.4.3. Using a Homomorphic Probabilistic EncryptionScheme to Produce a Non-interactive (n,t,t l) VSSWe restrict the rest of this chapter to an informaldiscussion of our protocol. The formal presentation isgiven in Section 5.Given Encrypt, we show how to share a secret in[1,l]; a longer secret may be shared by sharing blocks ofIl bit secrets in parallel. We convert Shamir's secretsharing into a non-interactive VSS 9S follows. The dealeruniformly picks a secret 8- -[I,l), and YoEMES 8 andsets Yo to be the constant term of a degree t polynomialQ. He chooses the t other coefficients of Q uniformlyin MES. He then broadcasts encryptions of thecoefficients of Q, Encrypt( Yo), ,Encrypt( Yt). As inShamir's scheme, he sends Q(i) to player i via aprivate channel. The point is that i can verify his pieceby checking thatEncrypt( Q(i)) 5. Our Protocol5.1 InitializationLet Generator be a homomorphic probabilisticencryption scheme generator. The dealer i setsx -Generator(k,n), where k is the security parameter,and n is the size of the network. We omit the depenonx.LetMES Domain(Encrypt) ,denceCYPH Range( Encrypt J.The dealer i uniformly picks a secret 8 -[ l,l], setsyo -MES', and computes Y Encrypt(yo). The VSS isinitialized with common input i,x, Y. All players storei,x, Y on a work tape; i additionally stores Yo as hisauxiliary input.(4.3)(Encrypt( Yo))·( Encrypt( YI)) j . ( Encrypt(Yt)) j'Even for probabilistic encryption schemes, we muststill prove that broadcasting the encryptions does notallow an adversary to guess the secret advantageously.This is done by showing that the adversary can simulatehis view by himself. To facilitate the simulation, wealter the protocol slightly by having the dealer encrypt acertain multiple of the coefficients, as will be describedbelow.5.2. TIle Protocol ShareThe dealer broadcasts messages in steps 1 and 3;the players perform calculations in steps 2 and 4.1. The dealer i selects 1r -Sn, a uniformly chosen permutation of [1,n]. He sets A j -MES 1f (j) for each i andbroadcasts the probabilistic encryption this specifies,Encrypt(A1), .,Encrgpt(An ). He sends h,Ah on theprivate channel to i, where h 1r- I(i).2. Each player i lets A (Encrypt(AI), .,Encrypt(An ))denote the values he received on i's broadcast channeland h and C denote the values he received on theprivate channel from i in round 1. We defineCheckid(i,h,C,A) l iff Encrypt(C) Encrypt(Ah ) andPredicate ( C) i.When this .is the case, i stores h butnot C Ah ; if this fails, i immediately rejects the dealeras faulty.4.4 Tolerating a Dynamic AdversaryIt would seem that a non-interactive VSS could notbe zero-knowledge with respect to a dynamic adversary.On the one hand, by the intractability assumption, asim ulator cannot reconstruct the secret. On the otherhand, we wish that he can sim ulate the output of anadversary, who could corrupt any t players and outputvalid pieces with those indices. How,ever, if the sim ulator knew all the pieces, he could compute the secret,The resolution of this difficulty is to perm ute the sharesin a way unknown to the adversary; the adversary doesnot know which share a player should have before corrupting him. In this way, a simulator knowing t sharescan "fool" an adversary into thinking that these are thecorrect shares for the players corrupted. Of course, thisleaves the problem of how to convince a player that heis receiving the proper share.This latter problem is solved by having the dealerprobabilistically ,encrypt a random perm utation 1r E Sn.The dealer lets (AI- -MES (I)),. ,(An -MEs (n)) andbroadcasts Encrypt( AI)' . ,Encrypt(An).The dealersends A h on theprlvate hannel to player i, wh-ereh 7r-l(j); i eanverify that Prdi06te{Ah ) i. isd signatestha;t playerj -shouid subsequently r -eeive3. The dealer sets (Yl,. .,Yt) -MES. He computes andbroadcasts( Y I,···, yt) (Encrypt( n! ·YI) , . ,Encrypt( n! ·Yt)).LetQ: Z- MfSdenote the "polynomial" function,Q(a) Ea'·y,. The dealer privately sends Mh Q(h)1 0to player i 1r(h).432Authorized licensed use limited to: University of Maryland College Park. Downloaded on February 23,2010 at 17:12:39 EST from IEEE Xplore. Restrictions apply.

4. Each player i computes Y o yn!. LetY ( Yo, Y1 , , Yt ) denote Yo and the values broadcastlast round; let Nh be the ValUE! i just received on theprivate channel. Define Check (Y,Nh,h) 1 iffEncrypt(n!·Nh ) ( Yo)·( Y ).( lth'). When this is true, jstores h ,Nh ; otherwise, he rejects the dealer as faulty.Remark: As we mentioned in Section 4.2, scalar m ultiplication by n! need not be 1-1. Therefore, coefficient114 is not uniquely determined by the encr

faulty systems. As verifiable secret sharing is a bottleneck for so many results , it is essential to find efficient solutions. 1. Introduction 1.1 TIle Problem Informally, verifiable secret sharing is a protocol in which a distinguished processor" or dealer, selects and encrypts a "secret message", s, and gives a "share" of s to each of n .