２０１３年６月第一版开本：B５（７２０ × １０００）

安全远程网络投票协议

x x xxx 著

北京

内容简介

x书共有十三章。系统全面地介绍了远程网络投票协议设计与分析的基本理论、关键技术及最新成果。主要内容包括远程网络投票协议的分类和模型、国内外发展现状、安全属性及其实现所需要的关键技术、典型远程网络投票协议、基于符号模型手工方式分析与验证无收据性、应用 PI 演算、一阶定理证明器 ProVerif 、基于符号模型自动化分析与验证抗拒绝服务攻击性、无收据性和抗威胁性、概率进程演算、自动化安全协议证明器 Crypto‐ Verif 、基于计算模型自动化分析和验证抗威胁性等。

本书可供从事安全协议、密码学、计算机、通信和数学等专业的科技人员、硕士和博士研究生参考，也可供高等院校相关专业的师生参考。

图书在版编目（CIP）数据

安全远程网络投票协议／ xx ，xxx著畅 — 北京：科学出版社，２０１３

ISBN ９７８‐７‐０３‐０３６８２６‐３

Ⅰ畅 ① x ⋯ Ⅱ 畅 ① 孟 ⋯ ② 王 ⋯ Ⅲ 畅 ① 远程网络计算机监控

Ⅳ 畅 ① T P２７７ ② TP３９３畅２

中国版本图书馆 CIP 数据核字（２０１３）第０３９４７４号

责任编辑：xxx ／责任校对：xxx 责任印制：x x ／封面设计：科迪亚盟

出版

北京东黄城根北街１６号

邮政编码：１００７１７

http ：／／w w w ．sciencep ．co m

印刷

科学出版社发行各地新华书店经销

倡

２０１３年６月第一版开本：B５（７２０ × １０００）

２０１３年６月第一次印刷印张：２０１／２

字数：３９５６４０

定价：85畅00 元

（如有印装质量问题，我社负责调换）

序

随着信息技术与产业的迅速发展和广泛应用，社会逐步实现了信息化。在信息化社会中，许多事务都采用信息化的方法进行处理。因此，如何使信息化的事务处理能够高效方便地进行并确保信息处理的安全就成为一个重要的问题。

投票是人们表达自己对某一事物意见的一种方式，已经广泛应用于选举、评奖、表决等事务处理中。用于传统事务处理的投票方式有举手、投石块、投金属币以及投纸票等。而在以计算机网络系统为基础的事务处理中，投票的方式发展成网络投票。由于投票所要处理的事务都是重要事务的裁决，涉及资源、利益和权力的分配等重要方面，所以确保投票系统的信息安全是一个重要问题。为此，网络投票系统综合采用了加解密、数字签名、密码协议、访问控制以及网络安全等多种信息安全技术。随着人们对网络投票理论与技术的研究和开发，网络投票系统已逐步走向实际应用。

本书作者长期从事网络投票的研究，重点研究投票协议及其安全性，取得了一系列重要成果。特别是在无物理约束条件下的安全远程网络投票协议、网络投票协议形式化分析与验证等方面的成果得到了国内外同行的好评。他们发表了一批高质量的学术论文，并培养了多名优秀的研究生。本书是他们这些研究成果的总结。本书的出版将为传播网络投票的基础知识、交流网络投票的理论与技术、扩大网络投票系统的应用做出贡献。

我作为xx在博士后期间的合作导师以及xxx在攻读博士学位期间的老师，见证了他们的努力学习和刻苦研究。我为他们取得的研究成果和学术著作的出版感到由衷的高兴，并向他们表示衷心祝贺！

xxx

２０１３年

前言

投票是人们表达自己对某一问题观点的一种方式。随着社会和经济的发展，采用投票方式来处理的事务越来越多。特别是信息技术的飞速发展使通过网络进行投票成为现实。目前远程网络投票已取代传统投票并广泛应用于商业和社会活动中。安全远程网络投票协议既是网络投票系统的基础和核心，又是安全协议研究领域的一个热点。由于远程网络投票的复杂性和特殊性，其安全性受到人们的重点关注。

作者从２００４年便开始安全远程网络投票协议研究工作，在远程网络投票协议设计方面、对其安全属性实现的关键技术进行了深入研究，在无物理约束条件下提出了一个安全远程网络投票协议；在其形式化分析和验证方面，分别基于符号模型和计算模型，对典型的及提出的远程网络协议进行自动化分析和验证。在这期间，参加过多次国际国内相关学术会议，与国内外多名专家进行过学术交流，曾得到国家民委基金、国家自然科学基金、湖北省自然科学基金等课题的支持，取得了一批高水平的研究成果，培养了多名优秀研究生，发表了一批高质量学术论文，也在已出版的部分著作中反映了我们的一些研究成果。本书是作者长期从事远程网络投票协议研究的成果总结。

本书包括１３章。第１、２章介绍了传统投票方式和分类、远程网络投票的分类和模型、远程网络投票的通信模型以及在安全远程网络投票协议设计中需要的关键技术等。第３、４章重点对远程网络投票协议安全属性中非常重要的无收据性和抗威胁性的发展现状做了阐述，同时对典型的与提出的远程网络投票协议及其安全性进行了深入分析和研究。第５～９章重点介绍了基于符号模型分析远程网络投票协议的国内外发展现状、手工方式分析与验证无收据性、应用 PI 演算、一阶定理证明器 Pro Verif 、符号模型自动化分析与验证抗拒绝服务攻击性、无收据性和抗威胁性。第１０～１３章重点讨论了基于计算模型分析远程网络投票协议的国内外发展现状、概率进程演算、自动化安全协议证明器 CryptoVerif 、计算模型自动化分析和验证抗威胁性等。本书由中南民族大学xx和xxx共同撰写，其中第

１、２、６、７章由xxx撰写，其余章节由xx撰写。全书最后由xxx稿、xxx校稿。

本书的研究工作得到了国家民委基金（No畅１２ZNZ００８、１２ZNZ００９、１０ZN０９）、

国家自然科学基金项目（No ．９１０１８００８、６０６０３００８）和湖北省自然科学基金（No ．

· iv · 安全远程网络投票协议

２０１１CDC１６３）的支持以及其他课题（SZY１１００８，YZZ０９００８）的资助，在此表示衷心的感谢。

由于水平有限，对一些问题的理解和表述或有肤浅之处，诚请读者批评指正。

x x xxx

２０１３年４月２５日

序前言

第 1 章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １

１畅１引言 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １

１畅２投票的分类 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２

１畅２畅１按照票的介质进行分类 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２

１畅２畅２按照票的类型进行分类 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３

１畅２畅３按照票的权重进行分类 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４

１畅３传统投票模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４

１畅４远程网络投票模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ５

１畅５本章小结 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６

第 2 章相关的密码技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９

２畅１公钥密码体制 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９

２畅１畅１ RSA 公钥加密体制 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９

２畅１畅２ ElGamal 公钥加密体制 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９

２畅１畅３ Paillier 公钥加密体制⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９

２畅１畅４ BCP 公钥密码体制 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １０

２畅２秘密共享⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １０

２畅３门限公钥加密⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １２

２畅３畅１ RSA 公钥加密的门限版本 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １２

２畅３畅２ ElGamal 公钥加密的门限版本 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １３

２畅３畅３ Paillier 加密的门限版本 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １３

２畅４盲签名⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １４

２畅５同态加密⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １４

２畅６混淆网⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １６

２畅７ Fiat‐Shamir 启发式 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １８

