Secret Sharing Schemes Russ Martin May 14, 2012 Table of Contents What is Secret Sharing? Traditional Schemes Shamir’s Simplified Blakley’s Theory of More Efficient Schemes Short Share Secret Sharing Robust Secret Sharing What is Secret Sharing A method of distributing data between a group of persons so that any subset of a specified size can access the data, and a subset of size smaller can not. A (t,w) Threshold Scheme is a method of sharing a key K among w participants in such a way that any t participants can compute the value of K, but no group of t-1 participants can Definitions Perfect Secret Sharing Scheme (PSS) – A scheme in which t-1 shares provide absolutely no information on the hidden data Information Rate – Ratio of # of bits in the secret being hidden to the # of bits in the size of each share 1 is ideal, as the size of the shares are the size of the secret Must be less than or equal to 1 for any perfect secret sharing scheme Traditional Schemes – Shamir’s Based on polynomial interpolation – given t points on the plane, only one polynomial q(x) degree of t-1 exists that satisfies q(x) = y for all xi (the key given to each participant). K = the data being hidden by the scheme, in numeric form q(x) = a0 + a1x + … + ak-1xk-1, where K = a0 Shamir’s Scheme – Key Distribution To Distribute data: Choose w unique elements in Zp, where p>w. These are the x values. For i in 1 to w: Give xi to each of the participants. These x values are public Choose t-1 values in Zp randomly. These values are secret to the person distributing the shares. These are the a values. Privately give each member y = q(x) corresponding to their x value, where t 1 q( x) K a j 1 j j x mod p Shamir’s Scheme – Key Reconstruction Goal is to solve for the a values used during distribution, notably a0 = K With t participants, one can form t linear equations in the form: t 1 q ( xand ) taunknowns, a1 x ... aist 1axunique solution. 0 With t equations there Shamir’s Scheme - Example p = 19, t = 3, w =4, xi = i K = a0 = 12 Randomly Choose a1 = 14 , a2 = 3 q ( x ) 12 14 x 3 x mod 19 2 q(1) = 10, q(2) = 14 , q(3) = 5 , q(4) = 2 Shamir’s Scheme – Example (Solving) (1,2,3) • (1,2,4) 10 a 0 a1 a 2 10 a 0 a1 a 2 14 a 0 2 a1 4 a 2 14 a 0 2 a1 4 a 2 5 a 0 3 a1 9 a 2 2 a 0 4 a1 16 a 2 (1,3,4) 10 a 0 a1 a 2 5 a 0 3 a1 9 a 2 2 a 0 4 a1 16 a 2 • (2,3,4) 14 a 0 2 a1 4 a 2 5 a 0 3 a1 9 a 2 2 a 0 4 a1 16 a 2 • In all cases, Equations solve for 12, 14, and 3, the values chosen Shamir’s Scheme - Alternate Reconstruction Each participant computes a value of b for each possible subset of participants they could reconstruct the secret with. This can be done prior to reconstruction, as all x values are public xk b jare computed, mod p Once b values for reconstruction as xcanbexused 1 k t , k j k j such: t K b j 1 j y j mod p Shamir’s Scheme Size of all shares are the size of the hidden key (Information Rate = 1) For t-1 people, forms a line of possible answers – providing no information, making this a PSS If a person is “more important”, increase their ability by giving them multiple shares Recommended # of shares: w = 2t – 1 Allows recovery with loss/destruction of t-1 shares, but no reconstruction with same number Simplified Shamir’s Scheme Works only with a (t,t) threshold scheme Over any finite integer field Zm Randomly choose t-1 integers from i = 1 to t-1, denoted y1 … yt-1 t 1 yt K y i mod m i 1 yi = Shares given to participants Simplified Shamir’s Scheme Reconstruction: t K y i mod m i 1 With t-1 particpants, only can compute K-yi Still a PSS Traditional Schemes – Blakley’s t different (t-1)-dimensional hyperplanes will always intersect at exactly one point. t = 3, 2-dimensional planes in the form a1x1 + a2x2+ … atxt =b K = x1 Blakley’s Scheme - Distribution Choose a prime p and F = finite, t-1 dimensional field Select a secret, random point x, where x1=K, rest of values are random. All a values are also random and public Privately give each person yi = ai1x1 + ai2x2 + … aitxt Forms a w x t matrix, with Ax = y Blakley’s Scheme - Reconstruction Solve system of equations Ax = y, only with the t users that are combining shares. K = xi Blakley’s Scheme Not fully secure – all participants know the point exists on their plane Public share is much larger than K – t times in magnitude. n*t a values are needed. a values are not sensitive, may be public Information Rate is 1 More Efficient Schemes Note that for large secrets or number of participants, there is a large amount of data needed to be transferred Ideally, size of each share would be equal to size of the secret divided by the threshold Since Information Rate is now greater than 1, it can no longer be guaranteed to be a perfect secret sharing scheme Security can not be proved for any scheme with shares shorter than secret, as there will be some information revealed. Computationally Secure Secret Sharing Scheme Proposed by Hugo Krawczyk Computationally Secure – No Information can be efficiently computed from a single share Polynomial Indistinguishability – Two Probability Distributions that cannot be told apart through any polynomial-time algorithm Can be applied to encryptions – An encryption function is computationally secure if for any pair of messages M’ and M’’, their encryptions under all possible keys are polynomially indistinguishable Computationally Secure Secret Sharing Scheme Applied to a Secret Sharing Scheme Computationally Secure if for any pair of secrets of same length S’ and S’’, the distribution of their shares are polynomially indistinguishable Information Dispersal Algorithm (IDA) A split of a file F into n partitions, where m are needed to reconstruct the original file. Each partition size F/m, with a little redundancy attached Short Share Secret Sharing Distribution Encrypt the secret S using a random key in a polynomially indistinguishable algorithm Split the encrypted file into w fragments using IDA Encode the key using a PSS to create w shares of the key Give each participant one part of the key and one part of the encrypted file Reconstruction: Use IDA to reconstruct the file Use PSS to recover the key Decrypt the file using the key to uncover the secret Share Size ≈ Size(File) / t + Size(Key) Robust Secret Sharing A scheme that can recover the secret with up to m corrupted/malicious shares m < t and t ≤ w-m Same Distribution and Reconstruction of Short Share, but signed shares Sign file after encrypting, but before IDA Sign each of the shares Additional size of shares is not dependent on secret, only the signing system Downsides Requires a public key signature verification system Much more computationally complex Entity distributing the secret needs to be known Works Cited Stinson, Douglas R. Cryptography:Theory and Practice. CRC Press 2006. Shamir, Adi. How to Share a Secret. November 1979. Krawczyk, Hugo. Secret Sharing Made Short. 1993. RSA Laboratories. What are some secret sharing schemes? http://www.cs.bilkent.edu.tr/~selcuk/publications/BSS_I SC08.pdf Questions?