中国剩余定理在电子投票中的应用及其门限秘密共享方案的研究

理论计算机科学电子笔记186（2007）67-84www.elsevier.com/locate/entcs基于中国剩余定理的广义秘密共享及其在电子投票Sorin Iftene1Al.I.Cuza大学计算机科学系我是你的我，罗马人的我摘要基于中国剩余定理的门限秘密共享已被Mittette [23]和Asmuth和Bloom [1]所考虑。在本文中，我们证明了中国剩余定理可以用来实现更一般的访问结构，如分区或加权阈值的。我们也证明了存在一些非加权门限访问结构，其实现需要中国剩余定理的一般变体，即，其中模块不一定是两两互质的变体。作为所提出的秘密共享方案的一个应用，我们提出了一个多权威电子投票方案，其中，作为一个新颖性，计票当局可能有不相等的权重。保留字：秘密共享，中国剩余定理，电子投票1引言和附录秘密共享方案从秘密开始，然后从中导出某些共享（或影子），这些共享被分发给用户。秘密可以仅由属于预定访问结构的某些组恢复。在第一个秘密共享方案中，只有份额的数量对恢复秘密很重要这种方案被称为门限秘密共享方案。我们在这里提到沙米尔方案[5]、Mittette伊藤、齐藤、西关[19]、贝纳洛、莱希特[4]提出了更一般的秘密共享方案的构造本文证明了中国剩余定理可用于实现更一般的存取结构。我们首先考虑的是1电子邮件：siftene@infoiasi.ro1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.01.06568S. Iftene/Electronic Notes in Theoretical Computer Science 186（2007）67共享方案，其中用户集合被划分为隔间，并且当且仅当来自任何隔间的参与者的数量大于或等于固定隔间阈值并且参与者的总数大于或等于全局阈值时，秘密可以被恢复。本文将Brickell的构造推广我们还扩展了阈值Mechtette和Asmuth-Bloom计划，以解决更一般的访问结构。我们提出了如何实现任何加权阈值访问结构（其中一些正权重与每个用户相关联，并且当且仅当每个用户的权重之和为零时，可以重建秘密）。参与者大于或等于一个固定的阈值），但我们证明了我们的扩展也适用于一些非加权阈值访问结构。本文的结构如下。本节的其余部分致力于数论的一些基础知识，重点是中国剩余定理。在简要介绍秘密共享之后，我们在第二节中综述了基于中国剩余定理的门限秘密共享 在第三节中，我们将Brickell关于划分秘密共享的构造推广在第四节中，我们将基于中国剩余定理的门限秘密共享方案推广到更一般的访问结构，并讨论了所得到的方案的同态性质。在第五节中，我们描述了一个多权威的电子投票方案的基础上提出的秘密共享计划。我们的结论和一些有趣的未来研究方向在最后一节。在本节的其余部分，我们将介绍数论中的一些基本事实和符号更多详情，请参阅[8]。设a，m∈Z，m= 0. a除以m的整数的商用divm表示，余数用modm表示。设a，b，m∈Z.我们说a和b是模m的同余，我们使用符号a ≠ b mod m，如果m|（a−b）。在m i = 0的情况下，amodm等于amodm = bmod m。集合{0，1，. ，m − 1}将由Zm表示，对于任何整数m ≥ 1。设a1，.，an ∈Z，a2+···+a2f= 0。 最大公约数（GCD）1N一个1，…，ann将由（a1，.，an）。众所周知，α1，...，αn∈Z，满足α1a1+··+ αnan=（a1，.，an）（线性形式的gcd）。设a1，.，an∈Z使得a1···an= 0. 的最小公倍数（lcm）a1，.，an将由[a1，.，an]。中国剩余定理在计算机科学中有许多应用（见[10] 关于这个话题的调查）。我们只提到它在Quisquater和Couvreur [27]提出的RSA解密算法、 Pohlig和Hellman [26]提出的离散对数算法以及S. Iftene/Electronic Notes in Theoretical Computer Science 186（2007）6769pi用于恢复在Mimutte的门限秘密共享方案[ 23 ]或在Asmuth-Bloom门限秘密共享方案[ 1 ]中的秘密中国剩余定理的几个版本已经被提出。下一个定理被称为广义中国剩余定理（[24]）：定理1.1设k≥ 2，p1，…，pk≥ 2，且b1，.，bk∈Z.方程组P2P1mod p1⎨⎪.- 是 的⎪P.B.Kmod pk在1 ≤ i，j ≤ k的情况下，如果 bi≠bjmod（pi，pj），则在Z中有一个解. 此外，如果上述方程组在Z中有解，则它在Z[p1，... . ，pk]。Ore已经证明，该解决方案可以获得为克i=1γiδibimod [p1，.，pk]，其中δi=[p1，...，pk]，对于所有1 ≤ i ≤ k，γ1，. ，γk是任意整数，使得γ1δ1+···+ γkδk= 1（注意（δ1，.，δk）= 1）。当（pi，pj）= 1时，对于所有1≤ij≤k，得到标准版本的中国剩余定理Garner [13]为这种情况找到了一个有效的算法，Fraenkel [12]将其推广到一般情况。基于中国剩余定理的2门限秘密共享方案我们首先介绍一些关于秘密共享方案的基本事实。读者可以参考[31]关于这个主题的调查。假设我们有n个用户，数字1，... ...，n}）。非正式地，A-秘密共享方案是生成（S，（I1，.，In）），使得• （正确性）对于任何A∈ A，找到元素S的问题，给定集合{I Ii|i∈A}，是“容易”的;• （安全性）对于任何A∈ P（{1，2，.，n}）\ A，找到元素S的问题，给定集合{Ii|i∈A}，是难处理的。集合A将被称为授权访问结构或简单地称为访问结构，S将被称为秘密，并且I1，.，n将被称为S的份额（或阴影）。集合A的元素将被称为授权组。2 P（{1，2，.，n}）表示集合{1，2，.. ..，n}。70S. Iftene/Electronic Notes in Theoretical Computer Science 186（2007）67在一个完美的秘密共享方案中，任何未经授权的群体的份额都不会给出关于秘密的信息（在信息论意义上）。Karnin、Greene和Hellman [20]已经证明，在任何完美的门限秘密共享方案中，份额必须至少与秘密一样长，后来，Capocelli、DeSantis、Gargano和Vaccaro [7]将这个结果扩展到任何完美秘密共享方案的情况。在一个理想的秘密共享方案中，共享的长度与秘密的长度一样长。自然条件是访问结构A是单调的（[4]），即，（n ∈ P（{1，2，. ，n}））（（<$A ∈ A）（A <$B）<$B ∈ A）.任何单调访问结构A都由最小授权群的集合很好地指定，即， 集合Amin={A ∈ A|（<$B ∈ A\{A}）（<$B <$A）}。此外，未授权访问结构A，A = P（{1，2，. ，n}）\A，由最大未授权组的集合很好地指定，即，集合Amax={A ∈ A|（<$B ∈ A\ {A}）（<$A<$B）}。在第一个秘密共享方案中，只有重建阶段的参与者数量对恢复秘密很重要。这种方案被称为门限秘密共享方案。定义2.1设n≥2，2≤k≤n。 访问结构A={A∈ P（{1，2，.，n}）||一|≥ k}将被称为（k，n）阈值访问结构。在这种情况下，我们还得到Amin={A∈P（{1，2，... ，n}）||一|= k}，A={A∈ P（{1，2，. ，n}）||≤ k − 1 }，且A max = { A ∈ P（{ 1，2，.| ≤k − 1}, and Amax= {A ∈ P({1, 2,... ，n}）||= k − 1 }。|= k − 1}. 任何A-秘密共享方案将被称为（k，n）-门限秘密共享方案.本文接着简要讨论了基于中国剩余定理的门限秘密共享方案。2.1一个MechtetteMittette定义2.2设n为正整数，n≥2，且2≤k≤n。 An（k，n）-Mittette序列是两两互素的正整数序列p1p2<<···pn使得 β≥pi1···pik−1>x0）。因此，为了确保合理的安全性水平，需要具有大因子的（k，n）-Mittette序列，α−ββ必须被选择（在[21，第9页]）。显然，Meclette我们推广了文献[ 17 ]中的Mittette定义2.3设n为整数，n≥2，且2≤k≤n。 广义（k，n）-martette序列是一个序列p1，. ，pn的正整数，使得ma x1≤i1<···

下载后可阅读完整内容，剩余1页未读，立即下载