多项式环上的广义Mülette模秘密共享方法与中国剩余定理相关

理论计算机科学电子笔记186（2007）43-48www.elsevier.com/locate/entcs多项式环上的广义MültteTatyana Galibus1白俄罗斯国立大学白俄罗斯明斯克Genadii Matveev2白俄罗斯国立大学白俄罗斯明斯克摘要本文在多项式环上推广了Mittette模秘密共享。Meclette提出了整数环上的门限秘密共享我们延长他的方法环的多项式这是欧几里德以及因此允许使用中国剩余定理。特别是，我们证明了任何访问结构可以实现这种模块化的方法。进一步，我们给出了具有相同次数模的秘密共享方案的参与者数目的界最后估计了新方案的信息率。关键词：接入结构，中国剩余定理，互质多项式，欧氏环，Mülette秘密共享，模秘密共享，份额，门限。1引言秘密共享的概念最初是由Shamir [8]引入的，它是一种将秘密值分成份额的数学方法后来，Asmuth，Bloom [1]和Mittette [6]基于整数环上的中国剩余定理，独立地此外，Asmuth和Bloom建议使用欧氏环而不是整数环所有提到的方法都处理阈值秘密共享，即t个参与者中不少于k个的所有子集都可以计算秘密。1电子邮件地址：galibus@bsu.by2电子邮件：matveev@bsu.by1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.04444T. Galibus，G.Matveev/Electronic Notes in Theoretical Computer Science 186（2007）43最近，人们注意到，一些不同于阈值结构的其它存取结构可以借助于由Iftene [4]引入的所谓广义Mittette序列模块化地实现特别是，他提出了所谓的划分秘密共享的模块化实现。本文提出了多项式环Fq[x]上的Mittette秘密共享，其中Fq是素数阶的Galois场. 我们表明，它可以用来实现任何给定的访问结构。实际上，我们构造了相应的Mittette序列。此外，我们认为Mittette序列的多项式的相等程度的最接近的可能的模。这个属性对于秘密共享是重要的（例如，参见[3]）。我们给出了该序列长度的上界，即等模秘密共享方案的参与者数目最后，在最重要的q= 2的情况一般存取结构的2Meclette介绍了他的门限秘密共享方法。让我们给出一些更一般的定义。设P={x1，x2，...，Xt}是秘密共享方案的参与者的集合。 我们说，如果来自A的参与者被授权，可以计算出这个秘密。设Γ是P中所有授权子集的集合。又设Γ是单调的，即A∈Γ，A<$B<$B∈Γ.然后我们说Γ是P上的一个存取结构。特别地，阈值访问结构由Γ ={B P ||B|≥ k}。Iftene模块化实现的分区存取结构为：||一|≥K，|A Cj|其中K是全局阈值，C1，C2，.，Cm是P划分为隔室和k1，k2，.，KM是对应的隔室阈值的集合。模秘密共享的基础是Z上的中国剩余定理，该定理在Fq[x]上也成立。因此，我们可以为多项式构造类似的Mittette方案。众所周知，如果同余S（x）≠s1（x）（mod m1（x）），.，S（x）≠sk（x）（mod mk（x））在F上q [x]是可解的，则它具有模LCM（m1（x），...， mk（x））。作为一项规则，剩余类代表最小程度的选择这样的解决方案。现在设每个参与者xi∈P具有某个一元多项式mi（x）∈Fq[x].我们将任意子集A∈P的模mi（x）的最小公倍数记为[mi（x）;i∈A]。设秘密度S（x）选自某个区间（M1，M2），M1degS（x）M2，其中M1，M2∈N，份额si（x）定义为si（x）<$S（x）（modmi（x））。<<定义2.1我们说存取结构Γ在环Fq[x]上有Mittette实现，如果存在多项式mi（x），i=1，t，使得（1）deg[mi， i∈A]>M2对于A∈/Γ，deg[mi， i∈A]M1对于A∈/ΓT. Galibus，G.Matveev/Electronic Notes in Theoretical Computer Science 186（2007）4345我们还说多项式序列mi（x）是访问结构Γ的广义多项式Mittette序列。这个定义推广了Mittette显然，在给定的条件下，任何授权子集A∈Γ都能计算出解同余系S（x）<$si（x）（modmi（x）），i∈A的秘密，而任何其它子集都不能.定理2.2任意存取结构在环Fq [ x ]上都有Mültte模实现.证 据 让 我 们 首 先 选 择 多 项 式 m1 （ x ） ， m2 （ x ） ， . ， mt （ x ） 等 于 1 。NowweshaallconnsidedersomemaimalunauthorizedsubsetA∈/r （ 其 中 它被视为包含，即没有其他未授权子集包含它的子集）。 所有模不属于A的参与者，则乘以某个不可约幺半群p1（x）∈Fq[x]。因为我们可以选择任意次数的p1（x），那么在相乘之后，我们可以得到以下满足的条件：deg [mi（x），i∈A] deg [mi（x），i∈B]，对于任何授权子集B。<如果我们选择另一个最大值，这个条件也成立错误的未授权子集，并对不可约幺半群执行相同的操作p2（x）p1（x）.因此，在对所有最大未经授权的我们最终得到给定访问结构Γ的实现。为了得出结论，仍然需要选择秘密S（x），使得M1≤degS（x）M2，其中M1是属于未授权子集的模的LCM的最大度，M2是属于未授权子集的模的<属于授权子集。Q我们注意到，用两两互素多项式代替不可约多项式更为方便。在大多数情况下，对于互质多项式，在2.2中得到的多项式的次数环Fq[x]中的3个现在我们将证明，使用环Fq[x]可以使我们构造具有更好机会的Mittette序列。在这个环中，我们可以选择相同次数的模，即具有相等欧几里德范数的模。唯一的条件是模必须互质。注3.1设m1（x），m2（x），.，mt（x）是相同次数n的成对互质多项式的集合。 可以很容易地证明，这个集合是一个实现了t个参与者的所有阈值访问结构的Mittette序列：（1，t），（2，t），.，（t，t）。阈值的大小取决于秘密的程度。事实上，度可以从任何数值区间中选择：（n，2 n），（2 n，3 n），.，（（t−1）n，tn）.此外，这组多项式可以用于生成广义46T. Galibus，G.Matveev/Electronic Notes in Theoretical Computer Science 186（2007）4322martette序列的任何访问结构，不超过t个最大未授权子集。不可约多项式显然是互质的。设Fq[x]中的一元n次不可约多项式的个数为Nq（n）.Nq（n）的著名公式是（二）1ΣNq（n）=nnμ（d）qdD |n其中μ（d）是一个多目标函数[5]。利用Cq（n）从固定次数n的Fq[x]中导出了一个两两互素的多项式的最大现在我们来计算Cq（n）的值，但首先我们需要一个技术上的结果。我们不能给出下面引理的参考，所以我们给出它的证明引理3.2函数Nq（n）在n上严格递增，对任意自然数q，n，除了当它从n = 2开始严格增加时的情况q = 2，3。证据 由（2）可知，1nqn−q1nqn−q因此Nq（n）≥n（q-q−1），Nq（n）≤n（q+）q−11N（n+ 1）−N（n）≥（qn+1（nq−3n− 1）+（2n + 1）q）>0q qn（n+ 1）（q−1）对于每个q >3，因为nq >3n- 1。 其余情况需要更精确的估计，Nq（n）：n1nq[2]+1−qn1nq[2]+1−q如果q= 2，Nq（n）≥n（q−q−1），Nq（n）≤n（q+）q−11n[n+1]+1nN2（n+1）−N2（n）≥n（n+1）（（n−1）2-n22-（n+1）2[2]+1+2n + 2）>0从n= 5开始。对于1 log （2kn2n）=kn + n> 2，k，n∈ NQBenaloh和Leichter [2]设计了另一个著名的基于单调电路结构的一般访问结构的秘密共享方案它具有与[9]中本文不研究所构造的Mechtette秘密共享方案的完备性完备性可以用信息量或秘密值的广义熵与条件熵之差的对数来度量。在基本的Meclette方案的情况下，这种估计不是很好。然而，可以在Fq[x]上构造Asmuth-Bloom多项式秘密共享方案，即选择秘密值模p（x），其中p（x）是附加模。在这种情况下，信息量以及信息速率可以具有良好的估计，即该方案接近完美的理想方案。一种常见的方法是尽可能接近地使用互质模来实现完美性和理想性的最佳估计[3]。在多项式的情况下，上述估计可以得到相当大的改进，因为我们采用了对数字不可能的相等次数的模这48T. Galibus，G.Matveev/Electronic Notes in Theoretical Computer Science 186（2007）43研究是我们进一步工作的一个主题。事实上，我们在会议结束后完成了这项研究。我们利用Quisquater，Preneel和Vanderwalle的技巧证明了多项式模格式是完美的和理想的。这些作者重新讨论了整数环上模方案的安全性，并证明了它只是渐近安全的。4致谢我们感谢ICS研讨会的匿名评审，他们的宝贵意见有助于发现和纠正不准确和不清楚的问题。感谢N。Shenets帮助我们改进引理3.3的证明。引用[1] 阿斯穆特，CA，和J.Bloom，A modular approach to key safeguarding，IEEE Transactions onInformation Theory。29（1983），156[2] Benaloh，J.，和J.Leichter，广义秘密共享和单调函数，计算机科学讲义。403（1990），27[3] Goldreich，O.，D. Ron和M.苏丹，中文错误处理，IEEE信息论汇刊。46（2000），1330[4] Iftene，S.， 基于CRT的分隔秘密共享，密码学ePrint档案408（2005），网址：http://eprint.iacr.org/2005/408.pdf[5] 利德尔河，和H. Niderraiter，[6] Mittette，M.，如何分享一个秘密，计算机科学讲义。149（1983），371[7] Quisquater，M.，Preneel，B.，Vandewalle，J.，基于中国剩余定理的门限方案的安全性，计算机科学讲义。2274（2002），199-210。[8] Shamir，A.， 如何分享一个秘密，ACM的通信。22（1979），612-613.[9] Stinson，D.R.，“Cryptography: theory and practice,” CRC Press, Boca Raton, Florida,