EE Seminar: The Meta-complexity of Secret Sharing
הרישום לסמינר יבוצע באמצעות סריקת הברקוד למודל (יש להיכנס לפני כן למודל, לא באמצעות האפליקציה)- הרישום מסתיים ב- 15:10
Registration to the seminar will be done by scanning the barcode for the Moodle (Please enter ahead to the Moodle, NOT by application)- Registration ends at 15:10
Electrical Engineering Systems Seminar
Speaker: Oded Nir
Ph.D. student under the supervision of Prof. Benny Applebaum
Wednesday, 28th May 2025, at 15:00
Room 011, Kitot Building, Faculty of Engineering
The Meta-complexity of Secret Sharing
Abstract
A secret-sharing scheme allows the distribution of a secret s
among n
parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets is defined by a monotone function f: 0,1n→ {0,1}
. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size, S(f)
, serves as a natural complexity measure.
In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f
, is it possible to efficiently distinguish between cases where the secret-sharing complexity of f is small versus large? We examine this question across several computational models, including formulas, circuits, truth-tables, and graphs. Our results rule out the existence of instance-optimal secret-sharing compilers for formulas and reveal new connections between graph secret-sharing and questions in communication complexity.
