Subset secrets
Categories: Challenges, Engineering
There is a secret that you wish to partially share amongst N people such that there is an M < N for which any M or more people can reconstruct the secret, but any K < M people cannot. How do you encode the secret?
Shamir's Secret Sharing (https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing)
I would ask the first time each one from [M ; N] people to communicate me a public key that will allow me to send a private key using a RSA encryption algorithm.
This private key that I provided will allow them to reconstruct (via RSA) the secret.
I was too quick the first time and I understood backwards the problem.
Actually a secret can be reconstructed only if a minimum of M people are COMBINED...
The idea is to bring to each person (N-M+1) sub-keys. The full key is formed by N "sub-keys", this one will allow us to encrypt the message (using XOR algorithm).
A combinaison of M people is enough to get the full key and decrypt the secret.
I wrote a python script that encrypt a message with a list of private sub-keys (generated randomly), and decrypt a secret from a set of people.
https://www.github.com/melalj/liveramp-subset
I was too quick the first time and I understood backwards the problem.
Actually a secret can be reconstructed only if a minimum of M people are COMBINED...
The idea is to bring to each person sub-keys. The full key is formed by many "sub-keys", this one will allow us to encrypt the message (using XOR algorithm).
A combinaison of M people is enough to get the full key and decrypt the secret.
I wrote a python script that encrypt a message with a list of private sub-keys (generated randomly), and decrypt a secret from a set of people. However, it's also working for K<M people...
https://www.github.com/melalj/liveramp-subset
We shall use Shamir Secret Sharing Algorithm to correct this issue:
http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing
There is a secret that you wish to partially share amongst N people such that there is an M < N for which any M or more people can reconstruct the secret, but any K m, we will have larger than m points, hence able to interpolate and obtain the full polynomial of degree m-1. We need n to be prime in order for Zn to be a field, but i guess, as long as we do not evaluate the function at the zero divisors of the functions, it should be fine (not sure though). Evaluating the function over a field ensures that we have integer solution, which makes the points prettier, and the polynomial precise.