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).

.. more.

Homomorphic Encryption

We will talk in this post about a very useful cryptographic tool. But lets talk first about the motivation or the problem it solves first.

As the first example, we will introduce the private voting problem:
We want to make an online voting application, no one can know what anyone else has voted (not ever the server itself), but at the end, we will know how many votes each candidate has received. The problem is even harder if there is no "central" trusted server and it is a distributed system which all nodes interact with all others and no one can trust anyone else.

Now, lets introduce homomorphic encryption. Homomorphic encryption, is an encryption system which allows you to do calculations on the encrypted data, without knowing the original text. At the end you will get the encryption of the result, not the result itself.

Caution: the notation used is simplified and there are some details that are not mentioned in order to simplify the presentation.

To make it more elaborate, assume $a, b$ are plain texts, and $E(a), E(b)$, are their encryption. If the encryption system you are using allows for addition, you can then call $Add(E(a),E(b))$ and you will get $E(a+b)$.

Ok, so how can this help us in our voting problem ? We will describe the protocol to show how. There is a node which will start the voting, it is the only node that can decrypt values. He will send his vote $v_1$, either 0 or 1, encrypted to the the next node. The next node will take the encrypted vote and adds his encrypted vote, either 0 or 1, and forwards it to the next one, and so forth, in a ring-like fashion, until it reaches the first node again. The first node will then decrypt and will find the sum of the votes for the first candidate. This is repeated for each candidate.

Homomorphic encryption has a lot more applications, and is more sophisticated that the simplified version mentioned here. For example, it usually has "semantic" security, which means that it is a probabilistic encryption, which means that every time you encrypt the same value, you will get a different cipher text. That is, if two people sent you $E(1)$, you will not be able to know it is the same value just by looking at the cipher text alone. Also, there are encryption schemes that only allows for addition, and others that only allow for multiplication. There is one that allows for addition and only one multiplication. Those who supports unlimited number of addition and multiplication are called "algebraic homomorphic encryption", or "fully homomorphic". So far, fully homomorphic schemes incur very big overhead for practical purposes.

Note that homomorphic properties are usually intended in a cipher. If a cipher had these properties and it was not intended, it is called "malleable" encryption and it is considered a flaw instead. Remarkable homomorphic cryptosystem are RSA, ElGamal, and Paillier.

Note also that these schemes are also asymmetric. So anyone with public key can encrypt a value, but can not decrypt it except with a public key.

References:
- Pascal Paillier: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. EUROCRYPT 1999:223-238

- http://en.wikipedia.org/wiki/Homomorphic_encryption


Author: Mohammad Alaggan

.. more.