Re: Secret sharing algorithm with chosen keys


<lethal.possum@xxxxxxxxx> wrote in message
news:72bd8abd-1082-4b30-8659-7e3c4bfccde5@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hello,

I am looking for a secret sharing sharing scheme where the keys are
chosen and the resulting shared secret is computed from the keys. My
scenario is the following. I have a manufacturer that can create a
token containing a random cryptographic key. A group of N persons
decide to each buy one of these token/key only for the purpose to
compute from these keys a shared secret that any T of the N persons
should be able to recompute later.

I have read about schemes like Shamir's or Blakley's but here the
difference is in my situation the keys are chosen (randomly) by the
manufacturer. So it's the shared secret that needs to be computed from
the individual keys, not the other way around. I don't know if there
is a way to reverse the Shamir's or Blakley's scheme to work that way.

If N = T, it's easy: I could simply XOR the N keys to get the shared
secret. But I'd like to be able to reconstruct the shared secret even
in the case of a few missing shares. Does someone know of a secure way
to solve my problem?

As stated, I'm not sure if there's any way if T<N. Lets explore this a bit
to see why:

- Suppose that you have a group of T-1 people with valid tokens. Of course,
they can't compute anything.

- Suppose that you also have three individuals, Alice, Bob and Carol. Alice
and Bob have valid tokens (each of which include a random number). Carol
does not have a valid token, but she just made up a random number anyways.

You are looking for a scheme that takes the keys from T tokens, and
generates a value. So, let us call the value that, given the token values
from the group + Alice, "S". Then, that scheme would also need to have the
property that:

- The group + Bob is able to compute the same shared secret S
- The group + Carol is not able to compute the shared secret S.

However, all that Bob has is just a random number, just like Carol. What
makes Bob's random number different from Carol's?

From the above analysis, it would appear necessary for either the
manufacturer's random key have more properties than just being a random
number, the scheme has some input beyond the random values on the tokens or
there needs to be trusted third party which can distinguish valid random
numbers from bad ones.

--
poncho


.

Relevant Pages

  • Re: Secret sharing algorithm with chosen keys
    ... But I'd like to be able to reconstruct the shared secret even ... then protect the shared secret with multiple decryption keys, ... to precompute the public file: ... Given T tokens, ...
    (sci.crypt)
  • Re: Secret sharing algorithm with chosen keys
    ... But I'd like to be able to reconstruct the shared secret even ... then protect the shared secret with multiple decryption keys, ... My analysis neglected the possibility of a public file whose ... Given T tokens, ...
    (sci.crypt)
  • Secret sharing algorithm with chosen keys
    ... I am looking for a secret sharing sharing scheme where the keys are ... chosen and the resulting shared secret is computed from the keys. ... is a way to reverse the Shamir's or Blakley's scheme to work that way. ...
    (sci.crypt)
  • Re: Implicit actions and movement
    ... Laptop unfriendliness with numpad control scheme, ... possibility you have that will avoid ambiguousness of movment that we ... keys on the num pad) and have 4&6 change the facing. ...
    (rec.games.roguelike.development)
  • Re: Favorite Movment Keys
    ... keys, and whatever oddball scheme the author thinks is better than vi ... diagonals for the arrows, ... making the user select a control scheme appropriate to their region on ...
    (rec.games.roguelike.development)