[Cryptography] Shamir's secret sharing

[Henry Baker]

At 03:57 PM 6/19/2019, Adrian McCullagh 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?
> 
>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 at live.com
>Business E: amccullagh at odmoblawyers.com 
>Personal E: amccullagh at live.com
>WEBSITE: www.odmoblawyers.com 

Shamir's Secret Sharing has *information theoretic security*; i.e.,
without sufficient information, NO amount of computation (quantum
or otherwise), can recover the secret.

In particular, Lagrange Interpolation (over a finite field) can
be constructed for *every* different set of bits, so if you get
one bit wrong, you'll get the wrong answer, which isn't related to
the right answer in any way that a computer (quantum or otherwise)
can compute.

Google the Wikipedia entry.

There are many other problems with this scheme, but quantum computing
isn't one of them.

I have long advocated using Shamir Secret Sharing for storing portions
of a database in N different countries, where the portion and the
countries are carefully chosen to minimize the possibility of
"rubber hose"/warrant-maybe/extradition attacks on the cloud providers
in each of the N countries.  I'm kinda amazed that this isn't already
being done -- perhaps because it is difficult to find non-AWS,
non-Microsoft cloud providers in enough different countries.