２畅８离散对数相等知识证明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １８

２畅９ BCP 承诺方案

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ １９

· vi · 安全远程网络投票协议

２畅１０分布式明文相等测试 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２０

２畅１１指定验证者证明／签名⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２１

２畅１２指定验证者离散对数相等证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２３

２畅１３明文相等证明协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２４

２畅１４指定验证者再加密证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２６

２畅１５非交互式可否认认证协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ２８

２畅１５畅１ Meng 非交互式可否认认证协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３０

２畅１５畅２ Fan 交互式可否认认证协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３３

２畅１６ Meng 和 Xxxx 可否认加密模式 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３４

２畅１７本章小结 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３８

参考文献 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ３８

第 3 章远程网络投票协议

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４５

３畅１远程网络投票协议安全属性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４５

３畅２远程网络投票协议国内外发展现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４７

３畅２畅１无收据性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ４７

３畅２畅２抗威胁性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ５６

３畅３本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６３

参考文献 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６４

第 4 章典型远程网络投票协议

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６８

４畅１ DLM 投票协议

４畅２ FOO 投票协议

４畅３ CGS 投票协议

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６８

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ６９

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ７２

４畅４ JCJ 投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ７４

４畅５ Acquisti 投票协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ７６

４畅６提出的基于明文相等证明的投票协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ８１

４畅７提出的基于非交互式可否认认证协议的投票协议⋯⋯⋯⋯⋯⋯⋯⋯ ９０

４畅８提出的基于可否认加密的投票协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９４

４畅９本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９８

参考文献 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ ９８

第 5 章基于符号模型的远程网络投票协议分析与验证

⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０２

５畅１引言

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０２

５畅２符号模型分析与验证远程网络投票协议

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０３

５畅３本章小结

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０７

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０７

目录 · vii ·

第 6 章手工方式分析与验证无收据性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

６畅１ DKR 模型及应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

６畅１畅１应用 PI 演算 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

６畅１畅２ DKR 模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１１１

１１５

６畅１畅３ DKR 模型应用 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１１６

６畅２ Jonker‐Vink 模型及应用 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２２

６畅２畅１ Jonker‐Vink 模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２２

６畅２畅２ Jonker‐Vink 模型应用 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２３

６畅３ Meng 模型及应用 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２７

６畅３畅１ Kessler 和 Xxxxxxx 逻辑 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２７

６畅３畅２ Meng 模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

６畅３畅３ Meng 模型应用 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３２

１３４

６畅４本章小结 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３９

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

第 7 章自动化分析与验证正确性与抗威胁性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３９

１４１

７畅１引言 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４１

７畅２一阶定理证明器 Pro Verif ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４１

７畅３ Backes 模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４５

７畅３畅１远程网络投票协议形式化模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４５

７畅３畅２安全属性形式化定义 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４６

７畅４本章小结

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４８

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

第 8 章自动化分析与验证抗拒绝服务攻击性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１４８

１５０

８畅１引言 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５０

８畅２扩展的应用 PI 演算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５２

８畅２畅１攻击者上下文 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５２

８畅２畅２项⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５３

８畅２畅３扩展后的进程

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５３

８畅２畅４进程上下文

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５４

８畅３定义和符号说明

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５４

８畅４自动化证明抗拒绝服务攻击性方法

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５６

８畅５本章小结

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１５８

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

第 9 章自动化分析与验证典型远程网络投票协议安全性⋯⋯⋯⋯⋯⋯⋯⋯

１５９

１６１

９畅１正确性与抗威胁性

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１６１

· viii · 安全远程网络投票协议

９畅１畅１ Meng 等投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

９畅１畅２ Meng 投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

９畅１畅３ Acquisti 投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１６１

１７９

１９７

９畅２抗拒绝服务攻击性 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２１５

９畅２畅１ Meng 投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

９畅２畅２ Acquisti 投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２１５

２２０

９畅３本章小结 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２２４

参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２２５

第 10 章基于计算模型的远程网络投票协议分析与验证

⋯⋯⋯⋯⋯⋯⋯⋯⋯

２２７

１０畅１引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０畅２计算模型分析与验证远程网络投票协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１０畅３本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２２７

２２９

２３１

２３２

第 11 章 Blanchet 演算和XxxxxxXxxxx ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２３８

１１畅１ Blanchet 演算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２３８

１１畅２自动化证明工具 CryptoVerif ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２４４

１１畅２畅１结构 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２４４

１１畅２畅２证明目标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２４９

１１畅２畅３语法

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２５０

１１畅３应用：可否认性模型

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２５２

１１畅３畅１提出的可否认性模型

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２５２

１１畅３畅２ Meng 协议可否认性自动化证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２５７

１１畅３畅３ Fan 协议可否认性自动化证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２６７

１１畅４本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

第 12 章扩展的Blanchet 演算 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２８０

２８２

１２畅１扩展的Blanchet 演算 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２８２

１２畅２应用：抗拒绝服务攻击性模型 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２８４

１２畅２畅１提出的基于事件的抗拒绝服务攻击性模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２畅２畅２４步握手协议抗拒绝服务攻击性自动化证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１２畅３本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２８４

２８６

２９２

２９３

第 13 章自动化分析与验证典型远程网络投票协议抗威胁性

⋯⋯⋯⋯⋯⋯

２９４

１３畅１引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３畅２提出的抗威胁性模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２９４

目录 · ix ·

１３畅３自动化证明 Meng 等投票协议抗威胁性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３畅３畅１ Meng 等投票协议⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

２９８

１３畅３畅２基于扩展的 Blanchet 演算建模 Meng 等投票协议 ⋯⋯⋯⋯⋯⋯⋯⋯

３００

１３畅３畅３ Meng 等投票协议抗威胁性自动化证明 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

１３畅４本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

３０７

３１３

第 1 章绪论

１畅１引言

投票是人们表达自己对某一问题观点的一种方式。而这种表达方式随着科学技术发展水平的不同而不同，比如从古代的石头，到近代纸质投票、机械杠杆投票仪、打xx 、光学识别投票，再到今天的直接记录电子投票系统、远程网络投票等，如图１畅１所示。

图１畅１投票方式

随着计算机和通信技术的发展，计算机已经普及到千家万户。特别是随着网络的迅猛发展，由于网络本身所具有的特点，使人们利用计算机或者各种通信设备在任何地方通过网络进行投票成为现实。由于远程网络投票的方便性和实施成本的低廉，必将对社会经济的发展和国家民主进程产生积极而重大的影响。比如，可以吸引更多的人来投票，方便残疾人投票，投票的人数不受天气等状况的影响。远程网络投票不仅消除了票的运输和计算上的困难，也大大减少了投票者由于日常安排与投票日发生冲突而带来的不便，同时也为残疾人士参与相关活动提供了便利。

在商业应用领域，比如我国证券行业，股东可以利用远程网络投票的方式通过深圳或者上海证券交易所股东大会网络投票系统来对各种议案，如增发新股、配股、发行可转债、重大资产重组等事项发表自己的观点。在政治生活方面，２００６年

８月，我国上海市闸北区宝山路街道第八届居委会的换届选举首次允许网络投票。选举所使用的电子投票系统提供了网络投票功能，无法现场投票的选民只要填写社保卡号码和发卡日期，就可以进行网络投票［１］。爱沙尼亚在网络投票选举方面的实践走在了世界的前列，它是全球第一个将远程网络投票方式运用于全国范围内地方选举的国家［２］。２０００年，爱沙尼亚政府规定可以在国家选举中采用 Inter‐ net 投票系统。２００５年７月，Internet 投票系统应用在本地政府选举中，２００７年１０

