量子算法与量子密码导论 课件 第5章 量子搜索算法及其应用

量子算法与量子密码导论量子搜索算法及其应用

一搜索算法原理及框架二搜索算法分析及示例三Grover算法与可满足性问题四Grover算法求解代数方程组Grover算法与密钥搜索本章内容

5.1搜索算法原理及框架1背景搜索问题是一个基础性问题，在计算机科学、密码学等许多领域中，很多问题的求解均可规约为搜索问题，如路径搜索、密钥搜索、碰撞搜索等。理论上来说，一般的NP问题均可用搜索的思路进行求解。对于特定问题来说，搜索不一定是最有效的方法。很多问题自身存在特殊结构，如果能够充分利用问题特征，则可能得到更高效的求解方法。对于无结构的搜索问题，如无序数据库搜索，暴力穷举可能是最优的方法。5.1搜索算法原理及框架1量子Oracle与搜索问题给定一个输出为0或1的函数可以将函数值存入一个辅助寄存器，构造一个量子Oracle，即5.1搜索算法原理及框架1量子Oracle与搜索问题根据量子Oracle，可以给出搜索问题的形式化描述。搜索问题：给定计算未知函数的量子Oracle，找到满足条件

的输入。5.1搜索算法原理及框架2Grover搜索算法框架如果满足要求的目标文件地址为z，则可以定义函数其中可以给出量子Oracle为5.1搜索算法原理及框架2Grover搜索算法框架将量子Oracle作用于量子态则只考虑地址寄存器，量子Oracle的作用可视为5.1搜索算法原理及框架2Grover搜索算法框架与一般的量子算法类似，制备初始等概率叠加态对应Grover算法框架如图5.1搜索算法原理及框架2Grover搜索算法框架在Grover算法中，核心的部分是Grover迭代过程，其线路实现如图5.2所示。5.1搜索算法原理及框架3搜索算法的图形描述量子Oracle的作用是在目标文件地址上翻转相位，实现标记目标文件地址的功能。5.2搜索算法分析及示例1搜索算法的复杂度算法初始态为第一次迭代后，逆时针旋转角，对应量子态变为进行k次迭代后，量子态变为5.2搜索算法分析及示例1搜索算法的复杂度

这是迭代的终极目标5.2搜索算法分析及示例2搜索算法示例根据Grover算法流程，可以给出针对4个数据的Grover算法线路图以k=3时的量子Oracle为例，目标数据编码为11，则量子Oracle可以直接用一个Toffoli门实现。5.3Grover算法与可满足性问题1概述在计算机科学、密码学等许多领域中，布尔可满足性问题的求解具有重要的理论和现实意义。此类问题的核心是确定是否存在赋值满足给定的布尔公式。换句话说，对于给定布尔公式的变量，确定是否存在一种赋值方式，使得公式计算结果为True。如果存在，则该公式称为可满足的；如果不存在，也就是公式对于所有可能的赋值的计算结果都是False，则该公式称为不可满足的。这可以看作一个搜索问题，目标是在布尔公式的各种赋值中寻找赋值计算结果为True的方案。5.3Grover算法与可满足性问题1概述Grover算法可用于加速任何NP完全问题的求解，但是如果对应的NP完全问题包含内部结构，则直接利用Grover算法可能无法实现有效加速。虽然在3-SAT问题上直接利用Grover算法穷举没有意义，但相关方法可以应用于更一般的情况（如k-SAT问题），对于某些特定问题，Grover算法可以胜过最优经典算法。此外，理论上Grover算法可以与经典算法进行深度融合，以获得比最优经典算法更好的加速效果。5.3Grover算法与可满足性问题2SAT问题Exactly-13-SATproblem：找到一个真值指派，使得每个Clause中恰好有一个literal赋值为1，且函数值为1。f(x1,x2,x3)=(x1∨x2∨¬x3)∧(¬x1∨¬x2∨¬x3)∧(¬x1∨x2∨x3)x1x2x3f0001第二Clause中3个literal为10010函数值为00101第一Clause中2个literal为10111第三Clause中3个literal为11000函数值为01011Y1101第一Clause中3个literal为11110函数值为05.3Grover算法与可满足性问题2SAT问题先构造子模块：考虑函数f的每个Clause取值为1，且恰好一个literal赋值为1；组合所有Clause。例：(x1∨¬x2∨x3)考虑y=x1

