Secret Sharing
(or, more accurately, “Secret Splitting”)
Original slides by Nisarg Raval
Material is adapted from CS513 lecture notes (Cornell)
http://www.cs.cornell.edu/courses/cs513/2000sp/SecretSharing.html
Why split a secret?
http://s3.amazonaws.com/rapgenius/1604757_1306648362304.08res_250_319.jpg
Goal
• Given a secret s first held by a “dealer” and then splits n
shares among n parties called “players”
a. All n players together recover s
b. Less than n players can not recover s
Naive Scheme
S1 = 100 S=10011 S2 = 11
High Order Low Order
• Concatenate shares to reveal secret
• S = (S1)(S2) = (100)(11) = 10011
• What is the problem? - Think of a salary or password
https://c2.staticflickr.com/8/7158/6761951167_54f2d69fb6_z.jpg
No Partial Disclosure
• Given a secret s and n players
a. All n players together recover s
b. Less than n can not recover any information about s
(unconditional security)
Dealer Generates Shares using XOR
S1 = Rand S=10011 S2 = S XOR S1
10100 00111
10011
S = S1 XOR S2
https://c2.staticflickr.com/8/7158/6761951167_54f2d69fb6_z.jpg
General Scheme
• Given a secret s and n players
a. Dealer generates n-1 random strings as first n-1
shares
b. Last share is the bitwise XOR of s with all the other
n-1 shares
General Scheme
• Given a secret s and n players
a. Dealer generates n-1 random strings as first n-1
shares
b. Last share is the bitwise XORing of s with all the
other n-1 shares
• Security Check
a. Can n players generate s?
General Scheme
• Given a secret s and n parties
a. Generate n-1 random strings as first n-1 shares
b. Last share is the bitwise XORing of s with all the other
n-1 shares
• Security Check
a. Can n players generate s?
b. Can any n-1 players generate s?
A More Flexible Scenario
S2 S1
S=10011
S2 S
S3
https://c2.staticflickr.com/8/7158/6761951167_54f2d69fb6_z.jpg
A More Flexible Scenario
S2 S1
S=10011
S2 ?
S3
• S can be constructed by 2 or more generals
• Less than 2 generals can not construct s
https://c2.staticflickr.com/8/7158/6761951167_54f2d69fb6_z.jpg
(n,t) Secret Sharing
• Given a secret s and n players
a. Any t or more players can recover s
b. Less than t players have no information about s
(3,2) secret sharing
S S1
2
S=10011
S2 S
S3
(n,2) Secret Sharing
(0,S)
x
secret S is y intercept
(n,2) Secret Sharing
(xn-1,yn-1) (xn,yn)
(x1,y1)
y (x2,y2)
(0,S)
x
(n,2) Secret Sharing
(xn-1,yn-1) (xn,yn)
(x1,y1)
y (x2,y2)
shares
(0,S)
x
(n,2) Secret Sharing
(xn-1,yn-1)
(x1,y1)
y
(0,S)
x
(n,2) Secret Sharing
one share does not suffice
(x1,y1) for every secret S, there is a line
through x1,y1
y
(0,S)
x
(n,3) Secret Sharing
(xn,yn)
(xn-1,yn-1)
(0,S) (x1,y1)
(x2,y2)
three points determine a quadratic polynomial
Shamir’s Secret Sharing
• It takes t points to define a polynomial of degree t-1
Easy to prove corollary of the Fundamental Theorem of Algebra, which states that a polynomial of
degree n > 0 has exactly n roots (when counted with multiplicity)
Suppose two distinct degree-(t-1) polynomials p1(x) and p2(x) both pass through the same set of t
points. Then p1(x)-p2(x) has t roots, which is absurd.
• Create a degree-(t-1) polynomial with secret as the constant coefficient and the
remaining coefficients chosen at random
• Find n points on the curve (not at x=0) and give one to each of the players.
• At least t points are required to fit the polynomial and hence to recover secret (and
any t points will suffice)
y = at-1 * xt-1 + at-2 * xt-2 + … + a1 * x + a0
Shamir, Adi (1979), "How to share a secret", Communications of the ACM
Use Case
S1
(3,2) S2
Secret Sharing
Scheme
S3
Private Key
Dyadic Security Product
• Pure-software virtual hardware security module (HSM).
• (Other vendors sell HSMs similar to TPMs that can store private keys and perform
TLS operations.)
• Share secret (e.g., private key for TLS) across multiple servers.
• Perform TLS operations using secure multiparty computation so that no server learns
private key.
• Assumes that it is more difficult to break into one server than several.
Unconditional Security
• Each share must be as long as the secret itself, e.g.,
number of possible values of polynomial at each point
where it is evaluated must be the same as number of
possible y-intercepts
• Require random bits of length proportional to the number
of players n as well as length of the secret l
• Can the sizes of the shares be reduced?
“Secret Sharing Made Short”
• Dealer begins by choosing a random symmetric key, e.g., a
256-bit AES key
• Dealer encrypts the secret using the symmetric key
• Symmetric key is split using Shamir’s (n,t) scheme
(n shares, each 256 bits): n*256 bits
• Encrypted secret is encoded using an (n,t) error correcting code
• Suppose encrypted secret length is l bits. Code uses n
“symbols” each l/t bits long: nl/t bits. Any t symbols out of n
suffice to recover the encrypted secret.
• Total bits: n*256 + nl/t (versus nl)
Idea Behind Error Correcting Code
• Use a polynomial as before.
• Break the “message” (e.g., the encrypted secret) into t pieces of length l/t.
Let yi denote the i’th piece.
• Create a polynomial f(x) where f(xi)=yi for some arbitrarily chosen x1, x2,
…, xt, e.g., xi=i.
• Now the goal is to recover not f(0), but f(x1), f(x2), …, f(xt)
• Evaluate the polynomial at n-t other locations xt+1,…,xn, e.g., xi=i.
• The n f(xi) values are the symbols
• Can recover the full polynomial from any t symbols
• Once the polynomial is recovered, find values at x1, …, xt.
Why is this scheme not
unconditionally secure?
It’s possible to learn some of the information about the
encrypted secret from fewer than t shares, e.g., knowing
f(x1) means knowing the first piece of the encrypted secret.
The error correcting code isn’t trying to hide information.
The goal is the opposite: enable the recovery of as much
information as possible from whatever symbols are at hand.
So the security depends on the strength of the encryption
system, e.g., AES, which is NOT unconditionally secure,
since key length (256 bits) may be less than secret length l.
Why isn’t AES Unconditionally Secure?
Suppose message length is l bits, and key length is k bits,
e.g., k=256, where k may be much less than l.
Given a ciphertext encrypted with a k-bit key, adversary can
narrow down plaintext to 2k possibilities out of 2l by
decrypting with all possible k-bit key values.
(Although this approach is not computationally efficient.)
Problem?
S1 compromised
S1
S2
S2 compromised
S3 S1 + S2 Secret
Time
Refresh Shares
Trusted
Third
Party
S’1 S’’1
S1
S’2 S’’2
S2
S’3 S’’3
S3
Time
Refresh Shares
Trusted
Third
Party
S’1 S’’1
S1 S1 compromised
S’2 S’’2
S2 S’2 compromised
S’3 S’’3 can not
S3
construct secret
Time
Proactive Secret Sharing
Server 1 S Server 2
S1 S2
Goal: without changing the secret, periodically update
shares in a way that old shares are invalidated.
Proactive Secret Sharing
Server 1 S Server 2
S1 S2
S11 S12 S21 S22
Goal: without changing the secret, periodically update
shares in a way that old shares are invalidated.
Proactive Secret Sharing
Server 1 S Server 2
S1 S2
Exchange
Partial Shares
S11 S12 S21 S22
S21 S12
Goal: without changing the secret, periodically update
shares in a way that old shares are invalidated.
Proactive Secret Sharing
Server 1 S Server 2
S1 S2
Exchange
Partial Shares
S11 S12 S21 S22
S21 S12
Compute
New Shares
S’1 S’2
Goal: without changing the secret, periodically update
shares in a way that old shares are invalidated.
Proactive Secret Sharing
Server 1 S Server 2
S1 S2
Exchange
Partial Shares
S11 S12 S21 S22
S21 S12
S’1 S’2
Recover S
(S11 S21) (S12 S22)
S
BitCoin Multi-Signature Addresses
• Related to, but different than secret sharing.
• Secret sharing: split a single secret into multiple shares.
• Multi-signature address: requires multiple signatures with
different private keys (secrets) to authorize a transaction.
• Examples: 2 out of 2, 2 out of 3, 3 out of 5.
Opening the Vault
