21世纪是信息的时代，除了电子信息科学技术继续高速发展之外，量子和生物等新型信息科学正在建立和发展。量子信息科学的研究和发展催生了量子计算机、量子通信和量子密码的出现。

由于量子信息的奇妙特性，使得量子计算具有天然的并行性。例如，当量子计算机对一个n量子比特的数据进行处理时，量子计算机实际上是同时对2n个数据状态进行了处理。正是这种并行性使得原来在电子计算机环境下的一些困难问题，在量子计算机环境下却成为容易计算的。量子计算机的这种超强计算能力，使得基于计算复杂性的现有公钥密码的安全受到挑战。

目前可用于密码破译的量子计算算法主要有Grover算法和Shor算法。对于密码破译来说，Grover算法的作用相当于把密码的密钥长度减少一半。而Shor算法则可以对目前广泛使用的RSA、EIGamal、ECC公钥密码和DH密钥协商协议进行有效攻击。这说明在量子计算环境下，RSA、EIGamal、ECC公钥密码和DH密钥协商协议将不再安全。

早在2001年IBM公司就研制出7个量子位的示例型量子计算机，向世界宣告了量子计算机原理的可行性。2011年9月2日，美国加州大学圣芭芭拉分校的科学家宣布，研制出具有冯·诺依曼计算机结构的量子计算机，并成功地进行了小合数的因子分解试验。2012年3月1日IBM宣布找到了一种可以大规模提升量子计算机量子位数的关键技术。

除了美国之外，加拿大的量子计算机取得了长足的发展。2007年2月加拿大D-Wave System公司宣布研制出世界上第一台商用16量子位的量子计算机。2008年5月提高到48量子位。2011年5月30日又提高到128量子位，并开始公开出售，1000万美元一台。美国著名军火制造商洛克希德·马丁公司购买了这种量子计算机，用于新式武器的研制。2013年初又大幅度地提高到512量子位，价格也上升为1500万美元一台。著名信息服务商谷歌公司购买了这种量子计算机，用于提高信息搜索效率和研究量子人工智能。

由上可知，量子计算机的发展大大超出了人们原来的预想。

必须指出的是，目前加拿大的量子计算机属于专用型量子计算机，它能够执行Grover算法，尚不能执行Shor算法。美国加州大学圣芭芭拉分校的量子计算机可以执行Shor算法，但量子位数太少。也就是说，目前的量子计算机尚不能对现有密码构成实际的威胁。但是，随着量子计算技术的发展，总有一天会对现有密码构成实际威胁。

在量子计算环境下我们仍然需要确保信息安全，仍然需要使用密码，但是我们使用什么密码呢？这是摆在我们面前的一个重大战略问题。

抗量子计算密码出版说明根据哲学的基本原理，任何事物有优点，必然也有缺点。据此量子计算机有优势，必然也有劣势。有其擅长计算的问题，必然也有其不擅长计算的问题。

实际上，量子计算机能够有效攻击许多现有密码，但并不能有效攻击所有的现有密码。基于量子计算机不擅长计算的那些问题构造密码，就可以抵抗量子计算的攻击。我们称能够抵抗量子计算机攻击的密码为抗量子计算密码。

出于对抗量子计算密码需求的紧迫性，国际上从2006年开始举办"抗量子计算密码学术会议（PostQuantum Cryptography）"，每两年举行一次，至今已举办了4届。已经产生了一批重要的研究成果，让人们看到了抗量子计算密码的新曙光。

为了使我国广大读者能够了解抗量子计算密码的发展，促进我国抗量子计算密码的科学研究和技术进步，清华大学出版社组织我们翻译出版了《抗量子计算密码》一书。