¬x2

x3

(x1

¬x2

x3)5.3Grover算法与可满足性问题2SAT问题(x1∨x2∨¬x3)

(¬x1∨¬x2∨¬x3)

(¬x1∨x2∨x3)y1=

x1

x2

¬x3

(x1

x2

¬x3)y2=

¬x1

¬x2

¬x3

(¬x1

¬x2

¬x3)y3=

¬x1

x2

x3

(¬x1

x2

x3)初始化子句1子句2子句35.3Grover算法与可满足性问题2SAT问题退计算q45.3Grover算法与可满足性问题2SAT问题5.3Grover算法与可满足性问题2SAT问题5.3Grover算法与可满足性问题2SAT问题5.4Grover算法求解代数方程组1代数方程组问题代数攻击在公钥密码、分组密码和序列密码分析领域，甚至在杂凑函数碰撞攻击领域都有成功应用，已经发展成为一种重要的通用密码分析方法。代数攻击通过分析密码算法的内部结构，构建多变元高次代数方程组，利用求解方程组开展密码分析。代数方程组的求解是一个困难问题，利用Grover算法可以暴力穷举求解代数方程组。当然，这种方法并非最优方法，这里只是以代数方程组为例，探索量子搜索算法如何直接应用于密码分析中的基础数学问题。5.4Grover算法求解代数方程组1代数方程组问题以二元域上的代数方程组为例，给定如下方程组这是一个四变元的方程组，如果采用穷举搜索算法求解，相当于在0000,…,1111这16个四比特的序列中找到同时满足4个方程的解。利用Grover算法搜索方程组的解，核心是构造一个能够标记方程组正确解的量子Oracle。5.4Grover算法求解代数方程组1代数方程组问题以第二个方程

为例，可以用量子线路实现，如图所示。5.4Grover算法求解代数方程组1代数方程组问题类似地，可以给出整个方程组的可逆线路5.4Grover算法求解代数方程组2搜索方程组解的量子线路5.4Grover算法求解代数方程组2搜索方程组解的量子线路单次迭代输出结果如图所示，从图中可以看出，对于单次迭代算法，执行1024

次后，得到正确解0110的次数约为480次，也就是说，成功概率约为0.469。5.5Grover算法与密钥搜索1AES算法AES（AdvancedEncryptionStandard，高级加密标准）是一种典型的对称密码算法。AES是一种面向字节的算法，以AES-128为例，其以128位的明文块和128位的密钥块作为输入，并生成相同大小的密文块。AES-128的状态（State）可以用一个4×4的矩阵描述，矩阵每个元素代表1字节（8位）。5.5Grover算法与密钥搜索1AES算法AES的每一轮加密可以分为SubBytes（字节代换）、ShiftRows（行移位）、MixColumns（列混合）及AddRoundKey（轮密钥加）4个步骤，其中，前3个步骤分别以字节、行和列为单位进行数据处理，可并行计算。5.5Grover算法与密钥搜索2Grover算法搜索AES密钥框架密钥搜索的目标是通过给定的明密文对，寻找用于加密的密钥。从Grover算法框架来看，相位翻转等模块是基本固定的。因此，利用Grover算法搜索AES密钥，核心是给出能够标记正确密钥的量子Oracle，本质上需要设计AES加密（解密）算法的量子线路。先考虑简化情况，对于AES-128，其量子Oracle实现框架如图所示。5.5Grover算法与密钥搜索2Grover算法搜索AES密钥框架从量子Oracle的功能结构可以看出，为实现标记正确密钥的功能，关键是要给出AES加密过程的可逆实现，也就是在量子线路模型下，实现AES的加密过程。这样能够对叠加态的密钥进行并行处理，从而加速密钥搜索过程。结合AES算法的流程可以看出，最为关键的是给出SubBytes、ShiftRows、MixColumns及AddRoundKey这4个步骤在量子线路上的可逆实现。5.5Grover算法与密钥搜索3AES算法的可逆实现利用Grover算法搜索AES密钥，核心是AES的可逆实现，主要资源消耗是SubBytes操作，本质问题是有效的求有限域上元素的逆元。

需要构造有限域上元素模平方运