· ２ · 安全远程网络投票协议

月，Internet 投票系统应用在国家选举中。根据Xxxxx 关于在美国国家选举中投票方式分类的报告，从２０００年到２００８年，使用电子投票的郡从３２０个增加到１０６８个，投票者使用电子投票的比例从１２畅４％增加到３２畅６％［３］。此外美国、日本、瑞士以及英国等国家在选举中大量进行远程网络投票实验，２０００年到２０１１年，瑞士实施了远程网络投票实验计划达到３６个［４］。

在最近的二十多年中，人们对电子投票及远程网络投票展开了深入研究，提出了许多远程网络投票协议。但是，不论在实践还是在理论方面，目前都没有完善的解决方案。其中远程网络投票协议是实施远程网络投票系统的基础，我国目前对远程网络投票协议的研究还非常少，处在刚刚开始阶段。因此为了促进我国社会经济的发展和满足人们的需要，对远程网络投票协议进行研究具有重要的现实意义和巨大的经济价值。

１畅２投票的分类

投票是人们表达自己对某一问题的观点的一种方式。投票可以按照不同的标准进行分类：① 按照票的介质的不同；② 按照票的类型；③ 按照每张票的权重分类。

1畅2畅1 按照票的介质进行分类

按照票介质的不同，投票可以分为两大类：纸质投票和电子投票，如图１畅２所示。

纸质投票的介质是纸张，它可以分为纸张选票、打孔的卡片等。纸张选票系统

装置最简单，就是在写有候选人姓名的纸上选择出自己的支持者，在他旁边画个圈，再投进密封的票箱即可。１８５６年澳大利亚首次运用该系统，美国直到１８８９年才在纽约首次使用。现在，在美国的少数民族和偏远农村等地区，还在使用这种投票方式。这种投票方式在我国的选举中是比较常用的一种方式。

打孔的卡片这种投票方式有点像学

生考试用的答题卡。在卡上写着候选人

的名字，投票者需在自己中意的候选人名

图１畅２按照按票的介质进行分类

字处打孔，然后将票投进票箱，与投票箱

相连的计算机可以自动识别。这种系统在１９６４年的美国总统选举中首次被佛罗里达州选民使用。在２０００年总统大选时，正是这种类别的选票导致佛罗里达州出现计票争议。因此，打卡装置也正在被淘汰。

第１章 x x · ３ ·

电子投票所采用票的形式是电子的。电子投票根据投票地点的不同分为投票地投票、选区投票、投票亭投票与网络投票。

现在在美国使用的是直接记录（direct recording electronic ）电子投票系统。此系统可以让投票者利用电子投票机方便地投票，机器上会显示候选人的名单，投票者只需按机器上的按钮，或者屏幕上的触

摸式按键，就可完成投选程序。

选区投票限定在一定的区域内的投票者才可以投票。也就是说投票者只要在这个选区内，没有规定你在某一个特殊的投票地进行投票，都可以在这里投票。

投票亭投票指的是在某一个指定位置

有投票官员来现场控制的一种投票方式。

网络投票［５］是指投票者利用计算机

图１畅３网络投票的分类

通过远程网络来进行投票的方式，如图１畅３所示。网络投票可以分为四种：

① 远程网络投票（remote internet voting ）；② 投票亭网络投票（kiosk internet voting ）；③ 投票地网络投票（polling place internet voting ）；④ 选区网络投票

（precinct internet voting ）。

远程网络投票指不在投票管理员的现场控制下，利用计算机通过远程网络进行投票。投票者在家庭或者工作场所等通过各种互联网终端来进行投票，因此这种投票方式面临的安全风险最大。

投票亭网络投票指在某一个特定位置，在投票官现场控制下通过远程网络进行投票。

投票地网络投票指在任何有效的投票地，在投票官现场控制下通过远程网络进行投票。

选区网络投票在一定区域内的投票者，除了只能在某一特殊投票地投票的投票者之外，才可以投票。也就是说投票者只要在这个选区内，没有规定投票者在某一个特殊的投票地进行投票，都可以在这里投票。投票是在投票管理员的现场控制下通过远程网络进行的。

1畅2畅2 按照票的类型进行分类

常用的票的类型有如下六种：

（１） yes／no voting ：投票者对问题进行 yes 或者 no 的回答。一般情况下用１

表示 yes ，用０表示 no 。

（２）１ ‐out‐o f‐L voting ：从 L 个可能的选择中选择一个。

（３） K‐out‐o f‐L voting ：从 L 个可能的选择中选择 K 个，这 K 个元素是没有

· ４ · 安全远程网络投票协议

次序关系的。

（４） K‐out‐o f‐L ordervoting ：从 L 个可能的选择中选择 K 个，这 K 个元素是有次序关系的。

（５）１ ‐L‐K voting ：投票者从 L 个选择中选择一个可能的选择，然后再在另一个可能的选择中选择 K 个。它的票的结构是（ I ，a１，a２，⋯ ，aK ）。比如在选举人大代表时，有 L 个不同的党派，共有 m 个候选人，投票人只能选自己所在的党派的候选人，那么这种选举方式就是１ ‐L‐K voting 。 I 表示党派，a１，a２，⋯ ，aK 表示自己党派的候选人中的 K 个。

（６） w rite‐in voting ：在投票时，可以投不在候选者名单中的票。

最初电子投票协议［６～８］只是支持简单的 yes／no 票类型，随着研究工作的深入，支持从多个中选择一个、或从多个中选择多个的电子／网络投票协议［９～１６］被设计出来，同时支持 w rite‐in 类型的远程网络投票协议［１７～２２］也被提了出来。

1畅2畅3 按照票的权重进行分类

按票的权重进行分类：① equal‐voting ：每个投票人的票的权重是一样的；

② weighted‐voting ：投票人的票的权重是不相同的；几乎所有的电子／网络投票协议都没有特别明确这一点［２３］。

１畅３传统投票模型

如图１畅４所示，在传统投票中，首先投票者去注册地点进行注册，只有经过注册的投票者才可以投票。

图１畅４传统投票模型

注册完成后，领取票，票一般是由投票委员会提前制定的。然后到投票地进行投票。一般情况下，投票地有投票箱，在箱子的顶部有一个投票时用的小缝，在投票时，人们把填好的票投进投票箱。

投票结束后，根据投票委员会的决定，选择公开计票或者不公开计票。如果

是公开计票，把投的票公开，然后进行计票，计票结果也当场公开。如果是不公开计票，则只公开计票结果。

传统投票需要花费大量的人力和物力来保证投票公正、公平的进行，防止破坏和舞弊行为的发生。

第１章绪论 · ５ ·

１畅４远程网络投票模型

在远程网络投票模型中，主要涉及的参与者有投票者、注册机构、证书颁发机构、计票机构、票的生成机构、贿票者与威胁者。当然也有另外的机构，比如监察机构等。

图１畅５远程网络投票模型

远程网络投票模型［２３］如图１畅５所示，由四个阶段组成：系统建立阶段、注册阶段、投票阶段和计票阶段。在投票过程中，贿票者可以对权威机构进行贿赂，为了处理这种情况，门限加密通常被用在远程网络投票系统中。

（１）系统建立阶段。权威机构建立投票系统，同时权威机构和投票者产生自己公／私钥。投票者和权威机构的私钥保密。权威机构生成票，然后将票和它的数字签名发送到公告板。

