<div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">Den tors 20 juni 2019 02:50Adrian McCullagh <<a href="mailto:amccullagh@odmoblawyers.com" target="_blank" rel="noreferrer">amccullagh@odmoblawyers.com</a>> skrev:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-AU" link="#0563C1" vlink="#954F72">
<div class="m_1520511189481803368m_7663646311126446372WordSection1">
<p class="MsoNormal">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? </p></div></div></blockquote></div><div dir="auto">Tldr it's secure even against quantum computers (if used with a secure RNG). </div><div dir="auto"><br></div><div class="gmail_quote" dir="auto"></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">* the full definition assumes infinite memory, which we don't have. Thus, the machines we have are only approximately Turing complete. </div><div dir="auto"><br></div><div dir="auto">What differentiates quantum computers from classic ones are which classes of problems they solve how fast, but not their mathematical capabilities. </div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">To the point;</div><div dir="auto"><br></div><div class="gmail_quote" dir="auto"></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">References:</div><div dir="auto"><br></div><div dir="auto"><a href="https://crypto.stackexchange.com/q/10904/7431">https://crypto.stackexchange.com/q/10904/7431</a><br></div><div dir="auto"><br></div><div dir="auto"><a href="https://github.com/WebOfTrustInfo/rwot8-barcelona/blob/master/topics-and-advance-readings/security_shamirs.md">https://github.com/WebOfTrustInfo/rwot8-barcelona/blob/master/topics-and-advance-readings/security_shamirs.md</a><br></div><div dir="auto"><br></div><div class="gmail_quote" dir="auto"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-AU" link="#0563C1" vlink="#954F72"><div class="m_1520511189481803368m_7663646311126446372WordSection1"><p class="MsoNormal"><u></u></p>
</div></div></blockquote></div></div>