# Is there an algorithm to derive a 1-of-N shared secret from a set of N private keys?

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.

• 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? – Guut Boy Oct 18 '16 at 6:38
• You can assume a trusted dealer. – Mike S. Oct 18 '16 at 10:02

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?

• 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). – Ilmari Karonen Oct 19 '16 at 16:21
• 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. – Louis Nov 17 '16 at 4:04