（２）注册阶段。投票者通过一个安全的信道得到他的信任状，从公告板得到票。

（３）投票阶段。投票者准备了一个加密的票，接着用可以验证的方式将它公布在公告板上，然后多个独立的混淆服务器以可验证的方式混淆被公布的票，使票的表现形式发生变化，投票者不能再识别出自己的票。在这个阶段，威胁者可能强迫投票者投一张特殊的票；贿票者可能贿赂投票者，干扰或者破坏投票。此时投票者可以使用一些技术产生一个假的信任状，然后使用它产生一个威胁者／贿票者不能验证的投票。

（４）计票阶段。混淆完成以后，多个计票服务器用门限解密算法解密票的密文，计票，然后发布计票的结果。

在远程网络投票中常用的通信模型如下：

· ６ · 安全远程网络投票协议

（１）公告板（bulletin board）。任何参加投票的实体都可以通过公告板发布信息。任何人都可以访问公告板。任何人都可以在公告板上自己所属的区域进行写操作，但是不能删除和修改公告板上的信息。

（２）不可泄漏通道（untappable channel）。不可泄漏通道是通讯双方之间的一个秘密通道。通过不可泄漏通道进行通信是物理上安全的。没有任何人，除了通信双方外，知道通道中传输的信息。同时通讯参加者也不能向任何人证明自己所发送的内容。

（３）不可追踪的匿名通道或匿名通道（untraceable anonymous channel or anonymous channel）。通过这个通道传送信息可以保证信息的发送者的匿名性。信息的接收者不知道信息的发送者的身份。

（４）不可泄漏的匿名通道（untappable anonymous channel ）。它既可以保证发送者的匿名性，又可以保证传输的安全。发送者和接收者不能重演发送或接收的内容。没有人能监听传输的消息。

１畅５本章小结

随着信息技术的发展，远程网络投票已取代传统投票并广泛应用于商业和社会活动中，其安全性受到人们的重点关注。本章对传统投票方式和分类、远程网络投票的分类和模型、远程网络投票的通信模型进行了详细研究，为后面的研究工作打下了坚实的基础。

参考文献

［１］上海宝山路街道．首次网络投票选举居委会．人民日报，２００６‐０８‐１０（第１０版）．

［２］ Xxxx T E ，Xxxxxxx X ．Internet voting in comparative perspective ：The case of estonia ．Politi‐ cal Science & Politics ，２００９，４２：４９７～５０５．

［３］ Brace K W ．Nation sees drop in use of electronic voting equipment for ２００８ election‐A first ，

election data service ．http ：／／w ww ．electiondataservices ．com ［２０１２‐３‐２４］．

［４］ U ．S ．Election Assistance Commission ．A survey of internet voting ．http ：／／w ww ．eac ．gov ／as‐

sets／１／Documents／SIV‐FINAL ．pdf ［２０１２‐３‐２４］．

［５］ Xxxxxxx X X ，Xxxx T E ．Point ，click ，and vote ：The future of internet voting ．http ：／／w ww ．

brookings ．edu ／press／books／pointclickandvote ．html［２０１２‐３‐２４］．

［６］ Benaloh J ， Xxxxxxxx D ．Receipt‐free secret‐ballot elections ／／Proceeding of the ２６th Annual ACM Symposium on Theory of Computing ，New York ，１９９４：５４４～５５３．

［７］ Xxxx X ，Xxxxxx X ．Receipt‐free mix‐type voting scheme／／Proceeding of the １４th Annual In‐ ternational Conference on Theory and Application of Cryptographic Techniques ，Saint‐Malo ，

１９９５：３９３～４０３．

第１章绪论 · ７ ·

［８］ Xxxxxxx R ，Dwork C ， Xxxx M ，et al ．Deniable encryption／／Proceeding of the １７th Annual International Cryptology Conference on Advances in Cryptology ，Santa Xxxxxxx ，１９９７：９０～

１０４．

［９］ Xxxxxx R ，Xxxxxxxx M ，Xxxxxxxxxxxx B ，et al ．M ulti‐authority secret ballot elections with linear work ／／ Proceeding of the １５th Annual International Conference on Theory and Appli‐ cation of Cryptographic Techniques ，Saragossa ，１９９６：７２～８３．

［１０］ Cramer R ，Xxxxxxx X ，Xxxxxxxxxxxx B ．A secure and optimally efficient multi‐authority election scheme／／Proceeding of １６th Annual International Conference on Theory and Appli‐ cation of Cryptographic Techniques ，Konstanz ，１９９７：１０３～１１８．

［１１］ Baudron O ，Fouque P A ，Pointcheval D ，et al ．Practical multi‐candidate election system ／／ Proceeding of the １２th Annual ACM Symposium on Principles of Distributed Computing ， New York ，２００１：２７４～２８３．

［１２］ Xxxxxxx I ，Xxxxx X ．A generalization ，a simplification and some applications of paillier’s probabilistic public‐key system ／／Proceeding of the ４th International Workshop on Practice and Theory in Public Key Cryptography ： Public Key Cryptography ，Cheju Island ，２００１：

１１９～１３６．

［１３］ Xxxxxxx I ，Xxxxx X ，Nielsen J B ．A generalization of xxxxxxxx’x public‐key system with ap‐ plications to electronic voting ．International Journal of Information Security ，２０１０，９（６）：

３７１～３８５．

［１４］ Hirt M ，Xxxx X ．Efficient receipt‐free voting based on homomorphic encryption ／／ Proceed‐ ing of the １９th International Conference on Theory and Application of Cryptographic Tech ‐ niques ，Bruges ，２０００：５３９～５５６．

［１５］ Xxx X ，Xxx X ．Receipt‐free electronic voting scheme with a tamper resistant randomizer ／／ Proceeding of the ５th International Conference on Information Security and Cryptology ，Se‐ oul ，２００２：４０５～４２２．

［１６］ Xxxxxxxx Z ．Electronic Voting Schemes ［Master Thesis］．Bratislava ：Comenius University ，

２００２．

［１７］ Neff A ．Detecting malicious poll site voting clients ．http ：／／votehere ．com ／vhti／documenta‐ tion／psclients ．pdf ［２０１２‐３‐２４］．

［１８］ Xxxxxxx A ， Xxxx X ．T he vector‐ballot approach for online voting procedures ．T owards Trustworthy Elections ，２０１０：１５５～１７４．

［１９］ Acquisti A ．Receipt‐free homomorphic elections and w rite‐in voter verified ballot ．T echnical Report of International Association for Cryptologic Research and Carnegie Mellon Institute for Software Research International ，２００４．

［２０］ xx ．Internet 投票协议研究［博士后出站报告］．武汉：武汉大学，２００６．

［２１］ Meng B ．A secure internet voting protocol based on non‐interactive deniable authentication protocol and proof protocol that two ciphertexts are encryption of the same plaintext ．Jour‐ nal of Networks ，２００９，４（５）：３７０～３７７．

· ８ · 安全远程网络投票协议

［２２］ Meng B ，Xx Z M ，Xxx X ．A receipt‐free coercion‐resistant remote internet voting protocol without physical assumptions through deniable encryption and trapdoor commitment scheme ．Journal of Software ，２０１０，５（９）：９４２～９４９．

［２３］ Meng B ．A critical review of receipt‐freeness and coercion‐resistance ．Information Technolo‐ gy Journal ，２００９，８（７）：９３４～９６４．

第 2 章相关的密码技术

２畅１公钥密码体制

