[Cryptography] composing EC & RSA encryption?

[Jerry Leichter]

> While we're having fun here [2], one more:  Adi Shamir's secret sharing is supposed to be information theoretic secure - not just computationally secure.  Is there mileage here?  How does it perform against QC?
It *is* information-theoretically secure.  In sketch:  The secret is the value at 0 of  an k'th degree polynomial.  The secrets are p(1), p(2), ..., p(n).  If you have any k of the p(i)'s, you can determine p and hence p(0).  If you have k-1 values, you can take any value you like for the k'th value and get a different value for p(0).

If you do this over the integers or the rationals or the reals (or even over the complex plane, I suppose), some information may leak because the sizes of the numbers are likely bounded.  So you do it over Z/p for some large enough p, and all values are equally likely.

Adding quantum computation changes nothing at all since the problem isn't in computing the missing value - it's that any possible value is equally likely.

Shamir's scheme implements threshold secrets:  Any subset of k shares gives you the secret, any small subset gives you nothing at all.  Josh Benaloh and I showed many years ago that you could implement any secret sharing scheme that made sense (e.g., any share from collection A and any share from collection B).  The secrets are bigger, but the computation is pretty much as simple and the security remains information-theoretic.  There's a scanned copy at http://www-bcf.usc.edu/~shanghua/teaching/Fall2015-476/BenalohLeichter.pdf

                                                        -- Jerry