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 pr...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2025-04-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | https://www.math.md/files/csjm/v33-n1/v33-n1-(pp113-129).pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1561-4042 2587-4330 |