公钥密码体制是密码编码学重要的组成部分，其加密算法和解密算法使用不同的密钥，一个是公钥，一个是私钥。这里主要介绍在远程网络投票协议中用到的 RSA 、ElGamal［１～２］、BCP［３］和 Paillier［４～６］公钥加密体制。

2畅1畅1 RSA 公钥加密体制

（１）密钥建立。

① 随机选择两个素数 p 和 q ， p ≈ q 。 ② 计算 n ＝ pq ，矱（n）＝（p －１）（q －１）。

③ 随机选取整数 e ，满足１＜ e ＜矱（n），gcd （e ，矱（n））＝１。 ④ 计算 d ，ed ＝１mod 矱（n）。

⑤ 公钥（n ，e），私钥 d 。

（２）加密算法。

加密明文 m ，m ＜ n ，则密文 c ＝ me mod n 。

（３）解密算法。

解密密文 c ，得到明文 m ＝ cd mod n 。

2畅1畅2 ElGamal 公钥加密体制

（１）密钥建立。

① 随机选择素数 p 。 ② g 是 Zp 中的乘法群 Z倡的一个生成元。 ③ 选择随机数

α ，１ ≤ α ≤ p －２，计算 h ＝ gα 。 ④ 公钥（p ，g ，h），私钥 α 。

（２）加密算法。

随机选择 k ，０ ≤ k ≤ p －２，则 m 的密文：c ＝（x ，y）＝（gk mod p ，mhk mod p）。

（３）解密算法。

xα

解密密文 c ，得到明文 m ＝ y mod p 。

2畅1畅3 Paillier 公钥加密体制

（１）密钥生成。

① 选择两个大素数 p ，q ，令 n ＝ pq ，矱（n）＝（ p －１）（q －１），λ＝ lcm（ p －１，q －１）。

· １０ ·

安全远程网络投票协议

倡 λ ２

u －１

② 随机选择 g（g ∈ Zn２），使得 g 满足 gcd（L （ g mod n ），n）＝１，其中 L （u）＝ n ，

其中 u ∈ Sn ＝｛ u ＜ n２｜n２＝１mod n｝。明文域为 Zn ，密文域为 Z倡２。 ③ 公钥（n ，g），私

钥（p ，q）。

（２）加密算法。

明文 m 且 m ＜ n ，选择随机数 r 且 r ∈ Zn ，则密文 c ＝ g

· r mod n 。

（３）解密算法。

倡

L （cλ mod n２）

m n ２

（ mod ng

密文 c ＜ n２，明文 m ＝ L λ ２

2畅1畅4 BCP 公钥密码体制

）mod n 。

２００３年，Xxxxxxx 等［３］提出 BCP 公钥密码体制，它保留了 Cramer‐Shoup 模式的特点，同时基于两个陷门，具有两种不同解密模式，可看作是 ElGamal 密码体制的加法同态的变种。令 h 和 g 是最大界中 G 的两个元素。如果 h ＝ gx ，x ∈ R ［１， λ（ N２）］，那么 x 就以很大的概率包含 ord（G），同时 h 是最大界。 ZN 是消息空间。

（１）密钥生成。

选择一个随机数 α ∈ ZN ，随机值 a ∈ ［１，ord （G）］，计算 g ＝ α mod N 和 h ＝

倡２２２

ga mod N２。公钥是三元组（ N ，g ，h），与之相对应的私钥是 a 。

（２）加密算法。

Xxx 得到 Xxxxx 的公钥（ N ，g ，h）。 Xxx 想加密明文 m ∈ ZN 发送给 Xxxxx 。计算：首先在 ZN２中均匀选择 r ，密文（A ，B）是 A ＝ gr mod N２，B ＝ hr （１＋ m N ）mod N２，然后发送（A ，B）给 Xxxxx 。

（３）解密算法。

从密文（A ，B）中恢复明文 m ，Xxxxx 计算如下：

B／（Aa ）－１mod N２

① 一种情况，知道 a ，Xxxxx 通过 m ＝ N 恢复 m 。 ② 另外一种

情况，如果知道因子分解结果：Xxxxx 可以得到 amod N 和 rmod N 。令 armod ord

D －１mod ２N

（G ）＝ γ１＋ γ２ N ，那么可以非常高效得到 γ１＝ armod N 。 Alice 根据 m ＝

倡

N · π（mod N）可以恢复明文，其中，π 是在 ZN 的 λ（ N）的逆。

２畅２秘密共享

１９７９年，Shamir［７］和Blakley［８］分别独立提出秘密共享思想，并分别给出了两种门限密码体制：xx朗日内插多项式体制（是完善的）和矢量体制（是不完善的）。

第２章相关的密码技术 · １１ ·

设秘密 s 被分成 n 份部分信息，每一个部分信息被称为一个秘密分量或共享份额

（也可以称为影子或秘密碎片），每个秘密分量均有一个参与者持有，若通过其中任意 t 个或多余 t 个参与者所持有的秘密分量可以重构 s ，而通过少于 t 个参与者所持有的密钥分量无法重构 s ，则称这种方案为（t ，n）秘密共享门限方案，其中 t 为方案的门限值。如果方案还满足任意一组参与者，若其个数少于 t ，则由他们所持有的秘密分量得不到秘密 s 的任何信息，称（t ，n）秘密共享门限方案是完善的。一个

（t ，n）秘密共享门限方案一般由两部分组成：一个是秘密分量的产生过程；另一个是秘密恢复过程。

Shamir 门限方案的构造基于多项式 Lagrange 插值公式。

设 f （xi ），i ＝１，２，⋯ ，n ，｛（x１，y１），⋯ ，（ xt ，yt ）｝是平面上 t 个点构成的点集，其中 xi ，i ＝１，⋯ ，t ，均不相同，那么在平面上存在一个唯一的 t －１多项式 f （ x ）通过这 t 个点。若把秘密 s 取作 f （０），n 个秘密分量取作 f （ xi ），i ＝１，２，⋯ ，n ，那么利用其中的任意 t 个秘密分量可重构 f （x），从而可以得到秘密 s 。

方案一般构造方式如下：设 G F（q）是一个有限域，其中 q 是一个大素数，满足 q ≥ n ＋１，秘密 s 是 G F （q）＼｛０｝上均匀选取的一个随机数，表示为（ i ＝１，２，⋯ ， t －１）。 t －１个系数 a１，a２，⋯ ，at －１的选取满足

ai ∈ R G F（q）＼｛０｝， i ＝１，２，⋯ ，t －１

在 G F（q）上构造一个 t －１次的多项式

f （x）＝ a０＋ a１ x ＋ ⋯ ＋ at －１ xt －１

其中，a０＝ s 。

n 个参与者记为 P１，P２，⋯ ，Pn ，Pi 分到的秘密分量为 f （i）。如果任意 t 个 Pi１，⋯ ，Pit （１ ≤ i１＜ i２＜ ⋯ ＜ it ≤ n）要想得到秘密 s ，可以使用｛（il ，f （ il ））｜l ＝１，⋯ ， t｝构造如下线性方程组：

a０＋ a１（i１）＋ ⋯ ＋ at －１（i１）t －１＝ f （i１）

a０＋ a１（i２）＋ ⋯ ＋ at －１（i２）t －１＝ f （i２）

⋯

a０＋ a１（it ）＋ ⋯ ＋ at －１（it ）t －１＝ f （it ）

∑

modq

因为 il （１ ≤ l ≤ t）均不相同，所以可由 Lagrange 插值公式构造多项式

f （x）＝

由多项式可得秘密 s ＝ f （０）。

