Special talk by Andrej Bogdanov on Local randomness versus global structure in cryptography and complexity
Info about event
Time
Location
5335-295 Nygaard
Secret sharing schemes are at the heart of cryptography. They can be modelled as a collection of distributions that are locally indistinguishable but globally structured. Using this probabilistic perspective, which is complementary to the usual algorithmic one, I will present the following results:
* The share size in the threshold secret sharing scheme of Shamir and Blakley from the 1970s is essentially optimal.
* Secret reconstruction can be carried out in the computational model of bounded-depth circuits, without resorting to linear algebra.
* The security of schemes with symmetric shares degrades gracefully in terms of coalition size (in contrast to linear-algebraic constructions which exhibit a sharp threshold).
The proofs are based on new connections of secret sharing to approximation theory and zero-sum games.
I will also discuss some related results on security of private circuits against global leakage, the complexity of small-biased sets, and the relation between hardness and (pseudo)randomness for sparse random linear equations with noise.