[Cryptography] Shamir’s secret sharing

[Natanael]

Den tors 20 juni 2019 02:50Adrian McCullagh <amccullagh at odmoblawyers.com>
skrev:

> 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?
>
Tldr it's secure even against quantum computers (if used with a secure
RNG).

Both classical and (general) quantum computers are approximately Turing
complete*, and any and every Turing complete computer can perfectly
simulate every other. Which means that everything computable by one Turing
machine is computable by them all (given enough time). And to the best of
our knowledge, everything which is computable can be computed by Turing
complete computers, we don't know of any solvable problem which they can't
solve.

* the full definition assumes infinite memory, which we don't have. Thus,
the machines we have are only approximately Turing complete.

What differentiates quantum computers from classic ones are which classes
of problems they solve how fast, but not their mathematical capabilities.

Every Turing complete computer can solve RSA of any size *with enough
resources*, but given the *available* resources our classical computers
gets stuck at around 2 kilobit RSA keys while quantum computers with our
available resources can in theory break RSA all the way to up to sizes of
multiple million bits or more (after that you hit the limits described in
the pqRSA papers). We also know exactly how to bruteforce AES256, but
neither classical nor quantum computers can actually do it when limited by
the resources we have available.

To the point;

Shamir's secret sharing scheme, when used with a secure unpredictable RNG,
is information theoretically secure. As such, it can't be broken by *any*
computer which follows known physical assumptions. When you don't have
enough shares to reach the threshold, there simply doesn't exist *any*
information that allows you to guess the secret better than random.

Just make sure your RNG itself is actually secure! A predictable RNG can
reveal correlations between the shares that was created and thus reveal the
secret.

So if used right, breaking Shamir's secret sharing scheme would require
some computer with access to a yet unknown mathematical "oracle", a
capability that exceeds the capability of Turing complete machines, and we
have no reason to believe that's possible. Quantum computers certainly
can't, not with what we know about them.

References:

https://crypto.stackexchange.com/q/10904/7431

https://github.com/WebOfTrustInfo/rwot8-barcelona/blob/master/topics-and-advance-readings/security_shamirs.md
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20190620/96987707/attachment.html>