2
$\begingroup$

This is different from Shamir's Secret Sharing in that we are starting with the keys and deriving a shared secret, rather than the other way around.

Let me be more precise:

We are given keys $k_1, \ldots, k_N$. We wish to derive a shared secret $S$ and a public datum $D$ such that:

  • $S$ is the same size as the $k_i$ (i.e. it is an element of the same key space).
  • $D$ is as small as possible -- hopefully no bigger than $S$ (but I'll take what I can get).
  • $D$ together with any one $k_i$ is sufficient to recover $S$, but insufficient to recover any of the $k_j$ (for $i \ne j$).
  • $D$ alone is insufficient to recover $S$. (This is to preclude trivial solutions like making $S$ constant.)

Can anyone suggest an algorithm, or convince me that this is impossible?

If no one solves this I may accept a partial solution that satisfies a subset of the above criteria.

$\endgroup$
2
  • $\begingroup$ are these $N$ different keys assumed to be held by $N$ different parties? Also should $S$ and $D$ be the result of some protocol among those parties or can we assume there is a trusted dealer? $\endgroup$
    – Guut Boy
    Oct 18, 2016 at 6:38
  • $\begingroup$ You can assume a trusted dealer. $\endgroup$
    – Mike S.
    Oct 18, 2016 at 10:02

1 Answer 1

2
$\begingroup$

I'll start this thread off with a not-very-satisfying solution. If we let $D$ be as long as all the $k_i$ put together (i.e. $|D|=N |k_1|$), then we can solve this using Shamir's Secret Sharing (SSS).

First, choose any $S$ we want. (As you can see, this problem is now under-constrained.)

Use $1$-of-$N$ SSS to derive keys $r_1,\ldots,r_N$, any one of which is sufficient to recover $S$.

Then define $$d_i := r_i - k_i$$ (that is, the difference between the $i$-th SSS key and our $i$-th input key).

Finally, let $$D := d_1 \| \cdots \| d_N$$

Now we can use any single $k_i$, together with $D$, to recover one of the $1$-of-$N$ SSS keys, which gets us $S$.

So I've established an upper bound on the length of $D$. Can anyone do better?

$\endgroup$
2
  • $\begingroup$ I believe this is optimal, by a simple counting argument. However, your scheme does not seem to actually satisfy the requirement that knowing $D$ and $k_i$ should not reveal $k_{j \ne i}$ (since in 1-of-$n$ Shamir's secret sharing the polynomial has degree 0, and so $r_i = r_j = S$). This could be fixed e.g. by defining $d_i = E_{k_i}(r_i) = E_{k_i}(S)$, where $E$ is a pseudorandom permutation family (e.g. a block cipher) over the keyspace, indexed by the key $k_i$. Note, however, that this would still not be information-theoretically secure (and indeed, I believe such security is impossible). $\endgroup$ Oct 19, 2016 at 16:21
  • $\begingroup$ If you want to make it information theoretic why not make each $d_i$ a share on a polynomial of degree at most $1$ such that the point $d_i$ and the participant's share $(i,k_i)$ both reside on $f_i(x) = S + a_i x$, Where $i$ is obviously publicly known. Thus to get the secret $P_i$ simply performs Lagrange interpolation on his own share $(i, k_i)$ and the public value $d_i = (x_i,r_i)$. obviously in this case $|D| = 2N|k_i|$ which is not very efficient. $\endgroup$
    – Louis
    Nov 17, 2016 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.