Crypto Seminar

Thursday, September 8, 2022 - 12:00pm to 1:00pm

Location:

In Person Watch Group and Virtual - ET Belloch-Skees Conference Room, Gates Hillman 8115 and Zoom

Speaker:

BENNY APPLEBAUM, ProfessorSchool of Electrical EngineeringTel-Aviv University http://www.eng.tau.ac.il/~bennyap/

Secret Sharing, Slice Formulas, and Monotone Real Circuits

A secret-sharing scheme allows to distribute a secret among n parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about it. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $2^{n-o(n)}$ and until recently no better scheme was known. Exciting recent developments, starting with the work of Liu and Vaikuntanathan (STOC 2018), have significantly reduced the share size accumulating in an upper bound of 1.5^{n+o(n)} (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of $2^{n^{1-\epsilon}} for some constant \epsilon>0, or even all the way down to polynomial upper-bounds.

In this talk, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) — a computational model that was introduced by Pudl\'{a}k (J. Symb. Log., 1997) in the context of proof complexity. We use this connection to obtain lower bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC of complexity 1.5^{n+o(n)}. To the best of our knowledge, this is the first improvement over the trivial 2^{n-o(n)} upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.

Based on joint work with Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. The Crypto Seminar is generously sponsored by Smart Contract Research Forum. In Person Group Viewing and Zoom Participation.

Event Website:

https://sites.google.com/view/crypto-seminar/home

For More Information, Contact:

Keywords:

Seminar Series