j ＝１

∏

f （ij ）

l ＝１

l ≠ j

（x － ij ）

（ij － il ）（）

然而参与者仅需要知道 f （x ）的常数项 f （０），不需要知道整个多项式 f （ x ），

所以可以通过下式求出 s ：

∑

s ＝

j ＝１

∏

f （ij ）

l ＝１

l ≠ j

－ il

（ij － il ）

（modq）

· １２ · 安全远程网络投票协议

由此可知，如果由 t 个参与者那么一定能获得秘密 s 。对于任何一个 s ∈ G F（q）存在唯一的多项式满足方程组１（可设 a０＝ s）所以若有 t －１个参与者，只能得到t －１个方程，而对 f （x ）来说，共有 t 个未知数，所以得不到关于秘密 s 的任何信息，因此这个方案是完善的。

２畅３门限公钥加密

这里介绍 Xxxxxxxx［９］提出的 RSA ，Xxxxxx 等［１０，１１］提出的 ElGamal 以及

Baudron 等［１２］提出的 Paillier 加密体制的门限版本。

2畅3畅1 RSA 公钥加密的门限版本

（１）密钥生成算法。

可信中心随机选择两个强素数 p ，q ，使得 p ＝２ p′ ＋１，q ＝２ q′ ＋１，其中，p′ ，q′也是素数。令 n ＝ pq ，n′ ＝ p′ × q′ ，取素数 e ∈ Zn′ ，e ＞ l 。 RSA 公钥为 PK ＝（n ，e）。利用欧几里得算法计算 d ∈ Zn′ ，使得 de ＝１mod n′ 。利用 Shamir 秘密共享模式：令

f （０）＝ d 。对 i ＝１，⋯ ，t ，随机选择 f i ∈ Zn′ ，令 f （ X ）＝ i∑ f i X 。秘密密钥SKi ＝

＝０

倡

di ＝ f （i）mod n′ ，验证密钥 V K ＝ v ，它是由 Zn２中的平方数构成的循环子群中的一个元素，子验证密钥 V K i ＝ vdi mod n ，i ＝１，⋯ ，l 。

（２）加密算法。

加密消息 m ，计算 c ＝ me mod n 。

（３）共享解密算法。

令 Δ ＝ l ！，计算 ci ＝ c２ Δ di mod n ，并且用零知识证明 log c４ Δ c２＝ logV K V K i 。

（４）秘密重构算法。

如果少于 t 个正确解密的秘密共享，则算法失败。否则令 S 是 t ＋１个秘密共享的集合。计算对于任意的 i ∈ ｛０，⋯ ，l｝，j ∈ S ，定义

∏

由 lagrange 插值公式得

μi ，j ＝ Δ ×

j′ ∈ S＼｛ j｝（ i － j′）

∏

∈

j′ ∈ S＼｛ j｝ i － j′

Δ （i）＝（）mod mf f j∑

μi ，j

j ∈

因为 f （０）＝ d 可得

m４ Δ ＝ c４ Δ d ＝ c４ Δ f （０）＝ ∏ c４ Δ μ

２２２ S

０，j

j ∈ S

f （ j ）＝ ∏ c２ μ

０，j

j ∈ S

mod n

根据gcd（４Δ２，e）＝１可用扩展的欧几里得算法计算出 a ，b 使得 a× ４Δ２＋ b × e ＝１。得

第２章相关的密码技术

m ＝ ma × ４ Δ２ mb × e ＝（m４ Δ２）a × cb mod n

2畅3畅2 ElGamal 公钥加密的门限版本

（１）密钥生成算法。

· １３ ·

执行密钥生成协议［９］，每个权威机构 A j 都拥有秘密 s 的共享 s j ∈ Zq ，其中，s是 ElGamal 加密体制中的私钥。权威机构把 hj ＝ gsj 公开。应用 Lagrange 插值可以从任何 t 个共享中重构秘密 s 如下：

s ＝ ∑ s j λj ，Λ ， λj ，Λ ＝ ∏ l

j ∈ Λ

l ∈ Λ＼｛ j｝ l － j

这正是 Xxxxxx 的（t ，n）门限秘密共享。公钥 h ＝ gs 公开。

（２）解密算法。

为不重构秘密 s ，而可以解密（x ，y）＝（gα ，hα m ），权威机构执行协议：① 每个权威机构 A j 广播 w j ＝ xs j ，并且以零知识证明 log g hj ＝ log x w j ；② Λ 表示任意 t 个通过了零知识证明的权威机构集合。恢复明文

m ＝

j ∈ Λ

x s

y ， xs ＝ x ∑ s j λ j ，Λ ＝

∏

j ∈ Λ

w λj ，Λ

2畅3畅3 Paillier 加密的门限版本

（１）密钥生成算法。

定义 Δ ＝ l ！，其中，l 是服务器的个数。选择整数 n ，n 是强素数 p ，q 的乘积，令

倡

p ＝２ p′ ＋１，q ＝２ q′ ＋１，gcd（n ，φ（n））＝１。令 m ＝ p′q′ 。随机选择 β ∈ Zn ，（ a ，b） ∈

Zn × Zn 。令 g ＝（１＋ n） × b mod n 。秘密密钥 SK ＝ β × m 采用 Xxxxxx （t ，n）模

倡倡 a n ２

∑

式共享，令 a０＝ βm ，随机选择 ai ∈ ｛０，⋯ ，n × m －１｝，令 f （X ）＝

i ＝０

ai X i 。服务器

Pi 的秘密共享 S i ＝ f （i）mod nm ，公钥 PK ＝（g ，n ，θ＝ L （ gmβ ）＝ amβmod n），验证密钥 V K ＝ v ，它是由 Z倡２中的平方数构成的循环子群中的一个元素，子验证密钥

V K i ＝ vΔ si mod n２。

（２）加密算法。

倡

加密消息 M ，随机选择 x ∈ Zn ，计算 c ＝ gM

x n mod n２。

（３）共享解密算法。

第 i 个参加者用自己的秘密共享 si 解密 ci ＝ c２ Δ si mod n２，并且以零知识证明

２

logc４ Δ ci ＝ log v Δ vi 。

（４）秘密重构算法。

如果少于 t 个正确解密的秘密共享，则算法失败。否则令 S 是 t ＋１个秘密共享的集合。计算

· １４ · 安全远程网络投票协议

M ＝ l

其中

j∏∈ S

c２ μ

j 0 ，j

n２ × １

mod

４Δ２

θmod n

j′ －１

μ０，j ＝ Δ × ∏ j′ ∈ S＼｛ j｝ j′ ∈ Z

２畅４盲签名

１９８３年，Chaum［１３］提出了盲签名的概念。盲签名在电子商务、电子政务中有着重要的应用。盲签名是一种特殊的数字签名，指签名者并不知道所签文件或消息的具体内容，而文件或消息的拥有者又可以通过脱盲后得到文件或消息的签名。盲签名的原理如图２畅１所示。

图２畅１盲签名

需要签名者把要签名的消息 m 通过盲变换为 m′ ，m′隐藏了明文 m 的内容。把 m′发送给签名生成者进行签名，得到签名 s′ 。需要签名者利用脱盲变换得到 m的签名 s 。这样请求签名者得到了 m 的签名 s ，而签名者不知道 m 的内容。

下面介绍基于 RSA 的盲签名算法。

