[Cryptography] Shamir’s secret sharing

Viktor Dukhovni cryptography at dukhovni.org
Thu Jun 20 00:28:53 EDT 2019


> On Jun 19, 2019, at 6:57 PM, Adrian McCullagh <amccullagh at odmoblawyers.com> wrote:
> 
> Can anyone point me to any papers dealing with the issue of whether Shamir’s Secret Sharing scheme is quantum crypto resistant.  In particular if it is resistant does the resistance improve if the complexity of the scheme increases.  That is, with n out of t, is 2 out of 3 keys less resistant that say 11 out of 21?

It is information-theoretically secure, just like a one-time pad.
Without the last requisite key-share you get zero information
about the shared secret, unless you know something about how
the missing share was generated (flaw in the RNG, ...).

A polynomial with coefficients in a field of degree $n$ is
uniquely determined by its values at $n+1$ distinct points
(e.g. a line is determined by two points), and any fewer
points get you no information about what value it takes
at some other distinct point.

With all but one share fixed, the secret is an affine linear
function (Ax + B) of the remaining share "x" with a non-zero
A.  Since we're in a field, the function is one-to-one and
the secret value is equidistributed if "x" is.  Thus same
security as a one-time-pad.
 
-- 
	Viktor.



More information about the cryptography mailing list