基于中国剩余定理的分组秘密分享

1基于中国剩余定理的分组秘密共享SorinIftene计算机科学系亚历山德鲁杨库扎大学雅西,罗马尼亚[e-mail]摘要一个秘密共享方案开始于一个秘密和它导出的分配给用户的某些秘密共享（或份额）.这个秘密可能只有通过某些预定群组才能被找回.就分组秘密共享而言,用户的设置可以被划分成组,只有当来自分组的参与者数量比固定的门限大而且全部的参与者数量比整体的门限大事,秘密可以恢复.在这篇论文中,通过拓展Blakley的结构[4],我们提出了一个新的分组秘密共享方案,它的整体门限是严格大于分组门限,未来降低共享的规模,我们指出了怎么样运用基于中国剩余定理的门限秘密共享.美国数学学会科目分类:94A62,11A07关键字:秘密共享,分组共享结构,中国剩余定理1说明和序言一个秘密共享方案开始于一个秘密和它导出的分配给用户的某些秘密共享（或份额）.这个秘密可能只有通过某些预定群组才能被找回.初始的秘密共享应用是用于保护密钥和防止共享接近战略资源.门限密码术（见例[7]）和一些电子投票方案（见例[6]）是秘密共享方案更近的应用.在第一个秘密共享方案中,只有在重组阶段的参与者数量对恢复秘密是重要的.2这种方案被称为门限秘密共享方案.我们提到的Shamir的基于多项式差值的门限秘密共享方案,Blakley的几何门限秘密共享方案,Mignotte的门限秘密共享方案和Asmuth-Bloom的门限秘密共享方案,都是基于中国剩余定理的.Ito,Saito,Nishizelki[14],Benaloh和Leichter[2]对一般的秘密共享方案提出了解释.就分组秘密共享而言,这个秘密可能只有通过某些预定群组才能被找回.就分组秘密共享而言,用户的设置可以被划分成组,只有当来自分组的参与者数量比固定的门限大而且全部的参与者数量比整体的门限大事,秘密可以恢复.在这篇论文中,通过拓展Blakley的结构[4],我们提出了一个新的分组秘密共享方案,它的整体门限是严格大于分组门限,未来降低共享的规模,我们指出了怎么样运用基于中国剩余定理的门限秘密共享.这篇论文的组织如下.剩下的部分描述一些数论序言,集中研究中国剩余定理.在第2部分,简单地介绍秘密共享之后,我们提出基于中国剩余定理的门限秘密共享方案.在第3部分,我们指出怎样运用基于中国剩余定理的门限秘密共享方案理解分组秘密共享.在最后一个部分总结论文.在余下的部分,我们提出一些数论的基本论据.更多的详细资料,读者可以查阅[5].使Zba,,被ab整除的商表示为adivb,余数表示为amodb.使Zaan,1,则有0121naa.naa,1的最大公因数gcd被表示为naa,,1.使Zaan,,1,则有01naa.naa,1的最小公倍数lcm被表示为],,[1naa.使Zmba,,.我们称ba,以m为模式同余的,且记为mbamod,当m|)(ba.mZ表示}1,,1,0{m.中国剩余定理在计算机科学方面有很多应用(见例[8]).我们仅提由Quisquater与Couvreur[18]提出的基于中国剩余定理的RSA解密算法,Pohlig与Hellman[17]的离散对数算法,和在Mignotte[15]或Asmuth-Bloom[1]的门限秘密共享方案中的秘密恢复算法.一些基于中国剩余定理的看法被提出.接下来的这个叫做一般中国剩余定理.定理1使2k,2,,1kmm,方程组11modmbx3kkmbxmod在Z内有解当且仅当对于所有的i1,kj,有),mod(jijimmbb.而且,如果方程组在Z内有解,则它在],,[1kmmZ内有唯一解.对于所有的kji1,当1),(jimm,有人得到了一个中国剩余定理的标准形式.Garner[10]发现了一个一个有效地算法,而Fraenkel[9]则将这个算法拓展到情况.2基于中国剩余定理的门限秘密共享方案我们提出了关于秘密共享方案的第一批基本论据.假设我们有n个用户标记为n,,1,假设存在}),,2,1({npA,一个A-秘密共享方案是生成)),,(,(1nIIS,则有对于任意的A,找到集合iI{|}Ai的元素S是“容易”的.对于任意的}),,2,1({nA\,找到集合iI{|}Ai的元素S是很困难的.集合A被称为授权的访问结构或者简单地访问结构,S被称为秘密并且nII,,1被称为共享（或者S的份额）.集合中的元素被称为授权的群组.一个自然条件是访问结构是单调的,例如)))(}))((,,2,1({(BBAAnPB任何单调渐近结构是广受认同的最低群组的集合,例如,集合)})({\)({minABABAA.此外,未经授权的访问结构,\}),,2,1({nP是广受认可的最大群组的集合,例如,集合)}})({\({maxBAABA.一类非常重要的秘密共享方案是门限秘密共享方案.在这些方案中,只有共享集合的基数对于恢复秘密是重要的.更确切地说,如果所需的门限是k,nk2,则最小的渐近结构是})},,2,1({{minkAnPA.在这种情况下,秘密共享方案被称为秘密共享门限),(nk.我们简要地介绍了基于中国剩余定理的最重要的门限共4享方案.2.1Mignotte门限秘密共享方案Mignotte的门限秘密共享方案[15]使用的特殊整数序列,称为Mignotte序列.定义1设n是一个整数2n时并且nk2.),(nk,),(nkAn,Mignotte序列是一个有效的整数序列nmm1,对于任意的nji1,knknmmmm12,则有1),(jimm.给定一个),(nk-Mignotte序列,方案的运算如下:选择一个随机整数作为秘密S,有S,kmm1,nknmm2;对于任意的ni1,共享iI通过iI=imSmod得到;给定k不同的共享kiiII,,1,秘密S可以使用中国剩余定理恢复,作为方程组唯一的解模kkiimm.11modiimIxkkiimIxmod通过引入广义Mignotte序列,,提出了提出了Mignotte方案的概论不一定通过两两互质的模[13].定义2设n是一个整数,2n或nk2,广义),(nk-Mignotte序列是一个nmm,,1正整数序列,则有}]),,([{min}]),,([{max11111111kkkkiiiiiiniimmmm显然,任意),(nk-Mignotte序列是一个广义),(nk-Mignotte序列.而且,若使),(nk-Mignotte序列的每个元素乘以固定元素Z,1),(1nmm,可以得到一个广义),(nk-Mignotte序列.除了}]),,([{min111kkiiniimm和}]),,([{max11111kkiiniimm,广义Mignotte方案与Mignotte方案相同.此外,对于这种情况,一般中国剩余定理用于重新找回秘密.52.2Asmuth-Bloom门限秘密共享方案Asmuth和Bloom在[1]中提出的方案也用到了特殊的整数列.更确切地说选择一个两两互素道德正整数数列nmmr1,,有knknmmmmr12给出一个序列,他的方案作用如下:从集合rZ中取一个随机数作为秘密S;对于任意的ni1,当y是一个随机整数,iI=imrSmod)(,有kmmZrS1;给出k不同的共享ikiII,,1,密文S可以通过rxSmod0获得,当0x已知,使用标准中国剩余定理,当做方程组(1)以ikimm1为模的唯一解11modiimIx(1)ikikmIxmodAsmuth-Bloom方案中用到的数列可以通过允许用一个明显的方法得到的不必要互素的模推广.我们可以用任意序列nmmr,,1,则有}]),,([{min}]),,([{max11111111kkkkiiniiiiniimmmmr显然,如果使一个普通的Asmuth-Bloom序列除了r和一个Z,1),,,(1nmm相乘,我们得到一个推广的Asmuth-Bloom序列.门限秘密共享还讨论了在应用中剩余定理[12]和提出了一个基于中国剩余定理的单一的角度点的阈值安全秘密共享方案[19].虽然基于中国剩余定理的门限秘密共享方案并不完美1,但是通过精心选择参数,这些方案可能导出一个合理的因素共享规模安全.1在一个完美的秘密共享方案中,对未经授权的群组不提供(信息理论意义上)关于秘密的信息.63基于中国剩余定理的分组秘密共享就分组秘密共享而言,用户群被分成组,只有当来自任一分组的参与者数量大于一个固定的分组阈值和参与者总数大于整体阈值时,秘密才能恢复.分组访问结构可以表述如下:定义3},,,{21mCCCC是},,2,1{n的一个分区,假设分组阈值},,,{21mkkkK,当jjCk1时,对于任意的mj1,和一个整体阈值k,mjjnkk1,),,(kKC-分组访问结构有下式得到)}kCA)(m1,j(k)A(|}),,2,1({{jjnPA在这种情况下,一个-秘密共享方案被称为一个),,(kKC-分组秘密共享方案.第一次讨论分组秘密共享的人是Simmons[21].Brickell[4]通过选择S当做m分组密码中的密码组合,每个分组使用一个门限共享方案,对mjjkk1提出了一个简单的方法.Ghodosi,Pieprzyk和Safavi-Naini提出了一个一般情况下有效的方案.我们将Brickell的结构拓展到一般情况.-选择秘密Smsss1,msss,,,1是正整数.-选择),(iiicgI,对任意的ni1,当-ngg,,1是对应于关于一个随意的),(nk-门限秘密共享方案的秘密S的共享;-对于每个mj1,ic{|}jCi是对应于关于一个随意的),(jjCk-门限共享方案的秘密S的共享.备注1（正确性）A是一个授权访问组,因此kA,对于所有的mj,1,jjkCA则在ngg,,1中至少有一个k能得出s.对于任意的mj,1,则在ic{|}jCi中至少有jk7能得出js.最后,秘密S可以通过Smsss1得到.备注2（安全性）A是一个授权访问组,有两种可能:-在kA情况下,s不能被定义;-有一个分组j使得jjkCA,在这种情况下,js不能被定义.在以上两种情况下,秘密S不能重建.备注3假使mjjkk1,如果所有的分组门限条件成立则整体门限条件也成立.因此这部分的秘密可以删除,只有当iicI,共享可以选择,对于任意的ni1,从而获得Brickell结构.利用完善的门限秘密共享方案作为基石可以到处大量的共享.我们建议使用基于中国剩余定理的门限秘密共享方案,以减少共享大小、维护,同时,合理的安全水平.为简单起见,我们只处理Mignotte方案,但是我们必须提到,这项技术也可以应用于Asmuth-Bloom方案.示例1人工小参数假设6n,}}6,5,4{},3,2,1{{C,分组阈值11k,22k,整体阈值5k.数列19,17,13,11,7,5是一个)6,5(-Mignotte数列,有85085,46189,数列13,11,7是一个)3,2(-Mignotte数列,有77,13.选择50000s,301s,402s,则秘密是50070S,共享是)1,11(),7,3(),5,2(),4,5(),8,6(),2,0(654321IIIIII有了共享)1,11(),7,3(),5,2(),4,5(),8,6(),2,0(654321IIIIII,我们就可以解决方程组8