一种动态多秘密共享方案

第９卷第７期　２０１０年７月　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　Ｖｏ１．９　ＮＯ．７　Ｊｕ１．２Ｏ１Ｏ　一种动态多秘密共享方案　唐淑萍　（亳州师范高等专科学校计算机系，安徽亳州２３３５００）　摘　要：提出了一种新的基于椭圆曲线密码体制的（ｔ，ｎ）动态秘密共享方案。该方案具有以下特点：参与者能自主选　择子密钥；在进行一次秘密恢复后，不会泄露关于子密钥的任何信息，子密钥仍可用恢复于下一个共享的秘密；参与　者的子密钥可定期更新，且更新工作由每个参与者独立完成。与传统的多秘密共享方案相比．该方案具有更高的安　全性和灵活性　关键词：秘密共享；椭圆曲线密码体制；多秘密共享；子密钥　中图分类号：ＴＰ３０９　文献标识码：Ａ　文章编号：１６７２—７８００（２０１０）０７—０１４５—０３　作由每个参与者独立完成，参与者可以随时更新自己的子密　０　引言　秘密共享是密码学的重要组成部分。它在重要信息和秘密　钥，并且对其他参与者子密钥对共享秘密的有效性不会产生任　何影响；子密钥可以多次使用，在进行一次秘密恢复之后不会　泄露关于参与者子密钥的任何信息．仍可用于下一个秘密的恢　复；该方案同时还提供了防欺诈的功能。　数据的保存、安全传输及合法利用中起着非常重要的作用。　１９７９年，Ｓｈａｍｉｒ和Ｂｌａｋｌｅｙ分别独立提出了（ｔ，ｎ）门限秘密共享　方案．其思想是将一个秘密分成ｎ份子秘密．通过秘密通道分　发给ｎ个参与者，ｎ个参与者中的任意ｔ个或多于ｔ个合作就　可以恢复该秘密，而少于ｋ个则无法恢复秘密。　秘密共享一经提出便得到了大量的研究．在Ｓｈａｍｉｒ秘密　共享思想的基础上，出现了很多类型的秘密共享方案：Ｋａｍｉｎ　１方案的构成　设椭圆曲线的基点为Ｇ，Ｇ点的阶为Ｎ；每个参与者Ｕ　（ｉ＝　１，…，ｎ）从（１，Ｎ）中随机选取一个整数Ｓｉ　ｃ　作为自己的子密钥，　参与者计算Ｐ。＝Ｓｉ　ｃ　Ｇ，并将Ｐ。和自己的编号Ｕｉ发送给秘密可　信中心ＴＣ；Ｋ。，Ｋ２，…，Ｋ　，为ｒ个待分发的秘密；Ｔ为更新周期　（Ｔ＝１，２，…），设初始时刻的时间为０，Ｆ　（）表示取纵坐标操　作，Ｆ　（）表示椭圆曲线上纵坐标和横坐标加和；ＮＢ为可信中心　提出了矩阵法构造的门限秘密共享方案：Ｂｅｎａｌｏｈ于１９８６年提　出同态秘密共享的概念：Ａｓｍｕｔｈ和Ｂｌｏｏｍ等对基于中国剩余　定理的门限秘密共享进行了研究；文献［３］提出了可验证的秘　密共享（ＶＳＳ），文献［４］提出了可复用子秘密的秘密共享。但是　在这些秘密共享方案中，参与者一次只能共享一个秘密，在实　ＴＣ管理的公告板，其信息对外公开。方案由秘密份额的产生、　子密钥更新和秘密恢复３个部分组成。　１．１秘密份额的产生　际应用中，当要共享多个秘密时，参与者需要保存多个秘密份　额，这样做的效率很低。为解决这个问题，文献［５］提出了多秘　密共享的概念。多秘密共享是指各参与者只需保存一个秘密份　额就可以实现多个秘密的共享。此后，文献［６］和文献［７］又分　别提出了基于单向函数的多秘密共享方案，与文献『５］相比效　率有了一定程度的提高。文献［８］基于系统分组码提出了一种　可信中心ＴＣ按如下步骤执行：　（１）在（１，Ｎ）之间随机选取一个整数Ｓ０，计算Ｐ０＝ＳｏＧ，并　检查是否存在Ｐｏ＝Ｐｉ，若存在则重新选择Ｓｏ　ＴＣ公布Ｐ０，Ｕｉ；　（２）计算ＳｏＰｉ＝（ｘ　⑨，ｙｉ。　），随机选取一整数ｄ∈（１，Ｎ），根据数　值对（０，ｄ），（Ｕ。，Ｙ　‘。　），…，（Ｕｎ，Ｙ　。　），构造ｎ次多项式：　（ｘ）＝　∑　ｘ　，并公布（ｄＧ）　Ｇ和ａ。　Ｇ（ｉ：１，２，…，ｎ），作为验证信息；　ｉ：０　（ｔ，ｎ）门限多秘密共享体制。但是这些方案中，每个参与者的子　秘密只能由秘密分发者选定，文献［９］提出了一种参与者可自　（３）随机选取３ｒ个互不相等的整数ｍ　，ｍ　，…，ｍ　，ｗ　，ｗ：，…，　ｗ　，ｗｒ＋】，ｗｒ＋２，…，ｗ２　∈ＺＮ，ｉｆ￣Ｇｊ＝ｗｉＧ，其中ｍ　与Ｋ，和Ｇ　相对应，计　算：　Ｔ，；Ｋ，一主选择子密钥的秘密共享方案，但该方案未实现子密钥的定期　更新。　本文基于椭圆曲线密码体制，提出了一种新的多秘密共享　方案。在该方案中，参与者可以自主选择子密钥；子密钥更新工　Ｆ　（ｍｄｃｊ）ｍｏｄＮ　（１）　并在ＮＢ上公布（ｍｊ，Ｔｊ，ＣＪ，Ｇｊ　）（ｊ＝ｌ，２，…，ｒ）。计算ｄＧ＇ｊ，ａ　基金项目：２０１０年高校省级自然科学研究项目（ＫＪ２０１０Ｂ１２３）　作者简介：唐淑萍（１９８３一），女，安徽砀山人，毫州师范高等软件学校助教，研究方向为网络与信息安全。　・１４６・　软件导刊　２０１０正　，　（Ｇｊ＝ｑ＋　）并在ＮＢ上公布验证信息ｄＧｊ，ａｌ　，ａｋ　（　＝ｌ，２，…，ｎ　＝Ｉ，２，…，ｒ；　＝ｔ，ｔ＋ｌ，…，ｎ）。　／　；ｉ　＝ｌｔ　ｚ　ｔ　器　。参与者根据自己的子密钥ｓ　。　和公开信息Ｇ＿可以计算出对　应秘密的秘密份额，Ｆ　（ｓｉ㈣Ｐ）Ｇ　为参与者Ｕ。对应的第Ｊ个秘密Ｋ　。的秘密份额（ｉ＝１，２，…ｎ；ｊ＝ｌ，２，…，ｒ）。　ｊ１．２　子秘密更新阶段　Ｇ　一ｕ　Ｊ］ｔ　ｌＸ－Ｕｍ　ｔ　一　，　ｔ　瓦ｘ－Ｕ　设在第Ｔ个周期参与者Ｕ：要更新子密钥：　（１）随机选取子密钥更新份额　，同时更新自己的子　，骞　。【＝Ｊ　Ｊ厂　ｎｒａｍ　ｍ　Ｊ　ｔ＝ｌ，ｍ　Ｕ≠ｌ　　，—Ｕ　。　　，（３）　因为参与者ｕ　在周期Ｔ一１时的子密钥为ｓ　（Ｔ－１）此时的秘密　整　：　（２）计算　＝　。　一　，Ｊｐ。）　；根据数值对（０，ｏ），（　，…，　（ｕｉ，０）（ｉ＝１，２，…，ｎ，ｉ≠ｊ），构造ｎ次多项式，参与者在第Ｔ个周期　的ｎ次更新多项式：　Ｉ　骞６　ｍ。　ｃ２　（３）计算验证信息　，　（Ｇ　＝　＋　＋　），然后发送ＴＣ。　ＴＣ收到参与者ｕｊ的验证信息后执行以下操作：计算ａ　ｉ　Ｇ　Ｊ＝　Ｇｉ＋　ｎ　Ｇ　ｉ，　Ｇ＿Ｉ　Ｇ　Ｊ＋　ｂ三Ｇｉ．然后在ＮＢ上修改验　证信息ａｉ　～Ｇ，ｉ和　Ｇ，。　１．３秘密恢复阶段　设在第Ｔ个周期ｔ个参与者参与共享秘密Ｋｊ的恢复。参与　秘密恢复的每个参与者Ｕ：按以下步骤恢复共享秘密Ｋｊ：　为不失一般性，假设参与共享秘密Ｋ的恢复的参与者为Ｕ　１Ｕ２…Ｕｔ。　（１）参与者ｕ。从公告板ＮＢ上获取（　，ｒＩ、ｊ，Ｇｊ，Ｇｊ＋　，ｄＧ　ｊ，ａｆ１］　，ａ　ｍＧ　（Ｇ　ｊ＝ｑ＋Ｇｉ＋ｒ），分别计算ｙｆＩ］＝　ｋ　Ｇ　，ｓ　ｍ　：（ｓ　）　，ｓ　ｍ”＝（ｓ　）　Ｇ０，　＝ｓ　一　相互交换ｓ　，ｓ　”；其他参与者通过等式　怕　＋∑（　）　ｃｎ　验证参与者ｕ，是否存在欺骗行为；　（２）将　个点做Ｌａｇｒａ　ｇｅ插值：（　。，　），（　，　），…，（ｕ　，ｚ　，则得到第Ｔ个周期的ｔ一１次多项式尸　Ｇ，：尸’　。由　Ｋ￣＝－Ｔｉ＋Ｆ　（ｍｊｄＧ￣）ｍｏｄＮ，则对应的秘密　被恢复。　证明：在第Ｔ个周期，参与者ｕ。子密钥为　己ｕｆ１］＝∑　；由ｙ　，ｓ　－－ｔ，（１）＝　＝　，　：　Ｐｎ）　Ｇｊ一　＝（ｓ（Ｉ’ｓ。Ｃ）　－ｕｆＪ］Ｇｊ＝　｛　一∑　；ｍ｝Ｇ＝ｉ（ｉ：１，２，…，１）　由ｔ个点（ｕ　，　），（ｕ　，ｚ　），…，（ｕ　，ｚ　）做拉格朗日插值，可以　计算得到第Ｔ个周期的ｔ．１次多项式：　多项式为：　。　）一ｄ＋ｎ（Ｔ－ｎ　。　１＋　＋…＋　Ｈ　ｍｏｄＮ　ｌ４）　由（２）和（３）可知，在第Ｔ个周期参与者子密钥更新后的秘　密多项式为：　尸　喜　＋喜　‘＋喜　‘＋．．・＋骞　三　ｄ一＋ａ　＋　，　＋　＋．＋…＋　．．＋　ｍｏｄ…Ｎ　（５））　　参与者ｕ．更新后的子密钥为：　，　由（３）和（５）得：（）　ｆＴ　ｌ　（Ｑ　ｌ　ｄＧ￣ｍｏｄＮ　、　由（１）和（６）　；　＋　／　ｆＤＪＪ　＋　ｆｍＪ　，　秘密　被恢复。　讦毕　２方案的分析　２．１方案安全－眭分析　下面讨论对本方案几种可能的攻击：　（１）攻击者试图通过参与者Ｕ；的子密钥影子Ｐｉ来获取子密　钥ｓ　ｉ，等价于求解椭圆曲线上的离散对数问题ＥＣＤＬＰ（Ｅｌｌｉｐｉｔｃ　Ｃｕｉ－ｖｅ　Ｄｉｓｃｒｅｔｅ　Ｌｏｇａｒｉｔｈｍ　Ｐｒｏｂｌｅｍ），这是非常困难的。　（２）在秘密恢复阶段，攻击者试图伪造秘密份额ｓ　给其他　的参与者，但必需满足等式　ｎ：　Ｇ　＋　（　）　，这等　价于求解椭圆曲线上的离散对数。　（３）攻击者试图通过参与者Ｕｉ的秘密份额　获取子密钥，　这同样等价于求解椭圆曲线上的离散对数问题。　（４）在子密钥更新阶段，攻击者试图通过参与者发送的验　证信息６　Ｇｔｊ，６　，：　＋　＋ｒＪ来获取参与者的子密钥，这等价　于求解椭圆曲线上的离散对数问题。　（５）如果攻击者已经获取了参与者Ｕ；的在周期Ｔ一１的子　密钥．但是没有获取第Ｔ个周期更新阶段子密钥更新份额６Ｊ　。　第７期　唐淑萍：一种动态多秘密共享方案　・１４７・　因此，无法获取更新后的子密钥。　以用于下一个秘密的恢复而无需重新分发：方案同时还提供了　（６）如果在某个周期参与者的子密钥被泄露，参与者可以　随时完成自己子密钥的更新而对其他参与者没有任何影响，其　防欺诈的功能．能有效地防止外部欺诈和内部欺诈等问题。因　此，本文提出的是一种更高效、更安全的多秘密共享方案。　参考文献　他参与者不必同步更新。因此，提高了安全性和效率。　２．２方案特点　（１）参与者可以自主选择子密钥，可信中心得到的只是参　与者的子密钥的影子。由子密钥的影子得到子密钥在计算上是　不可行的；当需要共享新的秘密时，可信中心只需要进行少量　【１］　ＳＨＡＭＩＲ　Ａ．Ｈｏｗ　ｔｏ　ｓｈａｉｒｎｇ　ａ　ｓｅｃｒｅｔ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，１９７９（１１）．　［２］ＢＬＡＫＬＥＹ　Ｇ．Ｓａｆｅｇｕａｒｄｉｎｇ　ｃｒｙｐｔｏｇｒａｐｈｙ　ｋｅｙｓ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｃｏｍｐｕｔｅｒ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ＡＦＩＰＳ．ＮＪ：ＡＦＩＰＳ　Ｐｒｅｓｓ，１９７９．　的计算和公开一些信息，提高了方案的效率。　（２）有效地防止了更新份额泄露可能出现的安全性问题。　［３］　Ｔ．Ｐ．Ｐｅｄｅｒｓｅｎ．Ｎｏｎ—ｉｎｔｅｒａｔｉｖｅ　ａｎｄ　ｉｎｆｏｒｍａｔｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｓｅｃｕｒｅ　ｖｅｒｉ—　ｆｉａｂｌｅｓｅｃｒｅｔ　ｈａｔｉｎｇ［Ｃ］．Ｉｎ　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏ－ｌｏｇｙ　ＣＲＹＰＴＯ＇９１，　更新由参与者自己独立完成，不需要和其他参与者进行交互，　ＳｐｒｉｎｇｅｒＶｅｒｌａｇ，１９９１．　克服了现有动态秘密共享的确定。减少了数据的传输量．提高　［４］ＬＡＩＨ　Ｃ　Ｓ，ＨＡＲＮ　Ｌ，ＬＥＥ　ＪＹ，ｅｔ　ａ１．Ｄｙｎａｍｉｃ　ｔｈｒｅｓｈｏｌｄ　ｓｃｈｅｍｅ　ｂａｓｅｄ　了方案的效率和安全性　ｏｎ　ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｃｒｏｓｓ—ｐｒｏｄｕｃｔ　ｉｎ　ａｎ　ｎ－ｄｉｍｅｎｓｉｏｎａｌ　ｌｉｎｅａｒ　ｓｐａｃｅ　（３）方案采用了椭圆曲线密码体制。椭圆曲线密码体制在　［Ｃ］．Ａｄｖａｎｃｅ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ－Ｅｕｒｏｃｒｙｐｔ　８９．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，　密钥长度、计算量和安全性等方面，都比传统的基于一般乘法　１９９０．　群上离散对数或大数分解问题的体制更具有优势。进一步地提　［５］ＨＥ，Ｉ，ａｎｄ　ＤＡＷＳＯＥＮ　Ｅ．Ｍｕｌｔｉｓｔａｇｅ　ｓｅｃｒｅｔ　ｓｈａｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ｏｎｅ—　高了方案的效率和安全性。　ｗａｙ　ｆｕｎｃｔｉｏｎ［Ｊ］．Ｅｌｅｃｔｒｏｎ．Ｌｅｔｔ，１９９４（１９）．　［６］Ｊ　ＨＥ，Ｅ　ＤＡＷＳＯＮ．Ｍｕｈｉｓｅｃｒｅｔ－ｓｈａｒｉｎｇ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎ　ｏｎｅ－ｗａｙ　３结束语　ｆｕｎｃｔｉｏｎ［Ｊ］．Ｅｌｅｃｔｒｏｎｉｃｓ　Ｌｅｔｔｅｒｓ，１９９５（２）．　［７］Ｌ　ＨＡＲＮ．Ｅｆｆｉｃｉｅｎｔ　ｓｈａｒｉｎｇ（ｂｒｏａｄｃａｓｔｉｎｇ）ｏｆ　ｍｕｌｔｉｐｌｅ　ｓｅｃｒｅｔｓ［Ｊ］．　本文基于椭圆曲线密码体制，提出了一种新的动态多秘密　ＩＥＥ　Ｐｒｏｃｅｅｄｉｎｇｓ　Ｃｏｍｐｕｔｅｒｓ　ａｎｄ　Ｄｉｓｔｌａ　Ｔｅｃｈｎｉｑｕｅｓ，１９９５（３）．　共享方案。在该方案中，参与者可以自主选择子秘密，参与者的　［８］Ｈ　Ｙ　ＣＨＩＥＮ，Ｊ　Ｋ　ＪＡＮ，Ｙ　Ｍ　ＴＳＥＮＧ．Ａ　ｐｒａｃｔｉｃａｌ（ｔ，ｎ）ｍｕｌｔｉ—ｓｅｃｒｅｔ　子密钥可以动态定期更新，且更新工作由每个参与者独立完　ｓｈａｉｒｎｇ　ｓｃｈｅｍｅ［Ｊ］．ＩＥＩＣＥ　Ｔｒｎａｓａｃｔｉｏｎｓ　ｏｎ　Ｆｕｎｄａｍｅｎｔａｌｓ，２０００（１２）．　成；共享多个秘密时，不需要重新计算参数和构造多项式，只需　［９］　Ｊｉｎａｊｉｅ　Ｚｈａｏ，Ｊｉａｎ　ｚｈｏｎｇ　Ｚｈａｎｇ，Ｒｏｎｇ　Ｚｈａｏ．Ａ　ｐｒａｃｔｉｃａｌ　ｖｅｒｉｉｆａｂｌｅ　要少量的计算和公布一些参数，只有在秘密更新时才需要构造　ｍｕｌｔｉ—ｓｅｃｒｅｔ　ｓｈａｒｉｎｇ　ｓｃｈｅｍｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｓｔａｎｄａｒｄｓ＆Ｉｎｔｅｒｆａｃｅｓ，　新的多项式；在进行一次秘密恢复后，其他参与者得到的只是　２００７（１１）．　子秘密的一个影子，参与者的子秘密不会泄露。因此，子秘密可　（责任编辑：卓光）　Ａ　Ｄｙｎａｍｉｃ　Ｍｕｌｔｉ－Ｓｅｃｒｅｔ　Ｓｈａｒｉｎｇ　Ｓｃｈｅｍｅ　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ（ｔ，ｎ）ｓｅｃｒｅｔ　ｓｈａｒｉｎｇ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ＥＣＣ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｓｃｈｅｍｅ　ｈａｓ　ｐｒｏｐｅｒｔｉｅｓ　ａｓ　ｆｏｌｌｏｗ：ｐａｒｔｉｃｉｐａｎｔｓ　ｃａｎ　ｃｈｏｏｓｅ　ｓｕｂ－ｓｅｃｒｅｔｓ　ｂｙ　ｔｈｅｍｓｅｌｖｅｓ；ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｓｕｂ－ｓｅｃｒｅｔｓ　ｃａｎ　ｎｏｔ　ｂｅ　ｌｅａｋｅｄ　ｗｈｉｌｅ　ａ　ｓｅｃｒｅｔ　ｗａｓ　ｒｅｃｏｖｅｒｅｄ，ａｎｏｔｈｅｒ　ｓｅｃｒｅｔ　ｃａｎ　ｂｅ　ｒｅｃｏｖｅｒｅｄ　ｂｙ　ｔｈｅ　ｓａｍｅ　ｓｕｂ－ｓｅｃｒｅｔｓ；ｓｕｂ－ｓｅｃｒｅｔｓ　ｏｆ　ｐａｒｔｉｃｉｐａｎｔｓ　ｃａｎ　ｂｅ　ｒｅｎｅｗｅｄ　ｐｅｒｉｏｄｉｃａｌｌｙ　ｗｈｉｃｈ　ｉｓ　ｃｏｍｐｌｅｔｅｄ　ｂｙ　ｔｈｅｍｓｅｌｖｅｓ．Ｓｏ　ｔｈｉｓ　ｓｃｈｅｍｅ　ｈａｓ　ｂｅｔｔｅｒ　ｆｌｅｘｉｂｉｌｉｔｙ　ａｎｄ　ｍｏｒｅ　ｓｅｃｕｒｉｔｙ．　Ｋｅｙ　Ｗｏｒｄｓ：Ｓｅｃｒｅｔ　Ｓｈａｒｉｎｇ；Ｅｃｃ；Ｍｕｌｔｉ－Ｓｅｃｒｅｔｓ　Ｓｈａｒｉｎｇ；Ｓｕｂ—Ｓｅｃｒｅ