Shamir Knows Alice and Bob's Shared Secret

a brief introduction to secret sharing

Thom Dixon <thomdixon@ufl.edu>

a brief introduction to secret sharing

First...

Contrived motivation

• The scrupulous bank manager.
• Has eight employees under her.
• Wants the vault to only be opened when more than half of her employees are present.
• How can she do this?
• Let's generalize the problem a little, and then reconsider.

Once again, with precision

• Given a secret S, we wish to give n people shares (pieces derived from S) such that:
• Knowing k (where k is bounded above by n) many shares enables you to reconstruct S.
• Having only k-1 (or less) shares gives you no further information about S.
• This is called an (n, k)-threshold scheme, where k is the threshold. The dealer provides the shares to the players.

Shamir's clever idea

• To solve our flustered bank manager's problem, we're going to construct an

(n, k)-threshold scheme.

• Recall that a k^th degree polynomial can be determined given k+1 points along the curve (interpolation).
• The gist is to encode our secret as a coefficient of a polynomial P with degree k-1, and then dole out the results of evaluating P at various points.

Shamir Secret Sharing

• Represent S uniquely as a natural.
• Choose a prime q such that q > S.
• Construct a (k-1)^th degree polynomial P over GF(q) in the following way:
• Fix the constant term a₀ = S.
• Randomly choose the remaining k-1 coefficients a₁, ..., a_k-1 from GF(q).
• For i = 1, ..., n, hand out (i, P(i)) as shares.

Consequences

• This is very clearly an (n, k)-threshold scheme.
• Why do this over GF(q)? Convenience.
• This scheme is information-theoretically secure (like One-Time Pad). In a nutshell, given an infinite amount of time and (computational) resources, this scheme remains impervious to cryptanalysis.
• This scheme is minimal (each share does not exceed the order of the secret).

