Mixnet中混洗功能的实现与相关算法研究

Mixnet中混洗功能的实现与相关算法研究

Mixnet中混洗功能的实现与相关算法研究

  • 适用:本科,大专,自考
  • 更新时间2024年
  • 原价: ¥306
  • 活动价: ¥200 (活动截止日期:2024-03-31)
  • (到期后自动恢复原价)
Mixnet中混洗功能的实现与相关算法研究

Mixnet中混洗功能的实现与相关算法研究

摘要:随着网络技术的发展,电子投票的需求一天天增加。而电子投票最重要的就是系统的安全性与匿名性。为使电子投票可行,1981年Chaum首次引入了Mix-net的概念,其原理为多个输入通过匿名信道混合产生多个输出,使得攻击者无法得到输入与输出消息之间的对应关系,从而保证了消息与用户的不可链接性,即匿名性。

混合网络由于其私密性被广泛用于电子投票系统之中。通过对输入密文的再加密和随机排序之后输出,让输出与输入之间对应关系无法被外界知晓,这就是混洗。本文通过对密码学理论的学习及对国外混合网络理论的研究,实现小批量的混合网络混洗功能。它是一种简单的,基于排序网络的,混合网络。

关键词:混合网络,混洗,排序网络,加密,解密

第一章 绪论

选举和投票是现代社会的一个重要内容,由于传统的人工纸质投票已经无法适应当今社会的需要。电子投票突破了传统纸质投票方式在时间空间方面的局限性,能完成远程投票。同时,电子投票程序取代传统投票管理中的人工行为,从而节约大量人力物力成本,降低人为因素的不确定性,做到更安全、更公正。所有这些优势,使得电子投票将会在更大范围内成为取代纸质投票的一种新的投票方式。

投票系统的基本安全需求之一是匿名性,即攻击者无法得到输入和输出消息之间的对应关系。为了实现匿名性,传统纸质投票是通过选票箱等物理隔离设施和监督机构的监督来共同确保的。然而,社会需求的不断发展使得传统纸质投票无法高效率的实现大范围的投票。于是,随着网络的大规模普及,大范围内的低成本、高效率的电子投票诞生了。而电子投票系统的安全性与匿名性也成为了最重要的问题。

1981年Chaum发首次引入了Mix-net的概念,其原理为多个输入通过匿名信道混合产生多个输出,使得攻击者无法得到输入与输出消息之间的对应关系,从而保证了消息与用户的不可链接性,即匿名性。但是所提出的mix-net存在安全上的漏洞,同时其实现的效率不高。

之后的二十几年中,研究人员提出了很多新的mix-net设计方案,随着mix-net技术的不断革新与发展,在mix-net系统中调用混乱服务器实现shuffle功能来加密成为了一种新的方式。本文就是通过研究Mixnet中混洗功能的实现,来为电子投票提供更强力的保密性

1.1.研究背景

混合网络是一种加密结构,使一个或多个服务器可以获取一系列加密的输入消息,对其进行重新加密,然后以未公开,随机排列的顺序输出。混合网络的最初概念应归功于Chaum,他将其设想为增强隐私的工具。 此后,它们被建议用于发起者匿名电子邮件,Web浏览和安全选举等任务,以及看似无关的应用程序,例如匿名支付系统和安全的多方计算。混合网络还可以隐式地在高级协议中充当匿名通道的基础。在许多情况下,例如匿名Web浏览,它们可能是在不可信环境中实现强大隐私的唯一现实机制。

在过去的时间里,研究人员将精力集中在阈值混合网络的研究上。这些是由多个服务器(称为混合服务器)实现的混合网络,即使面对恶意服务器攻击,也可以确保正确性和隐私性。这个方面的早期活动包括绪方,黑泽,佐久和高田,其次是安倍晋三和雅各布森。阈值混合网络的早期建议相当无效,在典型的参数设置下,每项需要数十个幂。Jakobsson后来提出了一个混合网络,该网络比以前的混合网络快大约一个数量级,但是仅使用非常大的输入批次(大约100,000个项目)即可。安倍曾提出了一种对小批量更有效的混合网络。Abe的开发独立于此处介绍的结构而开发,非常相似,但计算效率较低。

许多应用需要小批量混合。例如,在希特和萨科的免收选举方案中,n等于候选人的数量。对于Jakobsson和Juels提出的安全的多方计算技术,n = 4表示模拟两输入布尔门所需的输入大小。