本书由12位作者供稿，并由其中的3位作者进行编著而成，这些作者都是抗量子计算密码领域各个分支的著名专家。本书系统地介绍了抗量子计算密码的基本原理、代表性成果和发展趋势。全书共分6篇，第1篇为抗量子计算密码导论。首先介绍量子计算机对现有密码的威胁，然后简单介绍现有抗量子计算密码的概貌，使读者对此领域有一个整体的了解。第2篇为量子计算。讲述了量子算法的工作原理及其最新进展，使读者能够对量子算法及其攻击密码的能力有一个了解。第3篇为基于Hash函数的数字签名方案。基于Hash函数的数字签名方案为抗量子计算密码提供了一种有趣的候选。本篇介绍了基于Hash函数的数字签名技术的发展，给出了几种代表性的方案。第4篇为基于纠错码的密码。纠错码是一种有效的容错技术，基于纠错码可以构造密码，而且具有抗量子计算攻击的能力。本篇介绍了基于纠错码的主要密码类型，并分析指出了它们的优缺点。第5篇为格密码。首先介绍了格的困难问题，然后介绍了几种有代表性的格密码。当前，格密码已成为学术界的研究热点。第6篇为多变量公钥密码学。多变量公钥密码被认为是能抵抗量子计算机攻击的公钥密码体制之一。本篇介绍了多变量公钥密码过去二十多年的发展和主要成果，并具体分析了每一种方案的优缺点。

本书内容丰富，较完整地给出了这一领域的全貌，不仅介绍现有成果，而且给出了今后的发展趋势。因此本书是一本很有参考价值的好书。本书可作为研究生和高年级本科生的教材或参考书，也可供从事信息安全、计算机、通信、数学、量子信息科学等领域的科技人员作为参考书。

本书的第1篇和第4篇由张焕国翻译，第2篇由杨昌翻译，第3篇由吴万青翻译，第5篇由毛少武翻译，第6篇由王后珍翻译。

本书的翻译采取了分工翻译，集体讨论修订的方法。博士研究生胡国香、王亚辉、刘金会、贾建卫等参与了翻译书稿的讨论修订和译稿整理工作。

由于译者的专业知识和外语水平有限，书中错误在所难免，敬请读者指正，译者在此先致感谢之意。

译者于武汉大学珞珈山第一届抗量子计算密码研讨会于2006年在Leuven的Katholieke大学举行。来自全世界的科学家们畅谈了量子计算和可以抵抗量子计算机攻击的密码方面的发展状况。大会报告人和与会听众一致认为，抗量子计算密码是一个有巨大吸引力的研究方向，如果大规模量子计算机被制造出来，那么对于今后的Internet来说抗量子计算密码将是决定性的关键技术。于是，我们决定编写一本关于抗量子计算密码的书。Springer出版社立即同意出版此书。我联系了几位在这一领域的顶级科学家，他们都愉快地接受了我的邀请。现在，我们很高兴地把这本书奉献给读者。我们希望本书能够成为介绍抗量子计算密码、纵览这一领域发展水平、鼓励更多科学家加入这一研究的一本图书。

我们要感谢编写本书的其他几位作者，与他们的合作是愉快的。我们还要感谢Springer出版社，特别是要感谢Ruth Alewelt和Martin Peters对我们的支持。首席编著者还要感谢Tanja Lange给予的关于抗量子计算密码的启蒙性的讨论，感谢学术界首先开始举办抗量子计算密码的系列研讨会。

Daniel J. Bernstein

Johannes A. Buchmann

Erik Dahmen

于芝加哥和达姆施塔特

2008年12月Daniel J. Bernstein Oded Regev

University of Illinois at Chicago TelAviv University

djb@cr.yp.to

Johannes Buchmann Nicolas Sendrier

Technische Universitt Darmstadt INRIA Rocquencourt

buchmann@cdc.informatik.tudarmastadt.de  nicolas.sendrier@inria.fr

Erik Dahmen Michael Szydlo

Technische Universitt Darmstadt Akamal Technologies

dahmen@cdc.informatik.tudarmastadt.de mike@szydle.com

Jintal Ding Ulrich Vollmer

University of Cincinnati  Berlin, Germany

ding@math.uc.edu ac@u.vellmer.name

Sean Hallgren Daniele Micciancio

The Pennsylvanis State University University of California, San Diego

daniele@cs.ucsd.edu

Raphael Overbeck    BoYin Yang

EPFL,I&C,LASEC   “Academia Sinica”