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

《六人参与的超图存取结构的复杂性》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Des.CodesCryptogr.(2013)67:169–173DOI10.1007/s10623-011-9592-z六人参与的超图存取结构的复杂性MotahharehGharahi·MassoudHadianDehkordi2011 / 18接收：九月修订：29十一月2011十一月2011/ 29 /接受：发表于：十二月2011 21©施普林格科学+商业媒体，LLC 2011摘要：在本文中，我们研究了确定参与者人数为6的复杂的5个超图访问结构复杂性的精确值，这在Dijk的论文（DES的代码cryptogr 6:143–169，1995）中仍然是一个开放问题。我们

2、证明了这5个超图每个访问结构的复杂性是等于7 /4。关键词：完美的秘密共享方案;复杂性;熵方法数学主题分类（2000）94A62·94A171引言秘密共享方案是一种方法，它允许一个秘密在一个集合参加者进行共享，在这样一种方式下，参与者的预定义的授权子集可以运用他们所掌握的份额重建秘密。这个秘密共享方案被称为是完善秘密共享方案，如果非授权子集的参与者不能获得关于秘密的任何信息。是存取结构的所限定能够重建这个秘密的所有子集的集合，它应该是单调的，即任何包含这个集合的集合都是授权子集。存取结构的最小授权子集称为极小授权子集，记为。一个秘密共享方案的复杂性在于中获得份额最大的参

3、与者的份额与任何其他参与者份额的比的大小。存取结构的复杂性，记为，被定义为存取结构的所有秘密共享方案的复杂性的下确界。一组参与者集合为的图存取结构是包含基数只有两个最小授权子集的访问结构，在对图存取结构的复杂性问题的讨论上，已发表出多篇论文，例如[1—4,8—10]vanDijk研究了6人参与的112个图存取结构一共94例的复杂性，确定了复杂性的精确值.[10]在本文中，我们考虑确定的图访问结构，，，和的复杂性的精确值的问题。这个问题在vanDijk’s的论文中没有得到解决。在参考文献[10]中，vanDijk论证了对于对于以及。随后在文献[9]中，Sun和Chen论证

4、后将和的上界提至到了。将的上界提至了。近期，Padró和Vázquez提出了图存取结构，，和的复杂性的下界为，运用的是线性规划的方法[7]。在本文中，我们给出这些问题的简单论证方法。我们的方法的主要新颖之处在于引用了一般的引理，这使得我们证明hand-checkable，并独立于任何计算机计算。除此之外，通过使用这个引理，我们对存取结构复杂性下界进行了改进，由变成了，并且在文献[9]中得到了验证。我们也希望这个引理能够引申出其他的问题。我们对提出一种新的分解，使得的复杂性的上界从变到。确定了这个存取结构复杂性的精确值。2定义和基本性质在[4]中，我们将利用熵[1]来定义

5、完美的秘密共享方案考虑两组随机变量 X和Y中，熵函数 H，满足下列性质：正定性：单调性：如果，则子模性：设是参与者的一个子集，我们用表示参与者所获得的份额的熵。令是参与者集合定义的一个存取结构。的一个完善秘密共享方案共享一个秘密，其中参与者集合为满足：（a），对于任何参与者的授权子集。（b），对于任何参与者的非授权子集。本文所讨论的所有秘密共享方案都是完善的。存取结构的复杂性定义为，其中下界取遍所有的秘密共享方案，代表实现存取结构的秘密共享方案。对于每一个重要参与者，[4]所以。访问结构的复杂性等于1被称为理想的访问结构。图访问结构的所有的最小授权的子集恰有两个不同的参

6、与者。当存取结构是基于一个（连通的）图，然后参与者和最小授权子集恰好对应图的顶点和的边。定理1[3]是基于连通图的一个理想的存取结构，当且仅当图是一个完全多划分图[2]。为了获得访问结构的复杂性下界，我们运用如文献[1]中所描述熵值法。我们运用文献[8]中的Stinson’s理想分解定理，并且获得了上界。如下所示。令存取结构的最小授权子集是，的一个理想分解满足一下条件：1、，其中2、3、对于由参与者的子集组成的存取结构，基是理想的。定理2[8]令是个参与者的一个子集，存取结构的基为，对于，假设是存取结构的一个理想分解，其中表示访问结构的参与者的集合。定义：则3结果这一部

7、分的目的在于要确定对于参与者的集合的下面图存取结构复杂性。（1）我们注意到我们利用线性规划的方法所求出的，，和的复杂性的下界也是和文献[7]中得出的结果一致。在这里，我们提出一个一般的引理（引理4），然后可以用来建立报道，下界独立于其他任何的计算机计算。 首先，我们声明如下事实这将在本部分中使用。事实3[6]设是参与者的集合，是上的存取结构，则有：如果并且则如果但则现在我们证明如下引理，它将在我们需要它得到复杂性下界的时候被运用到。引理4 设是参与者的集合，是上的存取结构，满足并且，则有（2）证明由事实1，我们得到由的子模性，我们得到将上