1.2.国内外研究现状

Chaum于1981年第一次提出mix-net协议,并给出了一种基于RSA的具体实现。尽管Chaum最初提出的解密mix-net可以实现匿名性,但是它利用的是RSA公钥加密系统,加密消息长度和计算复杂度与混合服务器的个数成正比不适用于大型选举。此外,只要有一个混合服务器受到了破坏,混合过程就不能进行。

1993年Park等人提出用ElGamal公钥加密体制来实现重加密mix-net,首次解决了这个困扰。使得密文为固定长度,与混合服务器个数和用户计算量无关,增强了mix-net的稳定性,有利于大型基于mix-net的电子选举的实现。

2002年,Golle等人提出Optimistic Mixing。该方案引入乘积校验限制明文为一个特定的格式,对明文进行两次加密。在混合阶段,每个混合服务器通过

提供证据来证明输入密文对应明文的乘积等于输出密文对应明文的乘积。解密阶

段,首先对密文进行一次解密,如果通过验证,那么继续解密,进而得到明文;如果发现无效的元组,那么必有以下两种情况之一发生:一种情况是这些无效的

元组仅仅由选民造成的,那么mix-net将这些元组删除后继续解密;另一种情况

是无效的密文是由欺骗的混合服务器造成的,那么这些无效的密文需要被追踪,

直到发现欺骗的混合服务器,然后移除欺骗的混合服务器以及删除无效的密文,

将有效的密文输入到备份的mix-net。

2002年,Jakosson,Juels和Rivset提出RPC(随机部分校验),它的基本思想是将mix-net中相邻的两个混合服务器构成一组,从每组中第一个混合服务器的输出中随机选取一半的密文C,要求给出C和输入的对应关系;同时要求每

组中第二个混合服务器给出C的补集和输出的对应关系。从端到端的角度,匿名性并没有受到破坏,因为观察者无法找出一条完整的路径将一个输出和输入对应起来。

2010年,西班牙Scytl公司结合RPC与Optimistic Mixing两种协议优点,提出了Scytl协议。该协议最大的亮点就是提出了分组验证的概念,变体已应用

于Norway系统。

2012年Denise Demirel等人对Scytl mix-net进行改进。该方案适用于验证过程中组内选票数不相等的情形。该方案在验证过程采用随机分组验证(RBV)。

2012年Denise Demirel等人提出了一个永恒隐私的公共可验证的mix-net。它的优点是混合服务器在公告板BB上公布的消息没有揭示任何关于选民身份的信息。该方案利用Pederson承诺对消息进行编码、利用Paillier加密方案对解除承诺值进行加密。选民将消息的编码分成两部分发送到上,将加密的承诺值

也分成两部分发送到私有信道中。然后使用两个同步的mix-net进行混合,并且两个mix-net的置换完全一致。

国内学者对mix-net研究不多。西安电子科技大学王继林等人设计了一个

新的具有弹性的可验证mix-net协议,使用ElGamal公钥密码系统、零知识证明和Shamir门限方案等密码技术设计了一个mix-net协议,其技术关键在于把同一个密文向量让两个不同的有效的秘密共享组进行盲化解密,然后再进行比较,大大提高了解密的正确性。清华大学田宝等人对基于mix-net的电子投票系统提

出安全需求的矛盾和解决方法。李洪海等人利用Optimistic mix-net在两次会话中使用相同密钥这一缺陷,对其提出一种攻击,成功打破了选民的隐私。2012年苑浩发现一种基于mix-net的电子投票系统的缺陷,并给出相关的证明和攻

击方式。

伴随着密码学相关理论方面的日益完善,国内国际的大量学者利用各异的密

码学技术不断研究并设计出一些mix-net方案,广大学者对其做了众多研究,并

取得较多的研究成果。

1.3.研究内容和文章结构

针对于国内较少的在混合网络这方面进行研究,本文试着通过对排序网络和密码学相关知识学习并研究国内外学者们对于mixnet实现方案来阐述如何实现mixnet中的混洗功能。

在文章的第二章中回顾了相关的理论知识,第三章中介绍了mixnet的相关知识并描述如何实现混合网络中的混洗功能,第四章进行了实验的仿真,在第五章进行了总结和展望。

