Sampled Bits

In theory there is no difference between theory and practice; in practice there is

About GitHub Linkedin Blog
27 September 2018

Secret Sharing

by Alexandra Albu

Secret sharing is a very nice cryptographic primitive which is based on an ingenious yet simple idea. Although the main concept is pretty old, it still finds many applications in various fields.

The main motivation behind the development of secret sharing schemes was cryptographic keys management. Otherwise a difficult task, secure storage of cryptographic keys can be easily done using secret sharing. Simply encrypting the keys does not solve the problem, as the used encryption key still needs to be managed. On the other hand, the keys can’t be stored in plaintext - saving them in a single place is unreliable as they can be lost, while storing multiple copies of a key increases the risk of it being found by an attacker (1).

Secret sharing solves these problems using a clever idea. The method consists in splitting a secret - in the above scenario, the encryption key - into multiple parts, called shares, such that each individual share reveals nothing about the secret. The secret can, however, be reconstructed by authorized groups (called access structures). A scheme in which a secret is reconstructed given a sufficiently large group of shares is called a threshold secret sharing scheme. In this blog post we will discuss only this type of schemes.

Some less straightforward, but very interesting applications of secret sharing are secure multiparty computation protocols. These protocols allow users to compute a function over some inputs $x_1, x_2,…, x_n$ where $x_i$ is a secret known only by the $i^{th}$ user (2). Such secure computations can vary from simple sums over encrypted data - with applications in electronic voting - to data mining or even machine learning algorithms (for more on this, check this great blog post). This is possible due to the homomorphic properties of secret sharing schemes - we’ll come back to this later.

From the security point of view, secret sharing schemes can be classified into:

Shamir’s Secret Sharing Scheme

The algorithm was developed by Adi Shamir in 1979 and is based on polynomial interpolation. The central idea behind the scheme is that a polynomial of degree $ k-1 $ is uniquely determined by its values at $k$ points, while knowledge of at most $ k-1 $ point-value pairs gives no information about the polynomial coefficients. Put in an algorithmic/formal way, Shamir’s scheme goes like this:

Let $F$ be a finite field of size $p$ and $S$ be the secret. We assume without loss of generality that $S$ can be represented as an element of $F$. Let $k, n$ be natural numbers with $k \le n$, where $n$ represents the number of participants in the scheme - and the number of shares - and $k$ is the threshold value.

  • Choose $k-1$ elements $a_1,a_2,…, a_{k-1}$ from $F$ and construct the polynomial $f(x)=a_0+a_1x+a_2x^2+…+a_{k-1}x^{k-1}$, where $a_0=S$.
  • Compute the value of $f$ at $n$ distinct non-zero elements $x_1, x_2,…, x_n$ and distribute the shares $(x_i, f(x_i))$, $1 \le i \le n$ among the participants.
  • $k$ participants can now reconstruct the secret by using polynomial interpolation. Such a scheme is called a $(k, n)$ threshold scheme.

The main idea of Shamir’s secret sharing scheme can be illustrated through Fig. 1. (Disclaimer: I lied a bit here, as Shamir’s scheme deals with finite fields and not real numbers as in my figure down here. However, the main concept can be more easily visualized and understood in $\mathbb{R}$)

Visualization of Shamir's scheme
Fig. 1: In the left figure: being given 2 points, we can find an infinite number of second degree polynomials which pass through these points. In the right: having 3 points, one uniquely determines the second degree polynomial.

Blakley’s Secret Sharing Scheme

While Shamir’s scheme is based on polynomial interpolation, Blakley’s secret sharing algorithm relies on geometric properties of planes in a Euclidean space. In Blakley’s $(k, n)$ scheme, the secret is a point in a $k$-dimensional space and the shares are $n$ $(k - 1)$-dimensional hyper planes on which the secret lies. The secret can be recovered by finding the intersection of $k$ such planes.

Bibliography:

[1] Shamir A.: How to share a secret, Communications of the ACM 22.11 (1979): 612-613

[2] Yao A. C.: Protocols for secure computations. Foundations of Computer Science, 1982, SFCS’08. 23rd Annual Symposium on (pp. 160-164).

[3] https://mortendahl.github.io/2017/06/04/secret-sharing-part1/

tags: secret sharing - Shamir's Secret Sharing Scheme - Blakley’s Secret Sharing Scheme