六人参与的超图存取结构的复杂性.docVIP

Des. Codes Cryptogr. (2013) 67:169–173 DOI 10.1007/s10623-011-9592-z 六人参与??的超图存取结构的复杂性 Motahhareh Gharahi · Massoud Hadian Dehkordi 2011?/?18接收：九月修订：29十一月2011十一月2011 /?29?/接受： 发表于：十二月2011?21 ?施普林格科学+商业媒体，LLC?2011在本文中，我们确定参与者复杂的访问结构的精确值，这Dijk的论文（DES的代码cryptogr?6:143–169，1995）仍然是开放问题。我们证明了等于7?/ 4。关键词完美的秘密共享方案复杂性熵方法数学主题分类（2000）94A62·94A17 1引言秘密共享方案是一种方法，它允许一个秘密一个集合参加者共享，在这样一种方式，参与者的预定义的子集可以重建。是存取结构的所限定重建的所有子集的集合，应该是单调的，即的最小授权子集称为极小授权子集，记为。 一个秘密共享方案中获得份额最大的参与者的份额与任何参与者的大小的复杂性，记为，被定义为存取结构的所有秘密共享方案的复杂性的下确界。 一组参与者集合为的图存取结构是包含基数只有两个最小授权子集的访问结构，在对图存取结构的复杂性问题的讨论上，已发表出多篇论文，例如[1—4,8—10] van Dijk研究了6人参与的112个图存取结构一共94例的复杂性，确定了复杂性的精确值.[10] 在本文中，我们考虑确定的图访问结构，，，和的复杂性的精确值的问题。这个问题在van Dijk’s的论文中没有得到解决。在参考文献[10]中，van Dijk论证了对于对于以及。随后在文献[9]中，Sun和Chen论证后将和的上界提至到了。将的上界提至了。近期，Padró和Vázquez提出了图存取结构，，和的复杂性的下界为，运用的是线性规划的方法[7]。在本文中，我们给出这些问题的简单论证方法。我们的方法的主要新颖之处在于引用了一般的引理，这使得我们证明hand-checkable，并独立于任何计算机计算。除此之外，通过使用这个引理我复杂性下界变成了，并且在文献[9]中得到了验证。我们也希望这个引理其他的问题提出一种新的分解，使得的复杂性的上界从变到。确定了这个存取结构复杂性的精确值。 2定义和基本性质 我们将利用熵定义完美的秘密共享方案考虑两组随机变量?X和Y中，熵函数?H，满足下列：设是参与者的一个子集是参与者集合定义的一个存取结构。的一个完善秘密共享方案共享一个秘密，其中参与者集合为满足： （a），对于任何参与者的授权子集。 （b），对于任何参与者的非授权子集。 本文所讨论的所有秘密共享方案都是完善的。存取结构的复杂性定义为，其中下界取遍所有的秘密共享方案，代表实现存取结构的秘密共享方案。对于每一个重要参与者。访问结构复杂性等于被称为图最小的子集有两个不同的参与者。当结构是基于一个（连的）图的顶点和的边。 定理1是基于连通图的一个理想的存取结构，当且仅当图是一个完全多划分图[2]。 为了获得访问结构的复杂性下界，我们运用如文献[1]中所描述熵值法。我们运用文献[8]中的Stinson’s理想分解定理，并且获得了上界。如下所示。 令存取结构的最小授权子集是，的一个理想分解满足一下条件： 1、，其中 2、 3、对于由参与者的子集组成的存取结构，基是理想的。 定理2的基为，对于，假设是存取结构的一个理想分解，其中表示访问结构的参与者的集合。定义： 则 3结果 的下面图存取结构复杂性。 （1） 我们注意到我们利用，，和的复杂性的下界也是和文献[7]中得出的结果一致。在这里，我们提出一个一般的引理（引理4），然后可以用来建立报道下界独立于任何计算机计算?首先，我们声明如下事实这将在本部分中使用。事实3是上的存取结构，则有： 如果并且则 如果但则 现在我们证明如下引理在需要时候。引理4?是上的存取结构，满足 并且，则有 （2） 证明 由事实1，我们得到 由的子模性，我们得到 将上面所有不等式两边相加，我们得到需要的结果（2）。 作为一个直接的我们有以下推论5是上的存取结构，满足 并且，则有