2.预备知识

2.1.排序网络

排序网络是一种由线路和比较器模块组合成的网络为基础的数学模型,用于对数字序列进行排序。每个比较器连接两条线路,并通过将较小的值输出给一条线路、将较大的值输出给另一条线路的方式来对数值进行排序。排序网络和比较排序算法之间的主要区别在于,排序网络中的比较顺序是预先设置的,而不考虑先前比较的结果。比较顺序的这种独立性对于算法的并行执行非常有用。尽管模型简单,排序网络理论却非常的深刻且复杂。排序网络的概念最早由Armstrong、Nelson和O'Connor于1954年研究并提出,他们随后为此申请了专利。

排序网络在硬件和软件中均可实现。Donald Knuth 提出了如何将二进制整数的比较器实现为简单的三状态电子设备。Batcher在1968年提出使用排序网络来构建计算机硬件的交换网络,同时替换总线和更快但更昂贵的横杆开关。从2000 年开始,GPGPU使用排序网络(尤其是双调排序)来构建可在图形处理单元上运行的排序算法。

1.简介

排序网络由两部分组成:比较器和线路。线路被是携带着数值(每根线一个)从左到右运行,同时遍历网络。每个比较器连接两条线路。当通过两条线路运送的一对数值到达比较器,如果上部线路携带的数值大于下部线路携带的数值时,比较器会将数值交换输出。

在公式中,假设顶线携带数值为x,底部线路携带数值为 y,则在经过比较器后,顶部线路与底部线路分别携带x’=min(x,y)和y’=max(x,y),从而将输入的数值分别进行了排序。我们将这种能够正确地对所有可能的输入按升序排序的由线路和比较器组成的网络称为排序网络。

简单排序网络的完整操作如下所示。很容易看出为什么这个排序网络会正确地对输入进行排序。请注意,前四个比较器会将最大值“下沉”到底部,将最小值“浮动”到顶部。最终的比较器只需将中间的两根导线分开即可。

2.深度和效率

排序网络的效率可以通过其整体规模即使用的比较器数量多少或深度(非正式地定义为输入中的最大值在通过网络时可能遇到的比较器数量)来衡量。请注意,排序网络可以并行执行某些比较(由图形表示形式表示为位于同一垂直线上的所有比较器)。那么假设所有比较器中的比较耗时均为单位时间,则可以看出网络的深度等于数值输入到输出所需的时间。

3.排序网络构造