签名者的公钥（n ，e），私钥 d 。请求签名者想得到签名者对 m 的盲签名：① 请求签名者盲化 m 为 m′ ＝ mre mod n ，r 是随机数，r ∈ R Zn ；把 m′发送给签名者。 ② 签名者生成 m′的签名 s′ ＝ m′d mod n ，发送给请求签名者；③ 请求签名者计算 s ＝ s′ ＝

m′d

md red

md r d

r ＝ r ＝

r ＝ m mod n 得到 m 的签名 s 。

关于可证明安全的门限盲签名可以参看文献［１４］，［１５］。

２畅５同态加密

Paill

首先介绍同态加密、加法同态和乘法同态的概念，然后给出 RSA 、ElGamal 和

ier 公钥加密体制具有的同态属性。

（１）同态加密。

加密函数 E（）是同态的，如果给定密钥 k ，M 是明文集合，C 是密文集合，加密函数 E（）满足

第２章相关的密码技术

橙 m１，m２ ∈ M E（m１） ⊙ E（m２）＝ E（m１ ⊙ m２）

（２）乘法同态。

· １５ ·

如果已经知道 E（m１），E（m２）是明文 m１，m２的密文，任何人都可以得到 m１ ×

m２的密文 E（m１ × m２），即可以找到这样的运算碅使得

橙 m１，m２ E（m１ × m２）＝ E（m１）碅 E（m２）

（３）加法同态。

如果已经知道 E（m１），E（m２）是明文 m１，m２的密文，任何人都可以得到 m１＋

m２的密文 E（m１＋ m２），即可以找到这样的运算⊕使得

橙 m１，m２ E（m１＋ m２）＝ E（m１）⊕ E（m２）

（４） RSA 公钥加密体制。

假设公钥（n ，e），私钥 d 。 m１，m２ ∈ M ，c１＝ E（m１）＝ m１ e mod n ，c２＝ E（m２）＝

m２ e mod n 那么

c２ × c２＝ E（m１） × E（m２）＝（m１ e mod n） × （m２ e mod n）＝（m１ × m２）e mod n＝ E（m１ × m１）

因此 RSA 算法具有乘法同态的性质。

（５） ElGamal 公钥加密体制。

假设公钥是（G ，p ，g ，y），G 群，p 群的界，g 是生成元，y ＝ gz mod p ，密钥 z ，

m１，m２ ∈ M ，x１，x２是随机数，则

c１＝ Ex１（m１）＝（g mod p ，y m１ mod p）， c２＝ Ex （m２）＝（g mod p ，y m２ mod p ）

x１ x１ x２ x２

２

c２ × c２＝ Ex１（m１） × Ex２（m２）＝（g mod p ，y m１ mod p） × （g mod p ，y m２ mod p ）

x１ x１ x２ x２

＝（gx１ gx２ mod p ，yx１ yx２ m１ m２ mod p ）＝（gx１＋ x２ mod p ，yx１＋ x２ m１ m２ mod p）

＝ Ex１＋ x２（m１ × m２）

因此 ElGamal 具有乘法同态性质。

（６） Paillier 公钥加密体制。

Paillier 算法是概率公钥加密体制，公钥（n ，g），私钥（ p ，q），m１，m２ ∈ M ，x１，x２

是随机数，则加密算法 Ex （m）＝ gm x n mod n２，解密算法 D（），存在

１

２

c１＝ Ex （m１）＝ gm１ x１ n mod n２， c２＝ Ex （m２）＝ gm２ x２ n mod n２

c１ × c２＝ Ex１（m１）Ex２（m２）＝（g x１ mod n ） × （g x２ mod n ）

m１ n ２ m２ n ２

１２

＝ gm１＋ m２（x１ x２）n mod n２＝ Ex x （m１＋ m２）

因此 Paillier 加密算法具有加法同态的性质。

加法同态属性如下：

橙 m１，m２ ∈ Zn ，k ∈ N

D（E（m１）E（m２）mod n２）＝ m１＋ m２ mod n D（E（m）k mod n２）＝ kmmod n

D（E（m１）gm２ mod n２）＝ m１＋ m２ mod n

· １６ ·

安全远程网络投票协议

D（E（m ）m２ mod n２）＝ D（E（m ）m２ mod n２）＝ m m mod n

１１１２

自盲属性（self‐blinding ）如下：

橙 m１，m２ ∈ Zn ，r ∈ N

D（E（m）rn mod n２）＝ m

２畅６混淆网

混淆网（mix‐net）是实现通信匿名性的一种关键技术。匿名性指用户在访问资源或服务时不能泄露其身份。２００６年，T atli 等［１６］把匿名性分为两种：通信匿名性和内容匿名性。通信匿名性受到人们的重点关注。他们同时指出有三种方法可以实现通信匿名性：代理、对等网和混淆网［１７］。

基于代理的方法实现通信匿名性，发送方和接收方必须相信从发送方收到的消息已经进行了某种变换来隐藏发送方的身份。反之，当代理从接收方得到消息，把消息发送给真正的发送方。通常，基于代理的方法存在两个缺点：一个是用户必须无条件信任代理，另外一个是在用户和代理之间的信道没有保护机制。基于对等网实现通信匿名性，用户随机选择发送消息的路径，把消息发送给最终的接收者。这种方法不需要信任系统中的某一方。基于混淆网来实现通信匿名性，混淆网由一系列的实体∶ 混淆服务器组成。每个混淆服务器都有自己的公钥。每个混淆服务器接收到加密的消息，然后解密，批处理，重新排序，隐藏发送者的相关信息后发送给接收者。在远程网络投票协议中，主要用这种方法实现匿名性。安全的混淆网应该具有正确性、隐私性、健壮性、高效性和普遍可验证性。正确性指如果所有的混淆服务器是诚实的，那么结果就是正确的。隐私性隐含着如果一个固定最小数量的混淆服务器是诚实的，那么发送方的隐私性就可以得到保证。健壮性是指如果一定数量的混淆服务器是诚实的，那么可以防止任何欺骗和攻击。高效性指验证者的负载与混淆服务器的数量之间没有关系。普遍可验证性是指解密结果的正确性可以被任何验证者验证。主要思想是通过洗牌改变和修改对象的顺序来隐藏最初的和最后的排序之间的对应关系。 Xxxxx 把它作为匿名信道的一种实现方式。

１９８１年，Chaum［１７］提出第一个基于 RSA 的混淆网，并且证明可以抵抗被动攻击。被动攻击者可以监控在混淆服务器之间所有通信但是不能够得到混淆服务器内部每个混淆的排列。１９９０年，Xxxxxxxxx［１８］指出发送方的主动攻击比简单的重复密文攻击更加的复杂。１９９５年，Xxxx 和 Xxxxxx［１９］基于零知识证明，首先提出一个普遍可验证的混淆网。主要思想是每个混淆服务器必须提供其正确执行相关操作的零知识证明。１９９７年，Xxxxx 等［２０］证明健壮的混淆网同时也是普遍可验证的。２０００年，M itom 和 Xxxxxxxx［２１］证明如果 κ 是安全参数，t 标识邪恶的混淆服

第２章相关的密码技术 · １７ ·

务器个数，那么每个混淆服务器的计算复杂度是 O （κt N ），外部验证者的计算复杂度也是 O（κt N ）。２０００年，M itom 和 Xxxxxxxx［２１］指出在 Chaum 混淆网中应用的是 RSA 加密体制，因此，每个密文的大小与混淆服务器的个数是成正比关系。

１９９８年，A be［２２］设计了一个健壮的混淆网，其外部验证者计算复杂度是O （κN）。

