Aarhus University Seal / Aarhus Universitets segl

Special talk by Andrej Bogdanov on Local randomness versus global structure in cryptography and complexity

2019.03.25 | Marianne Dammand Iversen

Date Fri 05 Apr
Time 09:00 10:00
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.

CS frontpage, Featured, Public/media