Consequences (cont'd.)

• This scheme is hierarchical.
• Remember our bank manager? Construct an (18, 6)-scheme. The manager gets six shares, her two assistant managers get three each and each employee gets one share.
• Although minimal, this scheme does require that given a one gigabyte secret, each share be roughly one gigabyte.

Applications

• Distributed voting protocol.
• Note that Shamir's scheme is homomorphic with respect to the encoding function f, of the secret. That is, denote by W the set of all secrets, then f : W → GF(q)[x] is a homomorphism under addition. In particular, given encoded secrets a, b ∈ GF(q)[x] we have that f ^-1(a + b) = f ^-1(a) + f ^-1(b).

Applications (cont'd.)

• Assume we're voting on a yes or no issue.
• Suppose that there are n polling authorities and each has a published public identification number v_i.
• Each voter will construct a (n-1)-degree polynomial P_j using Shamir's scheme with their secret being -1 (no) or 1 (yes).
• Then the voter will evaluate P_j(v_i ) for i = 1, ..., n and give this value to polling authority i.

Applications (cont'd.)

• Finally, the polling authority i will sum all of the P_j(v_i ) values provided by voters and distribute this sum to the other n-1 authorities.
• Given all n sums, we can interpolate using the points (v_i , ∑ P_j(v_i )).
• The resulting constant term is positive if more votes were received for yes and negative if more votes were received for no.

Relax a little

• By relaxing the condition of information-theoretic security (i.e., perfect security) for computational security we can get smaller shares, and therefore a more practical scheme.
• This forms the foundation for a 1993 paper titled Secret Sharing Made Short from Hugo Krawczyk at IBM.
• Let's cover some prerequisites.

Semantic security

• Denote by Enc_K the (private key, length-preserving) encryption function Enc selected by key K. Let M be a message in the domain of Enc_K. We say that Enc_K is semantically secure if no information about M can be obtained in polynomial time from Enc_K(M).

Semantic security (cont'd.)

• This is equivalent to and often stated in the (easier to phrase/understand) form of ciphertext indistinguishability.
• An encryption function has ciphertext indistinguishability if an adversary who possesses two plaintexts M and M' and their respective ciphertexts C and C', has probability 1/2 + ε(K) of matching them correctly.

Reed-Solomon codes

• Very similar to Shamir's scheme.
• Rather than a secret S, we have data D.
• Instead of letting D be the constant term, we partition D in a natural way into D₀, ..., D_k-1 and let these be the coefficients of a (k-1)^th degree polynomial P over GF(q) with q a sufficiently large prime.
• We then evaluate P at i = 1, ..., n and dole out (i, P(i)).
• Reconstruct D easily via interpolation.

Krawczyk's clever twist

• Let S denote our secret and let Enc be a semantically secure cipher.
• Randomly select a key K and define E := Enc_K(S).
• Partition E into n fragments, E₁, ..., E_n, using Reed-Solomon.
• Use Shamir's scheme to construct n shares of K, dubbed K₁, ..., K_n.
• Dole out (E_i, K_i) for i = 1, ..., n as shares.

Consequences

• Is computationally secure. That is, if an adversary is given k-1 shares, they cannot discern further information about S in polynomial time.
• Reconstruction is very simple (interpolate twice, and then decrypt).
• Each share is roughly |S|/n + |K| units in size.

Applications

• More or less the idea behind the Vanish project from the University of Washington, which seeks to provide self-destructing data in a peer-to-peer system.
• Unfortunately, their replication algorithm was too eager which left them vulnerable to a Sybil attack, but apparently they're working with Vuze to address the problem.

AONTs

• In 1997, Ron Rivest (of RSA fame) introduced the concept of an All Or Nothing Transform (AONT).
• Described by Victor Boyoko, an AONT is "an unkeyed, invertible, randomized transformation with the property that it is hard to invert unless all of the output is known."
• In other words, an AONT is an (n, n)- threshold scheme.

AONTs (cont'd.)

• In practice, AONTs are used as a preprocessing step prior to encryption, mapping a message to a pseudo-message. This requires that an adversary decrypt the entire ciphertext when trying possible keys, which can significantly increase their computation time.
• We're going to explore Rivest's Package Transform, but first we have to cover some prerequisite knowledge.

XOR

• Interpret length n bit vectors a, b, and c as elements of (ℤ₂)ⁿ.
• Then XOR (denoted by ⊕) is just the usual addition in this abelian group. That is,
• a ⊕ a = 0,
• if a ⊕ b = c then c ⊕ b = a.
• This last property lends to its heavy use in cryptography to combine keystreams with plaintext in order to produce ciphertext. That, and it's fast and cheap.

Block Ciphers

• A block cipher is an indexed family of permutations which map a length n bit vector (called a block) to another length n bit vector in a pseudorandom fashion.
• The secret key then selects a permutation from this family.
• Common block ciphers include the AES (current FIPS), DES (old FIPS), 3DES, Blowfish, and more.
• Wikipedia is a wonderful resource.

Hash Functions

• Usually explained as a "fingerprint for data" since it provides integrity.
• Is a function h which compresses an arbitrary length bit vector into an n length bit vector, where n is fixed.
• h is a secure hash function if it
• has first and second preimage resistance,
• and has collision resistance.
• Examples include MD5, SHA-1, Skein and Keccak (SHA-3).

Package Transform

• Let Enc denote a block cipher and m₁, ..., m_n be our input message.
• Choose a random key K for Enc and a fixed key L.
• Compute the pseudo-message sequence c₁, ..., c_n+1 as follows.
• c_i = m_i ⊕ Enc_K(i) for i = 1, ..., n
• c_n+1 = K ⊕ h(1) ⊕ h(2) ⊕ ... ⊕ h(n)
• where h(i) = Enc_L(c_i ⊕ i)

Considerations

• The block cipher's block size provides a natural choice of share sizes.
• Loophole in cryptography export restrictions permit use of strong AONTs with weak encryption. This was the primary reason the scheme was proposed.
• This stems from the fact that K is not a shared secret key. It can be reconstructed by anyone who has the whole pseudo-message.

Applications

• Useful as a mode of encryption (as previously discussed).
• Use with Reed-Solomon to create an (n, k)-threshold scheme, as suggested by Resch and Plank in 2011 (dubbed AONT-RS).
• Turns out that the OAEP (the padding used for RSA, as specified by PKCS #1) is an AONT, as shown by Ron Rivest's graduate student Victor Boyko in 1999.

Asmuth-Bloom Scheme

• The big idea is to make an (n, k)-threshold scheme by constructing a system of n congruences such that the solution to any k of them uniquely determines S.
• Choose pairwise coprime positive integers T, m₁, m₂, ..., m_n such that
• S < T < m₁< ··· < m_n and so that
• m₁m₂ ··· m_k > T · m_n-k+2 ··· m_n.
• Such a sequence of integers is called an Asmuth-Bloom sequence.

Asmuth-Bloom (cont'd.)

• Define M := m₁m₂ ··· m_k for convenience.
• Choose a random positive integer R such that y := S + RT < M.
• Compute y_i := y (mod m_i) for i = 1, ..., n.
• Dole out (y_i , m_i) as shares.
• To see why this works, let D be a collection of k shares. Then by the CRT, there exists a unique solution y₀ modulo M_D := Π_{i ∈ D} m_i .

Asmuth-Bloom (cont'd.)

• Since y < M < M_D+1, we have that y₀ is unique modulo M.
• Finally, by construction, we have that S = y₀ (mod T).
• The key observation is that for any solution, y₀, to a (k-1)-subset of congruences, y₀ , can take on T possible values modulo T (i.e., is undetermined).

Consequences & Applications

• Like Shamir's scheme, Asmuth-Bloom offers information-theoretic security.
• This scheme was used to construct two function sharing schemes (replace the idea of reconstructing a secret with idea of evaluating a function) for computing RSA signatures and ElGamal decryption.

Other schemes

• Blakely independently discovered secret sharing in 1979 (same year as Shamir). His scheme used the intersection of (n-1)-dimensional hyperplanes in n-dimensional space. Shamir's scheme won due to the use of less storage space.
• There are a few other schemes based on the CRT. Wikipedia has a nice article.
• Current research is looking into (public) verifiability, and proactivity.

Questions/Comments?

Slides available at thomdixon.org.