我们可以用各种算法来构造深度为O()(因此规模为O(n)的简单而有效的排序网络,例如奇偶合并排序,双音排序,贝壳排序和成对排序网络。这些网络在实践中被频繁地使用。在排序网络的概念由Ajtai,Komlós和Szemerédi提出之后,使用称为AKS网络的结构来构造任意规模的对数深度网络在理论上说时可行的。Paterson描述了AKS网络的简化版本。虽然是一个重要的理论发现,但由于O符号中隐藏的线性常数过大,AKS网络几乎没有实际应用。

我们可以使用插入和选择原理轻松地递归构造任何规模的网络。假设排序网络的规模为n,我们可以通过将一个附加数字“插入”已经分类好的子网之中(使用插入排序原理)来构建规模为n +1的网络。我们还可以通过首先从输入中确定将会从最底部线路输出的数值,然后对其余值进行递归排序(使用冒泡排序原理)来完成同一件事。这两个分类网络的结构非常相似。两种不同转化方式的网络构造都是将一些可以同时执行的比较器折叠在一起,这表明它们实际上是相同的。

4.零一原理

虽然很容易证明一些排序网络(如插入网络/冒泡排序网络)的有效性,但并不是所有排序网络都那么容易。在n线网络中数字的排列方式有n!种,测试所有排序方式将花费大量时间,尤其是当n特别大时。而使用零一原理,测试用例的数量可以大大减少到。虽然仍然是指数量,但比n!要少(当n> = 4),并且随着n的增加两者的数量差会迅速变大。

零一原理指出,如果一个排序网络可以将一个由个零和一组成的序列正确地进行排序,那么它就可以将任意的有序输入进行正确排序。这不仅大大减少了排序网络有效性验证时所需测试用例的数量,在许多排序网络的搭建中也能起到很大作用。

首先通过观察以下有关比较器的事实来证明该原理:将单调函数f输入,x和y分别由f(x)和f(y)代替,然后比较器会输出min(f(x),f(y))=f(min(x,y))和max(f(x),f(y))=f(max(x,y))。通过对网络深度的归纳,该结果可以扩展为引理:如果排序网络可以将序列,...,转换为,...,,那么它可以序列f(),......,f()转换为f(),...,f()。现在我们通过反证法来证明该引理:假设输入序列,...,中存在<,并且排序网络对它们进行错误的排序然后输出。那么它也会错误地对序列f(),...,f()进行排序输出,通过函数

该函数是单调的,因此反过来证明零一原理是成立的。

这一原理已被W. G. Bouricius在1954年提出的一个定理中的一个特例证明

5.最佳排序网络

对于小而固定的输入数为n的序列,可以构造具有最小深度(最大并行执行)或最小长度(比较器数)的最佳排序网络。通过尽早停止递归并插入最佳排序网络作为基本网络的方式,这些网络可用于提高如由Batcher的递归结构所产生的较大规模排序网络的性能。

Knuth在其1973年出版的《计算机编程艺术》中列出了排名前16的最佳深度网络。尽管前八个网络的最佳性由Floyd和Knuth在20世纪60年代就验证确定了,但后六个网络的存在直到2014年才得以证明(1991年确定了九名和十名)。

假设输入一到十,已知长度最优的排序网络,对于更大的值,根据Van Voorhis定理,可以使用引理归纳得出其长度S(n)的下界:S(n + 1)≥S(n)+⌈⌉。1969年十个最佳网络的猜想就已经被提出,前八个网络被确定为最佳网络是自Floyd和Knuth的工作以后,但是第九个和第十个网络的最佳性直到2014年才得以确认。

目录

第一章 绪论 2

1.1.研究背景 3

1.2.国内外研究现状 4

1.3.研究内容和文章结构 6

第三章 Mixnet中混洗功能的实现 21

3.1.mixnet的基本流程 22

3.2Mixnet中混洗功能的实现 23

3.2.1.网络体系构建 23

3.2.2.PEP和DISPEP 24

3.2.3混洗功能流程 25

第四章 实验仿真结果 27

4.1.实验环境 27

4.2.流程文字说明 27

4.3.程序截图 28

4.4.运行结果截图 30

第五章 总结与展望 32

结束语 33

参考文献 34

参考文献

[1]Bruce Schneier,应用密码学—协议、算法与C源程序[M],北京:机械工业出版社,2003: 1-7 330-340,347-354

[2]Mohan Atreya,数字签名[M],北京:清华大学出版社,2003:49-56.

[3]William Stallings,密码学与网络安全[M],北京:电子工业出版社,2001

[4]卢开澄, 计算机密码学[M],北京:清华大学出版社,2001

[5]Salomaa A,公钥密码学[M],北京:国防工业出版社,1998

[6]闵嗣鹤,严士健,初等数论[M],高等教育出版社,1982

[7]方勇等编著,信息系统安全导论[M],北京:电子工业出版社,2003年4月

[8]陈景润,初等数论I,北京:科学出版社,1978

[9]范红,数字签名技术及其在网络信息安全中的应用[J],中国科学院研究生院学报,2001,18(2):4

[10]卿斯汉,密码学与计算机安全[M],北京:清华大学出版社,2000

[11]张先红,数字签名原理与技术[M],北京:机械工业出版社,2004

[12]Karli Watson,C#入门经典[M],北京:清华大学出版社,2002

[13] Ran Canetti,Verifiable Mix­Nets, 6.879 Special Topics in Cryptography Instructor:

[14] Nippon Telegraph and Telephone Corporation, Mix-Networks on Permutation Networks

[15] Markus Jakobsson and Ari Juels, Millimix: Mixing in Small Batches

[16] Ben Adida and Douglas Wikstr¨om, How To Shuffle in Public



  • 关键词 Mixnet 中混 功能 实现 相关 算法 研究
  • 上一篇:250W感性负载参测量显示与控制系统设计
  • 下一篇:基于OpenCV仪表指针读数识别系统设计
  • 暂无购买记录

    暂时没有评论

    真实

    多重认证,精挑细选的优质资源 优质老师。

    安全

    诚实交易,诚信为本。

    保密

    所有交易信息,都为您保密。

    专业

    10年专业经验,10年来帮助无数学子。