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