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.