Volume 14, Issue 2 (7-2014)
2014, 14(2): 97-114 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Cheraghi A. Determining the Optimal Complexity of Bipartite Access Structures. Journal title 2014; 14 (2) :97-114
URL: http://jsci.khu.ac.ir/article-1-1722-en.html
URL: http://jsci.khu.ac.ir/article-1-1722-en.html
Assistant professor
Abstract: (5457 Views)
Determining the Optimal Complexity of Bipartite Access Structures
Abbas Cneraghi
Abstract
Keywords: Complexity, Secret Sharing Scheme, Access structure.
In a bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padro and Saez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal complexity of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal complexity. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, a lower bound on the complexity. Moreover, we show new optimal constructions for certain bipartite access structures.
Abbas Cneraghi
Abstract
Keywords: Complexity, Secret Sharing Scheme, Access structure.
In a bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padro and Saez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal complexity of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal complexity. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, a lower bound on the complexity. Moreover, we show new optimal constructions for certain bipartite access structures.
Send email to the article author
| Rights and permissions | |
 | This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
