[Cryptography] composing EC & RSA encryption?
Jerry Leichter
leichter at lrw.com
Wed Oct 28 21:38:56 EDT 2015
> 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
More information about the cryptography
mailing list