# 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?

Did you love challenges? Then you will love LiveRamp. Apply now to join our team.

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.