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? Kind Regards Adrian Dr. Adrian McCullagh Ph.D. (IT Sec) LL.B.(Hons) B. App. Sc. (Computing) ODMOB Lawyers Research Fellow: Law Futures Centre Griffith University Mobile +61 (0) 401 646 486 Business Skype: admac57 Personal Skype. amccullagh@live.com<mailto:amccullagh@live.com> Business E: amccullagh@odmoblawyers.com<mailto:amccullagh@odmoblawyers.com> Personal E: amccullagh@live.com<mailto:amccullagh@live.com> WEBSITE: www.odmoblawyers.com<http://www.odmoblawyers.com/>; The contents of this email are confidential between the sender and the intended recipient. If you are not the intended recipient then no rights are granted to you because of this error and as such you are requested to promptly inform the sender of the error and to promptly destroy all copies of the email in your power, possession or control. The sender reserves all rights concerning this email and its contents including any privilege, copyright and confidentiality associated with this email. Even though an email signature block has been appended to this email, and notwithstanding the Electronic Transactions Act (Qld) or the Electronic Transactions Act (Cth), the signature block does not exhibit the senders intention to be bound by an offer previously sent by the intended recipient, unless the email in its body specifically indicates that the sender hereby accepts such an offer previously sent by the intended recipient. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

> On Jun 19, 2019, at 6:57 PM, Adrian McCullagh <amccullagh@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. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

Den tors 20 juni 2019 02:50Adrian McCullagh <amccullagh@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 _______________________________________________ The cryptography mailing list cryptography@metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography