1Secret SharingCS395T Design and Implementation ofTrusted ServicesAnkur GuptaOverview of the Talk Hugo Krawczyk. Secret Sharing MadeShort, 1993. Josh Cohen Benaloh. Secret SharingHomomorphisms: Keeping Shares of ASecret Secret, 1987. Josh Cohen Benaloh and Jerry Leichter.Generalized Secret Sharing andMonotone Functions, 1990.Secret Sharing Made ShortHugo Krawczyk 1993 Motivation: Shamir’s (n, m) thresholdscheme requires that each secret share beas long as the secret to be shared. Therefore, for a secret S of length r, totallength of share is rn. We present an optimal scheme thatrequires each secret share to be only r/m+ a constant (independent of r, n) in size.Perfect Secrecy Perfect Secrecy1) In Shamir’s (n, m) threshold scheme, noinformation about the secret is revealed inthe information theoretic sense. If S0 is thesecret, for every k < m, let S1, …, Sk be any kshares thenPr(S0 | S1, …, Sk) = Pr(S0) 2) No bounds on the computation power ofadversary are assumed.2Computational Secrecy Computational Secrecy:a) Adversary is resource bounded.b) No information is revealed using only polynomialresources.Polynomial Indistinguishability: Two probabilitydistributions are polynomial time indistinguishable ifany probabilistic polynomial time algorithm behavesessentially the same when its input is selected fromeither of the two distributions.Computation Secrecy: Formaldefinition An (n, m) threshold scheme iscomputationally secure if for any twosecrets S’ and S’’, for any k < m, thedistributions on shares D(S’; S’1, …, S’k)and D(S’’; S’’1, …, S’’k) introduced bythe scheme are polynomiallyindistinguishable.Ingredients of the Scheme (n, m) Information Dispersal Scheme (IDS)introduced by Rabin. A piece of information(say a file F) is divided into n shares andtransmitted over an unreliable channel. Anym shares suffice to reconstruct the file F. Sizeof each share is |F|/m. Secure private key encryption (ENC) Perfect (n, m) Secret Sharing Scheme (PSS)like Shamir’s threshold scheme.Distribution Scheme1) Choose a random encryption key K.Let E=ENCK(S) where S=secret2) Using IDS partition E into n fragmentsE1, E2, …, En.3) Using PSS generate n shares of thekey K: K1, K2, …, Kn.4) Send to participant Pi, the share (Ei, Ki)privately.3Reconstruction Scheme1) Collect from any m participants Pj,1<=j<=m, their shares Sj=(Ej, Kj).2) Using IDS, reconstruct E from Ejs.3) Using PSS reconstruct K from Kjs.4) Decrypt E using K to recover thesecret S.Analysis Length of each share Si=(|S|/m, |K|). Correctness (Sketch): a) m-1 Ejs reveal no more informationabout S than E itself (by security ofENC). b) m-1 shares reveal absolutely noinformation about the encryption key K(by security of PSS).Robust Secret Sharing How to ensure recovery of secret inpresence of malicious participants? Solution: Let the dealer digitally sign allthe shares. Now a participant can’t cheat!Secret SharingHomomorphisms: Josh Benaloh 1987 Motivation:1) Alice distributes a secret A to n agentsusing an (n, m) scheme.2) Bob distributes secret B to the same nagents using an (n, m) scheme.3) How can any m of the n agentsdetermine A + B while revealing aslittle about A and B as possible.4Homomorphism Property Let F: Tm -> S be a (n, m) threshold scheme.If Di1, Di2, …, Dim be any m shares then thesecret D is D=F(Di1, Di2, …, Dim ) (n, m) is (+, *) homomorphic, if D=F(Di1, Di2, …, Dim ) D’=F(D’i1, D’i2, …, D’im ) then D+D’=F(Di1*D’i1, …, Dim * D’im)(+, *) Composite Scheme Is an (n, m) scheme which divides a set of ssecrets d1, …, ds into subshares di,j 1<= i<= n, 1<= j <= s, such that1) The super-secret D=d1+d2+…+ds is easilycomputable from the super-sharesDi=di,1*…*di,s2) Pr(dj=xj | D=X) = Pr(dj=xj | D=X, 1<=i<=n,Di=Xi, for all i’ in I’, 1<=j<=s, di’,j=xi’,j) for every I’, |I’| <m i.e. knowing all super-shares, super-secret and at most m-1 sub-shares of each sub-secret reveals noinformation about every sub-shareHomomorphism andCompositeness Theorem: If |S|=|T| are finite then every (+, *) homomorphic threshold scheme is a (+, *) composite threshold scheme. Proof (sketch): Assume s=2 I.e. there areonly two sub secrets A and B. Let S=A+B.Further let k=m-1 conspire together so thata1,…, ak and b1,…, bk are known. Therefores1,…, sk (where si=ai+bi) are also known. AsS is known, and since |S|=|T| (and finite),therefore Fm-1:T->S is 1-1 and hence sk+1, …,sn can be computed. Thus knowing thembeforehand gives no additional information.Examples Shamir’s scheme is (+, +) homomorphic butnot (x, x) or (x, +). A variation of Shamir scheme is (x, +)homomorphic (secret=ga, a is divided into nsubshares using the Shamir scheme). By above theorem they are also compositeschemes. Hence composition of sub-secretscan be obtained without revealing the sub-secrets.5Applications Verifiable Secret Sharing Will use (+,x) homomorphism property ofan encryption scheme and (+,+)composite scheme. Secret Ballot Election Will use a (+,+) composite scheme.Encryption Scheme Verifiable secret sharing scheme will use thefollowing encryption scheme: Let r > |S| be prime, p and q also prime s.t. rdivides p-1 but not q-1. N=pq. Let y be suchthat gcd(N, y) =1 and y is NOT the rth residuemod N (I.e. y ≠ ar mod N, for any a). (N, y)are made public. To encrypt a secret s,choose a random x (relatively prime to N)and let E(s,x,y,N)=ysxr mod N. Knowing p and q, s can be easily determined. E is (+, x) homomorphic.Verifiable Secret Sharing Objective: Dealer should be able to prove theparticipants that he made a consistent dealI.e. from every k sub-shares we get the samesecret s, without revealing the secret s. This is useful in voting schemes where avoter needs to prove that he cast a validvote. We assume Shamir’s scheme as the secretsharing scheme (and hence a (+,+)composite scheme).Solution: Interactive Proof Interactive Proof (Probabilistic) Dealer will convince the participantsthat he made a consistent deal withhigh probability. For Shamir’s scheme, this boils downfor dealer to convince the participantsthat he used at most d=m-1 degreepolynomial P.6Algorithm1. Encryptions of the values of the points thatdescribe P are released by dealer.2. Similar encryptions of 100 more randompolynomials of degree at most d are released to theverifiers.3. A random
View Full Document
Unlocking...