More Fun with Secret SharingBrandon Hall 1Overview? Threshold cryptosystems• [DF89] Y. Desmedt and Y. Frankel. ``Threshold cryptosystems''. Advancesin Cryptology --- Crypto '89.? Proactive secret sharing• [HJKY95] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. ``Proactivesecret sharing, or: How to cope with perpetual leakage.'' Advances inCryptology --- Crypto '95.? Verifiable secret sharing• [Fel87] P. Feldman. ``A practical scheme for non-interactive verifiablesecret sharing.'' Proceedings of the 28th Annual Symposium on theFoundations of Computer Science:427--437. IEEE, October 12--14, 1987.2Secret sharing (review)[Sha79] How to share a se cret D:? Create polynomial of degree k − 1:f(x) = c0+ c1x + · · · + ck−1xk−1Assign c0= D and choose the other ci’s randomly.? Calculate f(1), f(2), . . . , f(n)? Distribute these f(x) “shares” to participants (along with the3corresponding x values)? To reconstruct secret, gather shares from k participants andinterpolate polynomialcorresponding x values)? To reconstruct secret, gather shares from k participants andinterpolate polynomialThis is called a (k, n)-threshold scheme.4Secret sharing: practical usage?Public key cryptography? Want to be able to decipher incoming messages, sign outgoingmessages for an entire organization? Don’t want to distribute single private key to everybody—badfor security? Having private key compromised is more costly than havingsymmetric key compromised? Shamir’s secret sharing sounds tempting5Secret sharing: security?A (k, n)-threshold scheme is “(k−1)-fault tolerant”, right?f(3)f(2)f(1)f(4)f(5)Secret sharing: security?A (k, n)-threshold scheme is “(k−1)-fault tolerant”, right?f(3)f(2)f(1)f(4)f(5)DSecret sharing: security?A (k, n)-threshold scheme is “(k−1)-fault tolerant”, right?f(3)f(2)f(1)f(4)f(5)DSecret sharing: security?A (k, n)-threshold scheme is “(k−1)-fault tolerant”, right?f(3)f(2)f(1)f(4)f(5)DD6Secret sharing: security?Straightforward application of Shamir’s scheme does notprovide much secrecy for distributed systems? Without secret sharing, secret is always e xtant—attacker maycompromise designated node at any time? With secret sharing, secret is available intermittently—attackerhas to compromise designated node at just the right time? Attacker can possibly trick shareholders into initiating areconstruction round7Threshold cryptosystemsWe have an idea![DF89] Y. Desmedt and Y. Frankel. “Thresholdcryptosystems”. Advances in Cryptology — Crypto ’89.8Threshold cryptosystems“Threshold cryptosystem” (also called society-orientedcryptosystem)? Pe rforms cryptographic operations without reconstructing privateke y? Not a generalized scheme like secret sharing—depends on thedetails of the underlying cryptosystem9ElGamal public key cryptography[ElG85] T. ElGamal. “A public key cryptosystem and asignature scheme based on discrete logarithms.” IEEETrans. Info. Theory IT 31, 1985.Components:? a large prime p? a generator g for the field Zp• a generator is a number such that (0, 1, g, g2, . . . , gp−2) isa permutation of the elements in Zp.• For a given prime field Zp, it turns out there are φ(p − 1)generators and they are not too hard to find.10ElGamal public key cryptographyComponents (cont’d):? a secret key a, 0 < a < p − 1All calculations performed in ZpPublish (p, g, ga)Keep a private11ElGamal public key cryptographyTo encrypt a message M :? Sender chooses random integer b? Raises g and gato the bthpower(use successive squaring)? Sends the tuple (gb, Mgab)To decrypt:? Receiver uses gband a to calculate (gab)−1? Multiplies by second entry to yield M12ElGamal public key cryptographyHow to crack ElGamal? If an eavesdropper could determine b from g and gb, or determinea from g and ga, the message could be decrypted.? This is known as the discrete logarithm problem.? No polynomial-time solution is known.? ElGamal is believed to be secure in general.13ElGamal threshold decryptionTo extend E lGamal with secret sharing techniques:? Generate polynomial for secret key a? Distribute (xi, yi) shares as normal and destroy polynomial? When an encrypted message arrives, select k participants? Each participant generates a modified shadow and computes apartial result on the message with this shadow? Designated node collects all partial results and uses them todecrypt message? Partial results reveal no more about the key than does ga14Lagrange Interpolating PolynomialsGiven k shares (x1, y1), . . . , (xk, yk), letπi(x) =kYj=1,j6=ix − xjxi− xjf(x) =kXi=1yiπi(x)Lagrange Interpolating PolynomialsGiven k shares (x1, y1), . . . , (xk, yk), letπi(x) =kYj=1,j6=ix − xjxi− xjf(x) =kXi=1yiπi(x)Claim: f(x) is our original polynomial15Lagrange Interpolating PolynomialsA simple c ase (k = 3):f(x) = y1(x − x2)(x − x3)(x1− x2)(x1− x3)+ y2(x − x1)(x − x3)(x2− x1)(x2− x3)+y3(x − x1)(x − x2)(x3− x1)(x3− x2)Note for all i, f(xi) = yi.16Lagrange Interpolating PolynomialsModified shadow for shareholder i isai= yiπi(0)? Only requires knowledge of one’s own share and the other xiinvolved in this sharing round? Observea1+ a2+ · · · + ak= f(0) = a17ElGamal threshold decryptionEach shareholder computes partial result (gbai)−1and sendsto designated nodeDesignated node multiplies all partial results to dec ryptmessage:Mgba(gba1)−1· · · (gbak)−1= Mgba(gb(a1+···+ak))−1= Mgba(gba)−1= M18ElGamal threshold decryptionEnhancement to m ake this less interactive:? Each node computes partial result gbyi? Designated node exponentiates each partial result by πi(0) beforemultiplyingAlso provide solution using geometry-based secret sharingDrawbacks:? Cannot prevent k shareholders from colluding with each other toreconstruct the secret key a19Later developments? Threshold signature scheme for RSA• [FD92] Y. Frankel and Y. Desmedt. ``Parallel reliable thresholdmultisignature.'' TR-92-04-02, Dept. of EE and CS, Univ. of Wisconsin.April 1992.? Threshold signature scheme for DSS• [GJKR96] R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin. ``RobustThreshold DSS Signatures.'' Advances in Cryptology --- Eurocrypt '96.? Improvem ent on RSA methods• [Rab98] T. Rabin. ``A Simplified Approach to Threshold and ProactiveRSA.'' Crypto '98.20Secret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret sharing: Part IISecret
View Full Document
Unlocking...