Subset secrets

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.

Share Button

5 Responses to “Subset secrets”

  1. Dylan Mar 13, 2013 at 5:03 pm #

    Shamir's Secret Sharing (https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing)

  2. Mohammed Elalj Mar 14, 2013 at 11:41 am #

    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.

    • Mohammed Elalj Mar 14, 2013 at 4:28 pm #

      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

    • Mohammed Elalj Mar 15, 2013 at 1:09 am #

      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

  3. Rachel Apr 19, 2013 at 9:47 am #

    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.

Leave a Reply