２０００年，Xxxxxxxxx［２３］设计了一个更加高效健壮的混淆网，然而其不具有普遍可验证性，在２０００年，Desmedt 和 Xxxxxxxx［２４］攻破了它。１９９９年，Xxxxxxxxx［２５］又提出一个健壮的混淆网（flash mixing ），可以抵抗攻击［２４］。２０００年，M itom 和 Kuro‐ sawa［２１］应用一个变种攻击［２４］，攻破了混淆网［２５］，同时他也给出了防止此攻击的解决方法。２００７年，Li 等［２６］发现混淆网［２７］不具有（t ，N‐２）适应性。１９９５年，Pfitz‐ mann［２８］提出了一个通用的对混淆网的攻击方法。１９９６年，M ichels 和 Xxxxxxx［２９］又提出了其他的攻击方法。２００３年，Wikstr迸m［３０］提出了对协议［３１］的攻击方法。同年，A be 和 Xxxx［３２］独立发现了对混淆网［３１，３３］的攻击方法，同时给出了匿名性和健壮性的形式化模型，但是没有提出具有这些安全性的混淆网。２００４年， Wikstr迸m［３４］提出了普遍可组合混淆网的思想，同时也给出了一个完整的构造和证明。一个非常重要的构造混淆网的工具是可证明的扰乱（proof of shuffle ）：通过每个混淆服务器执行一个可验证的扰乱，观察者可以确信每个混淆服务器在正确的运行。对多个数据项，如果多个相互不信任的实体连续的执行了多个可验证的扰乱，那么任何人不知道洗牌的结果。一个可验证的扰乱的输入是 n 个加密的消息，然后扰乱这些消息，也就是对它们进行随机排序，同时通过再加密替换掉原来的消息，输出扰乱的和再加密的消息。２００１年，Neff［３５］、Xxxxxxx a 和 Sako［３６］分别独立地提出了实现可验证扰乱高效算法。２００３年，Groth［３７］对 Neff 的方法进行了扩展并且对其效率进行了改进。后来，其他的作者也对其进行了改进和完善［３８，３９］。２００５年，Wikstr迸m［４０］首先提出一个基于 ElGamal 密码体制的混淆网。每个混淆服务器对输入部分的解密和洗牌，叫做发送方可验证。它没有用到再加密技术。同时基于 UC 框架证明了其存在任意少数混淆服务器腐败情况下的安全性。同时，他构造了第一个加密‐置换扰乱的证明，表明其可以转换为 UC 框架下的零知识证明。２００７年，A dida 和 Wikstr迸m［４１］基于 BGN 密码系统构造了一个解密扰乱和基于 Paillier 加密系统再加密扰乱，但是效率非常低。２０１２年，Xxxxxxx等［４２］对混淆网的最新发展现状作了介绍。

下面介绍混淆网的基本结构，如图２畅２所示。 EPK （m）表示用混淆服务器的公

钥 PK 加密 m 。

假设有 n 个消息的发送者 S１，⋯ ，Si ，⋯ ，Sn ，每个 Si 想发送消息 mi 给 Ri ，如果采用混淆网，则 Si 和 Ri 之间的对应关系是秘密的。

（１）简单的混淆网匿名通道，存在一个混淆网 x 服务器。

每个 Si 选择一个随机数 ri ，计算 ci ＝ EPK M （ ri ，Ri ，EPK R （mi ）），混淆网服务器

· １８ · 安全远程网络投票协议

解密，丢掉 ri ，以字母排列发布 Ri ，EPK R （mi ）。

在这个协议中，只有混淆网服务器知道 Si 和 Ri 之间的对应关系，其他人都不知道。为了更好地隐藏 Si 和 Ri 之间的对应关系，可以用 k 个混淆网服务器， Mix１，⋯ ，M ixk 。

（２） k 个混淆服务器的匿名通道，存在 k 个混淆服务器。

２

每个 Si 选择一个随机数 ri ，计算

１

EPK

（r１，EPK

（ r２，⋯ ，EPK k

（ rk ，Ri ，EPK R

（mi ），⋯ ）））

此时，一般说 Si 发送 Ri ，EPK R （mi ）到 k 个混淆匿名通道。

２

Mix１解密，丢掉 r１，把 EPK

排列在公告板上。

（r２，⋯ ，EPK k

（rk ，Ri ，EPK R

（mi ），⋯ ）），以字典顺序

Mix２，⋯ ，M ixk －１执行相同的动作。

最后 Xxxx 把 Ri ，EPK R （mi ）在公告板上以字典顺序排列。

图２畅２混淆网结构

在这个协议中，只要有一个混淆服务器诚实，那么 Si 和 Ri 的对应关系就是秘密的。

２畅７ Fiat‐Shamir 启发式

１９８７年，Fiat 和 Shamir［４３］提出了一个通用方法，可以将验证者诚实的安全零知识协议转化为数字签名方案。把这种方法叫做 Fiat‐Shamir 启发式。

一般用（commit ，challenge ，response）表示一个验证者诚实的零知识协议的副本，为了构造消息 m ∈ ｛０，１｝倡的数字签名，应用散列函数 H A S H ：challenge ← H A S H （m ‖ commit）。 Fiat‐Shamir 启发式是可以公开验证的，可以像验证数字签名那样验证隐藏在散列函数中的断言。

２畅８离散对数相等知识证明

离散对数相等的知识证明［８，１０，１１］（proofs of knowledge for equality of discrete

第２章相关的密码技术

logarithms）是用知识证明的方式来证明两个离散对数的相等。

· １９ ·

示证者有（g ，x ，h ，y）（g ，x ，h ，y ∈ Zp ）。而且知道 α ∈ Zp 满足 x ＝ gα 和 y ＝ hα 。验证者是诚实的验证者。图２畅３描述的是交互式的版本。应用 Fiat‐Shamir 启发式可以把图２畅３中的交互式的版本变为非交互式的版本。

非交互式的版本如下：首先示证者还是按照非交互式版本中那样计算，只是令挑战 c ＝ H A S H （a b x y）。然后，验证者检查

？

c ＝ H A S H （gr x － c hr y － c x y）

图２畅３关于 log g x ＝ log h y 的知识证明

２畅９ BCP 承诺方案

陷门承诺方案［４４］的抗碰撞性是指除非知道陷门，否则找到两个不同的输入，产生相同的值是不可能的。另一方面，知道陷门信息可以很容易构造碰撞。一个陷门承诺方案是由密码生成算法、承诺函数和碰撞构造函数组成的。下面介绍陷门承诺的概念和 BCP 陷门承诺方案［３］。

（１）陷门承诺。

陷门承诺也叫做变色龙承诺（chameleon commitment ）。 C 是一个函数，输入是（yi ，w ，r），yi 是验证者的公钥，对应的私钥是 xi ，w 是承诺的值，r 是一个随机数。 C 是一个陷门承诺如果满足以下条件：

① 如果不知道 xx 的秘密部分，承诺是绑定的，即不能够找到一对碰撞（w１，

r１），（w２，r２）使得 C（xx ，w１，r１）＝ C（yi ，w２，r２）。

② 给出 yi 和 C （xx ，w ，r），不能够计算出 w 。

③ 利用 yi 的秘密部分，很容易计算出任意数量的碰撞对。

Document Metadata

Table of Contents

２０１３年６月第一版开本：B５（７２０ × １０００）

Document Metadata

２０１３ 年 ６ 月第 一 版 开本 ：B５ （７２０ × １０００）

Document Metadata

２０１３年６月第一版开本：B５（７２０ × １０００）