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.
翻译:双部分秘密共享计划具有双部分共享结构,参与者组分为两部分,所有参与者在同一部分中都发挥同等的作用。 这种双部分计划可以用“ 楼梯” 来描述: 收集其最小点 。 一个计划的复杂性是相对于秘密大小的最大份额大小; 一个结构的$kappa$- 复合性是 entropy 方法提供的最佳较低约束。 一个结构是 $\ kappa$- complical, 如果它有 $\kappa$- complility, 结构是 $\ kappaa$- oprial- ideal- complility 。 受此领域大量公开的直观问题驱动, 主要结果可以概括如下。 首先, 对 $\ kappappa $- ideal- 多部分访问结构的新定性, 提供了一种简单和简单的方法来指定理想的双部分和三方结构 。 其次, $\ kappappa- concretile 结构, 由两个点确定, 以等宽和高度为一定的直径的直径直径的直径, 结构, 其中所有的直径的平为直径的直径的直径, 直为直为直为直为直方, 。