量子算法与后量子密码学

量子计算也许早就不是什么热门话题了，那我也来炒个冷饭，科普下针对密码学的量子算法，以及抗量子攻击的后量子密码学。

首先，简单介绍下什么是量子计算，量子计算是一种基于量子力学原理的计算方式，利用量子比特（qubit）进行计算，与传统计算机不同，量子计算机利用量子力学中的量子叠加、纠缠等现象，理论上在处理某些特定问题时展现出极大的计算速度优势。

量子门及门矩阵，图片来自知乎，作者见水印

为什么要限制在特定问题呢，我的理解是量子计算机和量子算法现在都还没完善到可以解决所有计算问题的程度，量子算法只在某些特定设计的问题上，借助量子叠加和纠缠的特性，得到了很好的计算结果（指速度上），不过量子计算机的设计不在今天的讨论之列，作为密码学科普文章，今天我们主要介绍针对密码学问题的量子算法，以及如何抗量子攻击。

各种量子计算机设计

在引入量子算法之前，先简单介绍一下它今天攻击的目标，大名鼎鼎的RSA，RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的，RSA就是他们三人姓氏开头字母拼在一起组成。这个密码算法有多重要呢？因为这个贡献，三人被授予了图灵奖。RSA算法自提出以来一直是最广泛使用的公钥加密系统之一，它基于大整数分解问题，即破解它的难度，与将一个大整数分解为两个素数的难度相同。

这个过程很难吗，不就是分成两个素数吗，小学都学过素数了，2，3，5，口算算算不就行了（

还真不是，这是一个主观上很具有误导性的问题，素数分解没有高效的公式，只能穷举，数字小的时候特别容易，但是当数字特别大时，只能靠计算机的计算速度了，这也是RSA安全性的底气。

那是不是量子计算机计算速度超快，可以快速穷举所有的素数？

是，也不是，这就是著名量子算法Shor算法的精妙之处，Shor算法是由彼得·肖尔（Peter Shor）于1994年提出的，它是一种基于量子计算的整数分解算法。与传统的算法如大整数因子分解相比，Shor算法在量子计算机上具有指数级别的加速优势。

Shor算法的基本思想是利用量子计算的并行性和量子叠加原理，对大整数进行因子分解。算法的主要思想如下是，首先生成一个随机数r，并与待分解的大整数n相除，得到一个小整数q。然后对q进行量子随机漫步，即不断地对q进行量子旋转门操作，直到找到一个因子。最后，用找到的因子去整除n，重复步骤（1）和（2），直到n分解完成。

Shor算法量子实现线路图

可能确实，看不懂什么原理，只要知道这个算法在量子计算机上跑的飞快就行了，如果量子计算机被发明出来了，那么所有依赖于RSA的加密系统就全部崩溃了。而且，通过对shor算法原理的剖析，我们可以知道，对于任何具备转化为求周期函数的周期为目标的问题都可以用同样算法以指数加速来快速解决，比如离散对数(ElGamal), ECC之类的非对称加密算法都可以用同样的思想来解决。所以说，量子算法对密码学的打击是毁灭性的。

当然，我们这种密码工作者肯定不会坐以待毙，所以一个新的方向--后量子密码学诞生了，所谓“后”，是因为量子计算机的出现，现有的绝大多数公钥密码算法（RSA、Diffie-Hellman、椭圆曲线等）能被足够大和稳定的量子计算机攻破，所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来，所以被称为“后”量子密码。也有人称之为“抗量子密码”，说的都是一个意思。英文中的表述是："Post-quantum Cryptography (PQC)"，或者 "Quantum-resistant cryptography"。

实现后量子密码算法主要有4 种途径，基于哈希函数，基于编码，基于多变量和基于格，其中，基于格的密码算法最受关注，因为其计算速度快、通信开销较小，且能被用于构造各类密码学算法和应用，因此被认为是最有希望的后量子密码技术。

格的定义，其实可以看做作为基的向量生成的线性空间

下面我们稍微介绍一下基于格的密码算法的原理，格(lattice)是一种数学结构，定义为一组线性无关的非0向量（称作格基）的整系数线性组合。下图表示了一个二维格和两组不同的格基：

二维格可以理解为平面点阵

一个格的格基可以不是唯一的，例如， ((2,1),(1,1)) 和 ((1,0),(0,1)) 都是二维整数格的一组格基。从上图中可以看到，即使是定义了同样的格的两组格基，其长度也可能相差很大。数学家和密码学家们普遍认为，对于一个维数足够高的格，通过一组随机选取的格基找到一组短格基，或得到一组线性无关的短格向量是困难的。这个问题称作最短独立向量问题(SIVP)。

而公钥密码学的安全源于数学上的困难问题，所以利用格上的困难问题可以很轻松的构建密码算法。不过需要注意的是，这些算法的安全性，仍然依赖于有没有可以快速求解其底层数学问题或直接对算法本身的高效攻击算法。换句话说，这些算法被称为抗量子算法，是因为目前没有量子算法可以攻击他们，而不是它们真正拥有抵抗所有（包括未来）量子算法的能力。这很有趣，所谓共同进化就是这么一回事，武器越先进，防御手段就越有利，但也反过来促进了攻击手段的发展。