目录
前言
近几年来，云计算、物联网、移动互联网等新概念、新技术被先后提出，促使信息技术飞速发展。同时，人类生活、沟通方式也随着新技术的普及不断变化。一方面，人类的沟通方式已经由传统的书信、电报、电话形式发展为使用计算机、智能手机、个人数字助理和平板计算机等网络终端设备；另一方面，电子媒体、网络技术不断发展，信息技术不断融入到社会化服务体系中。上述应用的快速进步，又促进了其他信息技术（如数据挖掘、电子商务、云计算技术等）的快速进步。但是，信息技术在给人们带来便捷的同时，信息安全问题也不断凸显。例如，近几年来，信息泄露事件不断发生，国内外多家著名互联网站、银行、公司发生信息泄露事件；网络攻击事件不断发生，且攻击技术不断升级，所造成的影响也越来越恶劣；随着智能终端的不断发展和推广，针对移动智能终端的恶意攻击比率不断提高。信息安全事件频繁发生，在给人们带来经济损失的同时，也给人们敲醒了安全警钟。各国政府和人民开始高度关注信息安全。2014年2月27日，我国成立了“中央网络安全和信息化领导小组”。该领导小组着眼于国家安全和长远发展，统筹协调涉及经济、政治、文化、社会及军事等各个领域的网络安全和信息化重大问题，研究制定网络安全和信息化发展战略、宏观规划和重大政策，推动国家网络安全和信息化法治建设，不断增强安全保障能力。
安全多方计算融合了密码学和分布式计算技术，是信息安全领域的一个重要研究方向，是现代密码学的重要组成部分，具有重要的研究价值和意义。首先，密码学中已经实现了对称加密算法和公钥加密算法。按照事物从低级往高级发展的必然规律，安全多方计算是密码学发展的必然方向。其次，近几年来分布式计算尤其是云计算技术迅速发展。过去的惨痛教训告诉我们，在一项新技术发展的初期就需要充分考虑安全问题。而伴随着不断发生的云安全事故，云计算安全也逐渐引起了人们的关注。很多安全专家指出，云计算的广泛应用需要向云计算架构中加入更强大的安全措施以保证其安全性，促进云计算应用的重点是解决云计算所面临的各种安全问题。安全多方计算作为一种研究分布式计算环境下多个参与方计算安全性的技术，对保证云计算的安全具有重要意义。再次，安全多方计算具有广泛的应用场景。例如，将安全多方计算应用到拍卖、投票中，实现安全电子拍卖、电子投票；将安全多方计算和数据挖掘技术相结合，实现保护隐私的数据挖掘技术等。可见，对安全多方计算的研究具有重要的理论和应用价值。
作者在过去的学习过程中发现，市面上的现代密码学书籍中往往将安全多方计算作为其中一个章节进行介绍。事实上，安全多方计算发展至今，已经积累了丰富的基础理论和研究成果。本书以现代密码学中的安全多方计算为研究重点，带领读者学习密码学中安全多方计算的基础知识和近期研究成果，希望帮助读者尽快进入这一领域。本书的内容以作者攻读博士学位期间的研究成果为基础，结合国内外学者在安全多方计算领域的最新研究进展和作者对该领域的认识，经过仔细归纳整理而成。
本书共10章，第1～3章介绍基础知识，第4～10章介绍安全多方计算及其应用。其中，第6～10章分别介绍了安全多方计算在数据比较、科学计算、电子投票、计算几何及集合运算5个领域中的应用。
本书得以顺利完成，首先要感谢我的博士生导师——北京邮电大学罗守山教授。罗老师学识渊博、治学严谨、淡泊名利。罗老师带我走上了安全多方计算的研究之路。短短的博士三年，我不仅跟罗老师学到了如何做研究，更主要的是学习到了他严谨的治学态度和“仁远乎哉，我欲仁斯仁至矣”的精神品质。在此，再次感谢罗老师对我的悉心指导和辛勤培养。2010—2013年我参加了由罗守山老师创办的安全多方计算讨论组，由衷感谢庞雷博士、贾哲博士、耿涛博士、许芬博士，感谢他们将自己掌握的知识、学习方法和经验进行了无私的分享。还要感谢武汉理工大学的于晓敏为本书所做的不厌其烦的工作及电子工业出版社的王志宇编辑对本书出版所付出的辛苦劳动。
本书的出版还得到了首都经济贸易大学青年科学基金（2014XJQ016）、首都经济贸易大学青年科研启动基金（恶意模型下的安全多方计算技术）、国家社科基金项目（15AGL001）、北京市教委科技面上项目（KM201410038001）的支持，在此一并表示感谢。
由于水平有限，书中难免有谬误之处，恳请读者批评和指正。近些年来，安全多方计算乃至密码学的理论和技术都在飞速发展，由于篇幅有限，很多新理论和新成果未能在本书中体现，敬请读者谅解。
本书作者
孙茂华
第1章 绪论
1.1 密码学的发展历史
密码学是一门发展中的交叉学科，由于其古老而深奥，对一般人来说既神秘又陌生。过去，密码学仅用于军事领域。随着计算机的发展和普及，基于数学和计算机的密码学得到了迅猛发展。纵观密码学的发展历史，可以将密码学划分为经典密码学和现代密码学两个阶段。
20世纪80年代以前的密码学是一种艺术，被称为经典密码学。经典密码学阶段又被划分为两个时期。1949年之前是经典密码学发展的第一个时期，被称为古典密码学阶段。密码学的历史十分悠久。早在4000年前，埃及人就开始使用密码实现传递消息的保密性。这个阶段的典型密码技术有凯撒密码和维吉尼亚密码等。在这长达几千年的时间里，人们使用了纸、笔或者简单器械实现的代换或置换来满足消息加密的需求。1883年，Kerchoffs第一次明确提出了“加密算法应建立在算法的公开且不影响明文和密钥安全的基础上”的编码原则，这个原则得到了广泛的认可，是古典密码学阶段的重要成果。从1949年到1975年，密码学成为一门独立的学科，是经典密码学发展的第二个时期。1949年，美国数学家Shannon发表了论文《保密系统的通信理论》，论文在信息论的基础上阐述了关于密码系统分析、评价和设计的科学思想。文中所提出的破译密码的计算理论已和计算机理论中的计算复杂性理论结合起来，成为评价密码安全性的一个重要准则。Shannon 的这篇论文也成为近代密码学开始的标志。在经典密码学发展的第二个时期中，密码机的出现使信息保密由手工方式转换为机器自动计算，大大提高了信息安全保护水平；同时，数据的安全性不再基于算法的保密性，而是基于密钥的保密性。从使用者的身份来看，经典密码学阶段的成果主要被军事和智囊机构使用。例如，明朝著名抗倭将领、军事家戚继光发明并使用了“反切密码”用于传递军事机密，他还专门编写了一本《八音字义便览》用于培训情报人员和通信兵。第二次世界大战中，各个国家都致力于密码的截获和破译，密码技术成为直接影响二战胜败的重要因素。例如，1941年我国著名密码破译专家池步洲截获并破译了日本的一份密电，提前获知了日本准备偷袭珍珠港的情报。可惜，蒋介石将情报通报给美军之后并没有得到美军的重视，铸成了后来著名的珍珠港偷袭事件。在第二次世界大战中，英国成功破译了德军的“恩尼格码”密码（图1-1），帮助盟军掌握了第二次世界大战欧洲战场的主导权。
图1-1 恩尼格码密码机
1976年，Diffie和Hellman发表了《密码学新方向》，提出了一种新的密码设计思想，证明了通信双方在不传输密钥的情况下实现保密通信的可能性。这篇文章开创了公钥密码学的新纪元。从此，密码学进入了现代密码学阶段。20世纪80年代以后，计算机的性能得到了飞速提高，同时计算机网络逐步建立并发展起来。计算机网络将原来孤立的单机系统连接在一起，实现了信息和资源的共享。然而，随之而来的信息安全问题也不断凸显。由于信息在处理、存储、传输和使用上有严重的脆弱性，很容易被泄露、窃取、篡改、伪造和破坏。人们开始使用防火墙、入侵检测设备和安全路由器等方式来抵御安全威胁。防火墙、入侵检测设备和安全路由器等安全网关设备中使用了大量的密码学算法。近几年来，随着云计算、物联网、移动互联网等技术的进步和普及，新的安全威胁不断出现。这也促进密码学算法的不断发展。不同于经典密码学的军事化用途，现代密码学技术已经被广泛应用在日常生活中的各个方面。例如，银行使用密码学协议来保障网上银行的安全性；计算机基于密码学方法实现访问权限控制等。可以看出，现代密码学已经不再单纯为军方或智囊机构使用，而是成为国家机构、公司、组织和网民共同使用的技术。
1.2 现代密码学体制
现代密码学发展至今，主要分为密码编码学和密码分析学两个分支。
密码编码学致力于建立难以被敌手攻破的安全密码体制。一个密码系统通常由明文空间、密文空间、密钥空间、加密算法和解密算法五部分组成。被加密的原始信息称为明文，加密后的信息称为密文。加密过程就是根据一系列的规则（称为加密算法）将明文转换为密文的过程。解密过程是加密过程的逆过程，是指根据另外一系列规则（称为解密算法），将密文转换为明文的过程。加密过程和解密过程往往需要使用一对密钥进行控制，分别称为加密密钥和解密密钥。在密码编码学中，根据整个协议中的加密密钥和解密密钥是否相同可以将密码编码学算法划分为对称密码学算法和公钥密码学算法。
对称密码学算法的出现早于公钥密码学算法。在对称密码体制中，通信双方使用同一个密钥实现加密和解密。因此，对称密码体制也被称为是单钥密码体制。对称密码体制的安全性依赖于密钥的保密性，而不是算法的保密性。也就是说，即使加密算法是公开的，只要密钥没有公开，信息的保密性依然可以保证。流密码和分组密码是对称密码算法中最常见的两类算法。流密码采用逐字加密方式完成加密。分组密码首先将信息分组，每个分组中包含多个字符，然后逐组进行加密。对称加密体制中最大的问题是密钥的分发和管理非常复杂且实施代价很高。尤其是大型网络中，当用户较为分散且数量较多时，对称加密体制的开销极高。但是，对称加密算法由于加密速度快，适用于高速保密通信。在公钥密码学算法中，通信双方使用不同的密钥分别实现加密和解密。因此，公钥密码体制也被称为是双钥密码体制或非对称密码体制。用于加密的密钥被称为公钥，是公开的。用于解密的密钥被称为私钥，是需要保密的。公钥密码学算法的安全性要求之一是通过公钥计算出私钥在计算上是困难的。相对于对称加密体制，公钥加密体制在密钥的分配和管理上容易得多。但是，由于公钥加密体制多数使用复杂的数学计算，多数公钥密码学算法的运算效率远远低于对称密码学算法的运算效率。
密码分析学主要是研究如何根据已经收集到的信息获得明文。对密码进行分析的尝试称为攻击。当前，攻击的方法主要有穷举攻击、统计分析攻击和数学分析攻击三类。根据密码分析时所利用的数据来源不同，也可以将攻击分为唯密文攻击、已知明文攻击、选择明文攻击和选择密文攻击四类。
如今，现代密码学作为一门重要的交叉学科，在促进信息化的健康发展中起了十分重要的作用。同时，现代密码学已经同生物学、量子学等学科有效结合，形成了生物特征密码学、视觉密码学、量子密码学等多个子学科。
1.3 现代密码学与安全多方计算
安全多方计算是现代密码学的一个研究分支，是现代密码学的重要组成部分。不同的密码学分支研究的目的不同。例如，公钥密码学算法最早是为了解决密钥分配问题而诞生的。当然，公钥密码学算法发展至今已经不再仅仅应用于密钥分配。安全多方计算主要解决分布式环境下多个参与者之间的计算安全性问题。可以先通俗地这样理解安全多方计算所解决的问题：分布式环境下，通信双方或多方如何在保护自己输入信息的前提下，完成某个功能函数计算。
安全多方计算协议的构造需要使用密码学中的很多工具。例如，秘密共享、茫然传输、同态加密算法、零知识证明等。本书第3章将对这些密码学工具进行介绍。
安全多方计算作为密码学的一部分，也经常被作为底层模块去构造更加复杂的密码学协议。例如，本书第7.4 节中使用安全多方计算协议构造多秘密共享协议。
安全多方计算可以看成是密码学和不同应用场景下的计算问题相结合的产物。例如，安全多方集合运算是使用密码学技术解决分布式环境下多个参与者之间安全地计算集合的交、并或其他运算问题。按照应用场景的不同，可以将安全多方计算进行分类，如图1-2所示。
国际著名密码学家 Goldwasser 曾经说过：“安全多方计算今天所处的地位正是公钥密码学算法10多年前所处的地位。它是密码学研究中一个极其重要的工具，它在计算科学中的应用才刚刚开始，丰富的理论将使它成为计算科学中一个必不可少的组成部分。”
图1-2 安全多方计算的分类
本文所包含的内容系《现代密码学——基于安全多方计算协议的研究》一书。这些内容的目的是为了学术交流和个人学习，并且在此过程中尊重原作者的知识产权。特此对作者的辛勤工作表示感谢，并感谢他们为密码学领域做出的贡献。如有侵权行为，请及时联系我进行删除或修改。感谢您对知识产权的尊重与支持。