Bipartite secret sharing and staircases

DOI10.1016/J.DISC.2024.113909MaRDI QIDQ6124455zbMATH OpenOpenAlexFDO

Authors László Csirmaz, František Matúš, Carles Padró

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.04904

zbMATH Keywords

cryptographyentropy methodlinear secret sharingmultipartite secret sharingsubmodular optimization

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: Bipartite secret sharing schemes have a bipartite access structure in which the set of participants is divided into two parts and all participants in the same part play an equivalent role. Such a bipartite scheme can be described by a "staircase": the collection of its minimal points. The complexity of a scheme is the maximal share size relative to the secret size; and the $kappa$-complexity of a structure is the best lower bound provided by the entropy method. A structure is $kappa$-ideal if it has $kappa$-complexity 1. Motivated by the abundance of open problems in this area, the main results can be summarized as follows. First, a new characterization of $kappa$-ideal multipartite access structures is given which offers a straightforward and simple approach to specify ideal bipartite and tripartite structures. Second, $kappa$-complexity is determined for a range of bipartite access structures, including those determined by two points, staircases with equal widths and heights, and staircases with all heights 1. Third, matching linear schemes are presented for some non-ideal cases, including staircases where all heights are 1 and all widths are equal. Finally, finding the Shannon complexity of a bipartite access structure can be considered as a discrete submodular optimization problem. An interesting and intriguing continuous version is defined which might give further insight to the large-scale behavior of these optimization problems.

Recommendations

• On the Optimization of Bipartite Secret Sharing Schemes
• Secret sharing on regular bipartite access structures
• scientific article; zbMATH DE number 1303145
• Secret sharing schemes with bipartite access structure
• On the optimization of bipartite secret sharing schemes

Cites work

• A FORBIDDEN MINOR CHARACTERIZATION OF MATROID PORTS
• A Solution of the Shannon Switching Game
• Classes of matroids closed under minors and principal extensions
• Conditional Independences among Four Random Variables I
• Conditions for representability and transversality of matroids
• How to share a secret
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3468904 (Why is no real title available?)
• Ideal multipartite secret sharing schemes
• On secret sharing schemes, matroids and polymatroids
• On the optimization of bipartite secret sharing schemes
• Online submodular minimization
• Optimal Information Rate of Secret Sharing Schemes on Trees
• Secret sharing on the \(d\)-dimensional cube
• Secret sharing schemes with bipartite access structure
• Secret-Sharing Schemes: A Survey
• Submodular functions and optimization.
• The size of a share must be large
• Theory of Cryptography
• Tight bounds on the information rate of secret sharing schemes

Cited in

(1)

• A comprehensive review of graph theory applications in secret sharing schemes

This page was built for publication: Bipartite secret sharing and staircases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6124455)