Secret Sharing Limitations Over Boolean Circuits

This paper offers a gentle introduction into the realm of monotone span programs and their connection with linear secret sharing schemes and attribute-based encryption while emphasizing the cryptographic importance of finding efficient MSPs for representing complex access structures. We provide a proof that there is no ideal LSSS for Boolean circuits, thus tackling the open problem of finding LSSSes of non-exponential size for Boolean circuits. Moreover, we present an application of our proof to graph access structures and a backtracking approach to finding efficient MSPs for given access structures.