Can Shamir's SSS be augmented so that having the secret as well as half the shares necessary to construct the secret is enough to reconstruct the key?

More generally, is it possible to construct a $$(k,n)$$ threshold secret sharing scheme (i.e. let than k shares leaks no statistical information about the secret) such that possession of the secret along with fewer than $$\left\lfloor \frac{k-1}{2} \right\rfloor$$ is enough to reconstruct the entire key (i.e. the entire polynomial)?

Context: I am trying to use a classical secret sharing scheme in a quantum setting, which requires erasing memory about the key once the secret is constructed.

So, if you have a $$(k,n)$$ threshold scheme, this means that your polynomial is of degree $$k - 1$$. That means you need $$k$$ points to interpolate the polynomial. The secret is just another data point. So, to reconstruct the very same polynomial used initially, possession of the secret should not help. You'd still need enough $$(x,y)$$ pairs to get back to the polynomial.

More generally, is it possible to construct a $$(k,n)$$ threshold secret sharing scheme (i.e. let than k shares leaks no statistical information about the secret) such that possession of the secret along with fewer than $$\left\lfloor \frac{k-1}{2} \right\rfloor$$ is enough to reconstruct the entire key (i.e. the entire polynomial)?

Well, if that's the problem you need to solve, well, sure, it is possible.

One obvious approach would be to extend your secret by including 256 random bits; you then take your extended secret $$S'$$, and construct a $$(k,n)$$ secret sharing scheme with that, using the bits from $$\text{SHAKE}(S')$$ as the source of the bits to construct your polynomial (rather than selecting them at random).

So, when you reconstruct the secret $$S'$$, that secret is sufficient to completely reconstruct the entire polynomial (along with 0 shares, which is fewer than $$\left\lfloor \frac{k-1}{2} \right\rfloor$$); when it comes time to use the secret, you just ignore the 256 random bits you added to $$S'$$

Now, I get the feeling that this doesn't really answer the question you really wanted to ask, but I don't know what that question is...

• Ah, I require that no randomness is added to the secret. Maybe this will help: Alice and Bob each hold 2 shares of a (5,2) and Eve holds 1 share. Alice and Bob deduce from their shares the secret as well as the key. They now have to turn over the information about the key to Eve, but before doing so they are aloud to act on the key with a function that is invertible given the secret (which should contain no information about the key). Given Alice and Bob know what share Eve holds, a natural choice is to turn the key into Eve's share. I am wondering if this is possible. – cplusplusguru Apr 26 at 16:42
• @cplusplusguru: if your shared secret is unguessable (e.g. it's a random AES key), then you can get away without the 256 random bits (which are there so that the adversary could not verify a guess of the shared secret) – poncho Apr 26 at 16:51