Shared secrets

This post continues the other approach to secure multi-party computation, which is called "Secret-sharing".

The problem

Consider the problem that, there is a nuclear missile, and there is its launch code. Only the president has that code. But what if the president is unavailable ? We can't trust any of the executives alone. We would require for example that 3 of them can launch the missile, but not any single one of them alone. This is what secret-sharing is about. It's goal is quite different than homomorphic encryption, but it used also for secure multi-party computation.

Which is more secure?

Homomorphic encryption relies on the assumption that it would take long time to crack it. Typically for example, the problem of factoring a very big number. Secret-sharing, on the other hand, is secure in information-theory sense. That means that even if given the entire eternity, you can not break it, simply because there is no information leakage (unlike the other approach where is information leakage with small probability).

Shamir's Secret Sharing

The first to publish about a practical secret sharing scheme was Shamir, in 1979 [1]. It's target is to create $n$ shares of the secret, such that any $k$ shares are sufficient to reconstruct the secret. Each person would be given some shares. The president is allowed to launch the missile alone, so he will have $k$ shares. The executes must be 3, so each one will take $k/3$ shares. The total number of shares is unbounded. Such a scheme is called $(k,n)$ secret-sharing.

What if some shares was stolen ?
If the number of shares stolen were less than $k$, then the other shares can be renewed by adding a random shared secret whose value is zero [2]. The old stolen shares are useless now since their compatible shares were replaced by new ones.

How does it work ?

Shamir's scheme depends on Lagrange Interpolation of polynomials. Using Lagrange interpolation, you can recover a polynomial $f(x)$ of degree $t$, given $t$ pairs $(x_i,y_i)$ such that $y_i=f(x_i)$.

Encoding a secret

To encode a secret value $v$ in a $(k,n)$ secret-sharing scheme, do the following:

- Generate a random polynomial of degree $k$ whose free coefficient is $v$ (that means $f(0)=v$).

- Evaluate the polynomial at $n$ different points $x_1,x_2,..,x_n$

- Each share consists of a pair $(x_i,f(x_i))$

Reconstructing a secret

to reconstruct the secret, collect $k$ shares, and follow the Lagrange interpolation and substitute $x$ by zero. That is we reconstruct the polynomial and evaluate it at zero. The result is $f(0)$, which is $v$. If you have less than $k$ points, the constructed polynomial is wrong and you can not retrieve the secret.

[1] A. Shamir, "How to share a secret," Communications of the ACM, vol. 22, 1979, p. 612–613.

[2] Herzberg, A., Jarecki, S., Krawczyk, H., and Yung, M. 1995. Proactive Secret Sharing Or: How to Cope With Perpetual Leakage. In Proceedings of the 15th Annual international Cryptology Conference on Advances in Cryptology (August 27 - 31, 1995). D. Coppersmith, Ed. Lecture Notes In Computer Science, vol. 963. Springer-Verlag, London, 339-352.

Originally posted to http://fci-h.blogspot.com/. This is just an automatically forwarded copy. (To read the Latex-typeset mathematics correctly, please visit the original post).