抗量子计算对称密码研究进展概述*

梁 敏, 罗宜元, 刘凤梅

1. 数据通信科学技术研究所, 北京 100191

2. 惠州学院计算机科学与工程学院, 惠州 516007

3. 河南省网络密码技术重点实验室, 郑州 450001

4. 电子科技大学网络与数据安全四川省重点实验室, 成都 610054

1 引言

1996 年Grover 提出著名的量子搜索算法(以下简称Grover 算法), 可实现对经典搜索效率的二次加速[1], 从而提高密码破译效率, 对密码安全性构成潜在威胁. 对于理想的对称密钥密码方案, 其安全强度将从O(2n) 次经典计算降低至O(2n/2) 次量子计算; 对于理想的杂凑函数, 其安全强度将从O(2n/2) 次经典计算降低至O(2n/3) 次量子计算. 因此, 无论对称密码算法设计多么完美, 其安全强度都将受到量子攻击的显著影响. 此外, 对于现实中的密码算法, 在量子计算攻击下其设计弱点或潜在弱点都可能被放大,从而面临比Grover 穷举搜索攻击更高效的量子攻击. 因此, 不能单纯依靠增大安全参数n来提高密码算法的抗量子计算攻击能力, 而是应该将量子计算融入密码学研究, 全方位考虑量子计算攻击在密码算法设计与分析中的影响.

目前, 基于量子计算的密码分析研究大致包括三个层次的内容: 一是量子安全模型研究, 目标是确立量子安全标准体系, 并为量子攻击和量子安全性证明提供根本依据; 二是在量子安全模型下针对结构和工作模式的分析和安全性证明, 目标是判断密码结构和模式在量子模型下是否符合量子安全标准; 三是在量子安全模型下针对密码算法的安全强度评估, 目标是全面而具体地评估密码算法的抗量子计算攻击强度.

在量子安全模型研究方面, 针对伪随机函数、加密、认证、认证加密、杂凑等密码学原语, 分别定义了量子安全模型. 对于带密钥密码原语建立的量子安全模型可分为两大类: Q1 模型和Q2 模型, 其中Q2 模型允许攻击者对原语执行量子查询而Q1 模型只允许经典查询. 这些量子安全模型具备不同的强弱程度,可作为衡量密码原语的不同安全程度的基准.

在量子安全模型下, 许多经典可证明安全的结构和工作模式受到量子计算攻击, 特别是许多结构和工作模式在Q2 模型下完全不安全, 它们在量子叠加态查询攻击下受到基于Simon 量子算法的量子多项式时间攻击[2]. 不过也有一些结构和工作模式在量子安全模型下是可证明安全的[3–6]. 还有一些结构或工作模式虽然不安全但是经过改造后可达到量子可证明安全性[7].

在量子安全模型下针对密码算法的安全强度评估, 主要包括两类研究: 一是通用量子攻击下的安全强度评估[8–13], 包括基于Grover 算法的量子穷举攻击和量子碰撞攻击下的复杂度评估; 二是专用量子攻击下的安全强度评估[14], 根据具体密码算法的特征来设计专用的量子攻击, 并评估其攻击复杂度. 其中, 前者研究较多, 形成了成熟的评估体系; 后者更强调专用性, 与具体密码算法是强相关的, 目前研究结果相对较少.

对称密码的抗量子分析研究仅有十多年的历史, 并且直到近五年才成为热点. 当前这些研究还很不充分, 尚不足以全面评估对称密码的量子安全性, 未来还需要继续加强量子攻击技术和量子可证明安全研究,为抗量子对称密码设计和量子安全强度量化评估奠定基础.

本文将分别从量子算法、量子安全模型、量子安全强度量化评估、对结构和工作模式的量子攻击、结构和工作模式的量子可证明安全性、抗量子对称密码设计等六个角度来概述抗量子对称密码研究进展. 在撰写过程中部分参考了眭晗和吴文玲[15]的综述论文.

本文第2–7 节分别从以上六个角度来介绍研究进展, 清晰呈现各项内容之间的逻辑联系, 实际上这六个方面的内容并非完全独立的. 第2 节介绍量子算法, 它是抗量子对称密码分析的基础工具; 第3 节介绍量子安全模型, 它为“抗量子攻击” 设定了基准, 是进行抗量子分析(攻击/证明) 的根本依据或框架; 第4 节介绍对称密码算法的量子安全强度评估, 它依托各种量子攻击技术, 全面而直接地评估对称密码算法的量子安全强度; 第5 节介绍对结构和工作模式的量子攻击, 从攻击角度阐述上层结构或模式的抗量子攻击能力; 第6 节介绍结构和工作模式的量子可证明安全性, 从证明角度阐述上层结构或模式是否达到量子安全模型所定义的安全标准; 第7 节介绍抗量子对称密码设计的进展情况.

2 量子算法

量子算法是开展抗量子密码分析研究的基本工具. 目前在密码分析中最广泛使用的量子算法是Grover 量子搜索算法及其推广. 近年来Simon 量子算法被用于密码结构和工作模式的分析, 攻击效率可实现指数级提升. 此外, 在某些特定情况下, 将这些量子算法组合使用, 扩大了攻击技术适用范围或提升了攻击效率, 例如Grover 算法与Simon 算法组合, Grover 与几率幅放大算法组合, Simon 算法的自我组合等. 下面具体介绍这些算法.

2.1 Grover 算法及其推广

Grover 算法可加速无序数据集的搜索效率, 而几率幅放大算法[16]是Grover 算法的一般性推广. 这里先介绍几率幅放大算法, 然后以特例形式给出Grover 算法.

总之, 几率幅放大算法的核心是两个量子酉变换A,Q, 其中A是一个制备初态|φinitial〉的量子变换,是必要的已知变换; 而Q的作用就是将初态中的解分量|good〉的几率幅进行放大, 它实际上可由量子变换A和对f的量子查询来实现.

Grover 算法. 在上述几率幅放大算法中, 令A为作用于k个量子比特上的Hadamard 变换, 即可获得Grover 算法.

碰撞查找问题: 给定一个函数H:{0,1}m →{0,1}n, 寻找2 个不同的输入值x1/=x2, 使得H(x1) =H(x2). 经典生日碰撞算法中对随机函数H的查询复杂度为O(2n/2). 量子碰撞查找算法可以更快地解决碰撞查找问题. 下面具体介绍相关研究结果.

2.2 Simon 量子算法

下面简单介绍Simon 算法的另一种用法: 并行地执行Simon 算法, 用来判断函数f是否为周期函数,而不必具体计算出f的周期值. 若并行地运行cn个Simon 子程序, 则输出一个量子态

然后采用量子计算对该量子态的每个叠加分量实现如下计算

其中Span(·) 和dim(·) 分别返回cn个输入值所张成的空间及空间维数. 若f不是周期函数, 则函数t将以大概率等于0; 若f为周期函数, 则函数t的计算值几乎等于1.

2.3 组合量子算法

近几年来, 许多研究工作都将上述量子算法进行组合使用, 在密码分析中实现更高效的量子攻击. 这里主要介绍Grover 算法和Simon 算法之间的各种嵌套用法, 它们已经被广泛用于密码分析. 此外还有其它的组合量子算法, 例如Simon meets Kuperberg 和Grover meets Kuperberg 等[26].

几率幅放大算法是Grover 算法的推广, Albrecht 等[27]将Grover 算法与几率幅放大算法组合使用,提出了过滤量子搜索算法(filtered quantum search), 其中外层使用几率幅放大算法来搜索问题f的解,内层嵌套使用Grover 算法来实现过滤器g. 该算法采用过滤器降低搜索问题解的开销. 他们将这种方法用于改进格筛法中3 种NNS (near neighbour search) 算法.

Simon 算法可自我嵌套使用, 即Simon 算法内部再嵌套一个Simon 子程序. 这种算法适用于函数f的周期本身也是关于另一个变量的周期函数的情况,即满足f(x,y)=f(x⊕g(y),y),其中g(y)=g(y⊕s).

上述都是同类算法的嵌套组合使用. 下面介绍功能不同的两种量子算法之间的组合使用, 即Grover算法与Simon 算法的组合, 目前有以下两种组合形式, 它们均采用了两层组合结构.

第一种由Leander 和May[28]提出, 适用于加密函数F(k,x) 的密钥恢复, 其中F(k,x) 满足以下两个条件: (1) 当k等于真实密钥k0时, 存在s使得F(k0,x) =F(k0,x ⊕s),∀x ∈{0,1}n; (2) 当k/=k0时,F(k,x) 以大概率不具有周期性. 将Grover 算法与Simon 算法组合使用时, 外层用Grover 算法搜索密钥k, 内层用并行的Simon 子程序作为Grover 迭代中的分类器: 根据密钥k能否使F(k,x) 满足周期性, 判断密钥k是否为真实密钥k0. 这里并不需要Simon 子程序计算出周期值, 而只用于Grover 迭代中标记待搜索的k值: 当且仅当k值使得F(k,x) 是关于x的周期函数, 则将待搜索量子叠加分量中的|k〉执行相位翻转变换成为-|k〉. 而为了判断F(k,x) 是否为关于x的周期函数, 只需要并行执行cn个Simon 子程序并检查输出能否张成一个n-1 维空间.

第二种由Bonnetain 等[29]提出, 其适用条件与前者类似, 但是在满足以下额外条件的情况下改进了量子查询复杂度: 函数F(k,x) 可分解成形式F(k,x)=f(k,x)⊕gk0(x), 这里f和g的值分别通过离线计算和在线查询来实现. 对于这种F(k,x), 若仍然采用Leander 和May[28]的组合量子算法, 则对g的量子查询次数为指数量级; 而Bonnetain 等[29]将其降为O(n), 其关键点在于该特定情况下可复用g的量子查询结果, 即, 先通过cn次对g的量子查询产生g的量子数据库|φg〉=⊗cn(∑x|x〉|gk0(x)〉), 然后基于|φg〉采用并行Simon 子程序检测函数F(k,x)的周期性, 并且|φg〉被使用一轮之后还可复原用于下一轮Grover 迭代. 正是这点改进, 使得某些结构或工作模式在Q2 模型下的攻击被转换成Q1 模型下的攻击[29], 因为这个量子数据库|φg〉是可以通过“经典查询+ 量子计算” 来产生: 以经典方式查询函数g在每个x处的取值{(x,gk0(x)),∀x}并根据查询值来执行CNOT 量子运算. 显然这里需要指数量级的经典查询次数, 但是在一定条件下可以调节或控制经典查询次数, 以获得在经典查询复杂度方面的攻击优势.

3 量子安全模型

安全模型是开展安全性证明和攻击的根本依据和思考框架, 也是衡量密码算法安全程度或等级的标准. 安全模型的强弱需适度: 太强而不可能达到, 就失去了意义; 太弱而容易达到, 却不能保证密码在现实使用中的安全性, 这也是没有意义的.

对于带密钥的密码学原语, 例如加密、认证、认证加密等, 量子安全模型可根据查询类型来分为两大类: Q1 模型和Q2 模型, 前者允许量子攻击者执行经典查询, 而后者允许量子攻击者执行量子查询. 两类模型相比, Q1 模型相对现实一些; Q2 模型比Q1 模型强很多, 但在量子计算时代Q2 模型攻击场景是可能存在的, 因此Q2 模型下的密码证明和攻击技术仍然具有研究价值和技术储备意义.

对于无密钥的密码学原语(例如杂凑), 量子攻击者可通过本地量子计算(不必通过查询) 来获得量子叠加态计算结果, 因而没有Q1 和Q2 模型之分. 对于带密钥的杂凑密码, 可参照认证原语来开展研究, 因此这里所提杂凑是指无密钥的.

后面将分别介绍加密、认证、认证加密、杂凑的量子安全模型及其研究现状.

3.1 加密的安全模型

类似于经典模型(记为Q0 模型) 下所定义的IND、IND-CPA 和IND-CCA, 研究人员定义了量子版本的攻击类型(量子选择明文攻击qCPA 和量子选择密文攻击qCCA), 以及量子版本的安全目标(量子不可区分性qIND 和量子语义安全性qSEM), 然后提出了一些量子版本的安全模型, 分别具备不同级别的量子安全程度. 这些量子安全模型主要包括IND-qCPA、IND-qCCA、qIND 和qIND-qCPA 等加密安全模型. 具体定义可参考相关文献[30—33] 中的研究. 图1 给出了它们之间的强弱关系总结, Q0 代表经典模型, Q1 和Q2 代表两种不同的量子模型. 在Q0 模型中, 敌手可执行经典计算和经典查询; 在Q1 模型中, 敌手可执行量子计算和经典查询; 在Q2 模型中, 敌手可执行量子计算和量子查询. 箭头表示两者之间的单向推导关系(若密码满足一个安全模型, 则必定满足另一安全模型), 带短斜线的箭头表示不存在该推导关系, 带“?” 的箭头表示暂时没有定论.

图1 加密量子安全模型之间的关系图Figure 1 Relationships between quantum security models for encryption

Chevalier 等[34]定义了qIND-qCCA2, 该成果曾在QCrypt2020 会议上作口头报告, 但是目前还没有正式发表, 所以未体现在图1 中. 对于量子版的IND, Boneh 和Zhandry[30]曾定义了全量子不可区分性fqIND, 并证明fqIND 因太强而不可能达到, 因此也未在图中体现. 对于Q1 模型下的IND 定义(即pqIND), 除了允许攻击者使用量子计算机以外, 它与经典安全模型下的IND 定义相同. Q2 模型下可定义三种不可区分性: IND、wqIND 和qIND, 其中qIND 最强, wqIND 稍弱, 但是目前还不明确wqIND 是否严格弱于qIND, 因此图中箭头上添加了“？”.

图中涉及4 种程度的不可区分性. 若对称密钥加密方案Π = (Gen,Enc,Dec) 满足其中某种不可区分性IND/fqIND/wqIND/qIND, 则对于所有的多项式时间攻击算法或敌手A, 存在一个可忽略函数negl使得

其中概率来源于A的内部随机性以及实验PrivK 中的随机性(选择密钥、随机比特b, 以及在加密过程中使用到的任何随机性). 这里的实验PrivKI(n) 分别用算法1–4 实验来描述, 其中IND 实验中的A具备概率多项式时间计算能力, 而其它3 种实验中的A都具备量子多项式时间计算能力. 符号φb表示量子态, Dsc(.) 表示以量子态作为输入来产生该量子态的经典描述, Qbuild(.) 表示以经典描述作为输入来制备量子态.

算法1 经典不可区分实验PrivKINDA,Π(n)Input: 参数n Output: 区分成功, 输出1; 否则输出0 1 k ←Gen(1n);2 m0,m1 ←A(1n);3 b←${0,1};45 c b′ ←←EAn(cck)(;b,m0,m1);6 if b′ = b then 7output 1;8 else 9output 0;10 end

算法2 全量子不可区分实验PrivKfqIND A,Π (n)1 k ←Gen(1n);2 φ0,φ1 ←A(1n);3 b←${0,1};4 5 φ b′←←|AE(nφck);〉(b,φ0,φ1);6 if b′ = b then 7output 1;8 else 9output 0;10 end Input: 参数n Output: 区分成功, 输出1; 否则输出0

算法3 弱量子不可区分实验PrivKwqIND A,Π (n)算法4 量子不可区分实验PrivKqIND A,Π (n)Input: 参数n Output: 区分成功, 输出1; 否则输出0 1 k ←Gen(1n);1 k ←Gen(1n);2 Dsc(φ0),Dsc(φ1) ←A(1n);2 φ0,φ1 ←A(1n);3 b←${0,1};3 b←${0,1};4 φb ←Qbuild(Dsc(φb));4 φ ←|Enck〉(b,φ0,φ1);56 φ b′ ←←|AE(nφck);〉(φb);5 6 tbr′ a←c e A ou(tφ φ);1-b;7 if b′ = b then7 if b′ = b then 8output 1;8output 1;9 else9 else 10output 0;10output 0;11 end11 end Input: 参数n Output: 区分成功, 输出1; 否则输出0

图1 中CCA1 与CCA2 (或qCCA1 与qCCA2) 的差别在于: 前者的选择密文查询发生在挑战查询之前,而后者的选择密文查询不受此限制.

3.2 认证的安全模型

在经典模型下的认证安全模型有: 选择消息攻击下的弱不可伪造性(WUF-CMA) 和选择消息攻击下的存在不可伪造性(EUF-CMA), 其中前者比后者弱一些. 在WUF-CMA 的定义中, 安全目标通常设定为:q次查询后不能在多项式时间内产生一个新消息msg 的标记tag, 但不排除产生“旧消息” (被查询过的消息) 的新标记的可能. 更强的安全模型EUF-CMA 的安全目标为:q次查询后不能有效产生一对新的“消息-标记(msg, tag)”. 在Q1 模型下, 关于认证安全模型没有明确的公开研究结论, 从当前的研究情况来看, Q1 模型下有类似于Q0 模型的等价关系, 而且两类模型之间的差距至多是多项式量级.

在Q2 模型下, 由于允许执行量子叠加态查询, 攻击者可并行地查询所有消息的认证标记, 因此在定义未被查询过的“新消息msg” 或者“新消息标记对(msg, tag)” 时遇到困难. 研究人员先后提出了两种方式来定义认证安全模型. 第一种是Boneh 和Zhandry[7]定义的PO (plus one) 方式. 对应的安全模型称为PO 安全性, 其中要求攻击者经过q次查询后不能有效产生q+1 个消息标记对(msg, tag), 且这q+1 对中的msg 不重复出现. 其加强版sPO 的定义中只要求这q+1 个消息标记对中不出现重复的(msg, tag), 但允许重复出现同一个消息msg. 第二种是Alagic 等[35]定义的的BU (blind unforgeable)方式. 对应的安全模型称为BU 安全性, 该模型要求在消息空间中随机分割出一块大小可忽略的盲区, 只允许攻击者查询该盲区以外的消息但要求攻击者去伪造该盲区元素的合法标记tag. 其加强版sBU 的定义中要求在消息标记对(msg, tag) 的空间中随机设置盲区, 不允许攻击者查询但要求伪造产生该盲区的元素(msg, tag).

通常广泛使用的EUF-qCMA 是指Boneh 和Zhandry[7]所定义的PO 方式, 即图2 中的EUFqCMA(PO), 后文直接写作EUF-qCMA. 而采用BU 方式定义的EUF-qCMA(BU) 值得继续开展研究.事实上, Q0 模型下的认证安全模型也可按PO 或BU 方式来定义, 但是WUF-CMA 等价于采取PO 和BU 方式的定义, 而EUF-CMA 也等价于采取sPO 和sBU 方式的定义. 图2 中总结了这些安全模型之间的强弱或等价关系, 前两行都是Q0 模型下的经典安全模型, 最后一行是Q2 模型下的量子安全模型. Q1模型位于Q0 模型和Q2 模型之间, 且与Q0 模型有类似的关系描述, 故图中未体现.

图2 认证安全模型之间的关系图Figure 2 Relationships between security models for authentication

3.3 认证加密的安全模型

认证加密方案可以同时提供私密性和完整性保护功能. 在研究其量子安全模型时, 应该兼顾私密性和完整性的量子安全定义. 私密性的定义可沿用加密安全模型(如IND-qCPA), 然而完整性的定义不能直接采用认证安全模型(如EUF-qCMA).

经典安全模型下的完整性定义有明文完整性INT-PTXT 和密文完整性INT-CTXT 两种. Q1 模型下也可类似地定义. 然而Q2 模型允许量子叠加态查询, 攻击者可并行地查询每个消息的密文, 因此在定义安全目标时应该特别注意. Soukharev 等[36]在Q2 模型下定义了认证加密的量子安全模型: INTqCTXT (量子攻击下的密文完整性) 和INT-qPTXT (量子攻击下的明文完整性). 但是, 他们在定义INT-qCTXT 时直接将IND-qCCA 的敌手能力和EUF-qCMA 的安全目标进行简单组合(若按通行记法应该记为EUF-qCCA), 显然不适合作为密文完整性的定义.

3.4 杂凑的安全模型

对于杂凑密码, 传统研究中采用的安全模型主要有抗碰撞性(collision resistance)、抗原像性(preimage resistance)、抗第二原像性(second-preimage resistance) 和不可区别性(indifferentiability), 分别记为Coll、Pre、Sec、Indiff.

由于hash 函数是无密钥的密码原语, 量子攻击者不必通过在线量子查询, 只需执行离线本地量子计算, 就可获得量子叠加态的杂凑值计算结果. 因此, 对hash 函数的在线量子查询并不会为量子攻击者带来攻击能力上的根本提升, 其量子安全模型也不再细分为Q1 和Q2 两类模型.

Hash 函数的量子安全性定义有两类, 一类是直接由经典安全模型的推广[37], 即在量子计算模型下定义的抗碰撞性CollQ、抗原像性PreQ、抗第二原像性SecQ、不可区别性IndiffQ. 另一类是量子计算情况下独有的, 目前包括Collapsing hash 和Bernoulli-preserving hash.

Collapsing hash 是由Unruh[38]在2016 年提出来的, 他发现在量子背景下, 特别是在研究抗量子密码协议时[39], 满足CollQ 的hash 函数不足以提供强的安全属性, 所以提出用Collapsing 替代CollQ. 一个hash 函数H是Collapsing, 若满足如下条件: 如果某个量子多项式时间算法产生了一个y值和一个量子寄存器X, 其中X处于由{|x〉|H(x)=y}中的基态组成的量子叠加态; 给定这个量子寄存器X(它可能已被测量或未被测量), 任何量子多项式时间算法均无法有效地区分X是否被测量过, 即其区分概率是可忽略的.

Bernoulli-preserving hash 是Alagic 等[35]在2020 年提出来的. 他们发现抗碰撞的hash 不足以证明MAC 构造方式“Hash-and-MAC” 满足Blind-Unforgeability, 从而提出更强的hash 量子安全定义——Bernoulli-preserving hash. 有效可计算的函数族H:X →Y是Bernoulli-preserving hash,若满足如下条件: 将Y中元素按Bernoulli 过程采样获得集合Y′, 则Y′关于函数h ←H的原像集{x ∈X|h(x)∈Y′}(以可忽略的差异) 等同于一个从X中Bernoulli 采样所得集合. Bernoulli-preserving hash 退化回到经典模型下就与经典的抗碰撞性等价了.

关于不同hash 安全属性之间关系的研究结果, 总结如下: (1) 一个函数H是随机预言机或者Q2 模型下的伪随机函数(即qPRF),则它也是Bernoulli-preserving hash;(2)一个函数是Bernoulli-preserving hash, 则它也是Collapsing hash; (3) 一个函数是Collapsing hash, 则它也是CollQ 的.

4 量子安全强度评估

本节将从两个角度来阐述量子安全强度评估的现状: 首先介绍一些经典分析技术的量子增强版, 然后总结叙述在这些量子分析技术下开展对称密码算法的量子攻击资源评估与优化研究的进展情况.

4.1 经典分析技术的量子增强

通过将密码算法的经典攻击方式进行量子化改造, 一些量子增强的密码分析技术相继被提出, 包括量子穷举攻击、量子碰撞攻击、量子中间相遇攻击、量子相关密钥攻击、量子滑动攻击、量子差分分析、量子线性分析、量子不可能差分攻击、量子平方攻击等. 与经典攻击方式相比, 它们的量子版本具有更好的攻击性能. 具体研究情况介绍如下.

量子穷举攻击和量子碰撞攻击分别是基于Grover 搜索算法对经典穷举攻击和碰撞攻击的量子增强.它们都是通用的量子攻击技术, 即使密码算法设计得非常理想, 仍然可以使用, 目前已被广泛用于评估密码算法的量子安全强度, 特别是对AES 和SHA 算法的量子安全强度量化评估[8,13]. 此外, 在NIST 抗量子公钥密码标准征集中, 所设定的五个安全级别正是分别对标AES128/192/256 和SHA256/384 的通用量子攻击复杂度[40].

量子中间相遇攻击是对经典中间相遇攻击的量子增强, 最早是Zhong 和Bao[41]在分析3DES 时提出的. Hosoyamada 和Sasaki[42]将该量子攻击技术进一步应用于攻击可调分组结构TDR、认证模式Chaskey、认证加密McOE-X、认证模式H2-MAC 和keyed-sponge、FX 结构等. 他们后来又提出量子版的Demiric-Selcuk 中间相遇(DS-MITM) 攻击[43], 用于分析6 轮Feistel 结构. 本质上, 这些量子中间相遇攻击都是用Grover 算法替换了经典中间相遇攻击中的搜索部分, 从而增强攻击性能; 差异在于, 这些工作需要根据具体密码的结构特点来提出有针对性的攻击方案设计.

Kaplan 等[44]提出了量子线性分析, Bonnetain 等[48]提出了量子平方攻击(或积分攻击), 这两种量子攻击技术分别是在经典线性分析和经典平方攻击的基础上, 将搜索部分用量子算法来完成, 从而实现攻击加速.

Chen 和Gao[49]基于HHL 量子算法(即线性方程组量子求解算法[50]) 提出了量子代数攻击方法,将AES、Trivium 和SHA3 等密码算法的量子安全强度与布尔方程组的条件数建立了直接关联, 从而将密码算法的安全分析转换成对条件数的分析.

上述量子攻击技术一般都可在Q1 模型下使用, 此时其攻击效率只能达到多项式量级的加速. 接下来介绍可实现指数级加速的量子攻击技术, 它们已经被用于Q2 模型下的攻击.

Kaplan 等[2]提出了在Q2 模型下使用的量子滑动攻击技术, 主要利用了Simon 量子算法来增强滑动攻击效率, 从而实现指数级加速(量子查询复杂度从O(2n/2) 降至O(n)). 这种攻击适用于迭代Even-Mansour 结构中所有轮密钥都相同的情形. Dong 等[51,52]针对2/4K-Feistel 提出了量子版的高级滑动攻击, 该技术适用于Feistel 结构的2 (或4) 个轮密钥以周期2 (或4) 交替地重复使用的情形(例如, 交替使用2 个轮密钥时, 迭代的每一轮所用密钥依次为k1,k2,k1,k2,k1,k2,···), 其攻击复杂度为量子多项式时间, 从而实现了指数级攻击加速. Bonnetain 等[53]以SPN 和Feistel 结构为分析对象, 深入研究了各种量子滑动攻击, 将“模加” 运算、自相似、圈等因素都考虑进来, 其攻击加速效果因结构的具体特点而差异巨大, 例如, Feistel 结构分别采用“⊕” 和“模加” 情况时, 在该量子攻击下的复杂度相差指数量级.

Rotteler 和Steinwandt[54]基于Simon 量子算法提出一种量子相关密钥攻击模型. 在此模型下, 攻击者不仅可对消息空间进行量子叠加态查询, 还可对密钥空间做叠加查询. 由于该模型赋予攻击者过于强大的能力, 任何分组加密方案都不可能抵抗此种量子相关密钥攻击. 因此, 这是一种不现实的量子攻击模型. Hosoyamada 和Aoki[55]提出另一种量子相关密钥攻击, 仅针对迭代Even-Mansour 结构可在多项式时间内恢复密钥. 事实上, 这种量子相关密钥攻击是对Kaplan 等所提出的量子滑动攻击[2]的一种推广, 从而适用于迭代Even-Mansour 结构中所有轮密钥都独立选择的情形.

总体来看, Q2 模型下的量子攻击技术通常以Simon 量子算法为核心, 从而实现非常高效的量子攻击;而Q1 模型下的量子攻击技术大多以Grover 搜索算法为核心, 攻击加速的效果有限, 但是相对Q2 模型来说是更具现实意义的. Bonnetain 等[29]提出了离线“Grover+Simon” 算法, 在特定的情况下可将Q2模型下量子攻击技术(包括Rotteler 和Steinwandt[54]的量子相关密钥攻击和量子滑动攻击) 转换到Q1模型下使用.

4.2 量子攻击资源评估与优化

在评估密码算法在量子攻击下的量子资源需求时, 首先需要选取一个或多个指标作为量化评估标准.量化评估指标的选取通常都要结合量子计算机物理实现进展水平. 量子线路模型是量子计算研究广泛采用的模型, 目前研究人员主要选取量子线路的各种复杂度指标, 如Toffoli 门与T 门的数量和深度、线路总深度、量子比特数等. 部分研究还将MAXDEPTH(最大线路深度)约束作为量化评估的一个限制因素,即在量子线路所允许的最大深度限制下量化评估量子攻击资源[10,13].

在量子穷举密钥攻击下, 加密算法安全强度的粗略估计是O(2n/2) 次量子计算, 与经典安全强度O(2n) 相比正好是平方加速, 其中n是密钥长度. 实际上这里O(2n/2) 是该攻击运行中执行Grover迭代的轮数, 由于每一轮Grover 迭代的主体部分都是以量子方式执行至少两次该密码算法, 通常也将O(2n/2) 视为量子查询复杂度. 为了量化评估加密算法的量子安全强度, 必须分析每一轮Grover 迭代(或密码算法) 的量子实现复杂度. 因此, 为了准确评估加密算法在量子穷举密钥攻击下的安全强度, 应尽可能准确地评估加密算法的量子实现复杂度. Grassl 等[8]最早开展了AES 的量子线路设计工作, 给出了AES-128/192/256 的量子线路实现中T 门数量和深度、Clifford 门数量、线路的深度和量子比特数, 在此基础上估计了量子穷举攻击所需量子资源: 对于AES-128, 需要2953 个量子比特, 1.19×286个T 门,1.55×286个Clifford 门, 线路深度为1.16×281(远大于粗略的估计值264). Kim 等[13]、Almazrooie等[56]、Jaques 等[57]和Zou 等[58]通过改进量子线路设计, 优化量子线路实现的各项复杂度指标, 尽可能逼近真实的量子攻击资源需求. 目前公开的最优设计是Zou 等给出的结果: AES-128/192/256 的量子线路实现分别需要512, 640 和768 个量子比特[58].

除了AES 以外, 研究人员还在量子穷举攻击下对其它(轻量级) 分组密码和序列密码开展了量子攻击资源量化评估和优化研究, 包括GIFT、SKINNY、SATURNIN[11]和基于ARX 的SPECK[12]和LowMC[57],还有基于反馈移位寄存器的序列密码Grain-128-AEAD、TinyJAMBU、LIZARD 和Grainv1 等[10].

对于杂凑算法, 为了评估其量子抗碰撞性, 一般使用量子碰撞攻击技术来量化评估其安全强度, 而为了评估其量子抗原像攻击性, 一般采用量子原像查找攻击(实际上就是对原像的量子穷举攻击). 无论从哪个角度来评估量子攻击资源, 都需要尽可能准确地评估杂凑算法的量子实现复杂度. Amy 等[9]在量子原像攻击下评估杂凑算法SHA2 和SHA3 的安全强度. 类似于对AES 的量子穷举攻击, 他们设计量子线路实现SHA-256 和SHA3-256, 然后评估了该攻击所需量子资源, 包括在采用表面码(surface code) 实现量子纠错的情况下的线路深度和量子比特数. Kim 等[13]从Toffoli 门深度和量子比特数角度改进了对SHA2 的量子原像攻击资源评估, 其中Toffoli 门深度可降至大约2141, 而量子比特数量可改进到802.

量子碰撞攻击技术的核心是量子碰撞查找算法. 早期的BHT 碰撞查找算法的查询复杂度为O(2n/3)(其中n为杂凑函数的输出长度), 优于经典碰撞攻击的复杂度O(2n/2); 但是该算法需要O(2n/3) 规模的量子随机可访问的经典存储(QRACM), 目前这个QRACM 需要用量子存储来完成. 在当前的量子计算机体系架构下, 用于存储数据的量子位就是量子计算机的核心, 相当于传统计算机的中央处理单元. 因此, 应该将这些量子存储纳入量化评估体系, 采用时间-存储折衷(time-memory tradeoff, TMT) 来评估算法复杂度. 在这种情况下, BHT 碰撞查找算法的TMT 值为O(22n/3), 与经典生日碰撞攻击的复杂度O(2n/2) 相比就失去了优势. Chailloux 等[59]重新发掘了量子碰撞查找算法的优势, 通过改进算法设计,新算法(简记为CNS 量子算法) 的时间复杂度为O(22n/5), 量子存储规模为O(n). 基于CNS 量子算法, Kim 等[13]对SHA2 在量子碰撞攻击下所需量子资源进行了量化评估, 给出的Toffoli 门深度估计为2117, 而量子比特数量为939.

除了量子穷举攻击和碰撞攻击这两类通用量子攻击以外, 采用其它攻击技术的量子攻击资源评估还存在很多研究空白. 研究人员在这方面也开展了一些工作, 针对具体密码方案的内部构造细节或特点, 设计专用的量子攻击算法, 开展量子安全强度评估. 具体介绍如下.

Bonnetain 和 Jaques[14]在 Q1 模型下采用离线 Simon 算法开展攻击研究, 给出了 Chasky、PRINCE、Elephant 等的量子攻击资源量化评估. 研究结果表明其攻击性能明显优于通用量子攻击.

这些研究进展表明, 专用的量子碰撞攻击能够显著改进碰撞查找效率, 已经成为了一种重要的量子攻击技术. 其潜力还可进一步发掘并应用于更多的密码方案.

5 对结构和工作模式的量子攻击

量子计算对对称密码安全性的重要影响之一是对结构和工作模式的威胁. 目前对结构和工作模式的量子攻击研究主要可分为两大类: (1) 在Q2 模型下的量子攻击, 这种情况下可以充分利用Simon 量子算法等黑盒算法取得指数级攻击加速; (2) 在Q1 模型下的量子攻击, 这方面的研究相对较少, 且不易取得显著的攻击加速效果. 由于这两类模型下的量子攻击技术和研究方法均存在较大差异, 下面将分别进行介绍.

5.1 Q2 模型下的攻击

在Q2 模型下攻击分组密码结构和工作模式的常用方法是先根据密码结构或模式的具体特点来设计具有周期性结构的数学函数, 然后用Simon 量子算法来查找该函数的周期(该周期值通常是某种关键信息, 例如密钥或者与密钥有关的值), 再根据攻击目标来设计后续的量子伪造攻击或量子区分攻击等. 理论上Q2 模型下还可使用其它黑盒量子算法作为区分器设计的基本工具.

Kuwakado 和Morii[64]在Q2 模型下研究了Even-Mansour 结构(即Ek1,k2(x)=P(x ⊕k1)⊕k2,其中P是一个公开置换,k1,k2为密钥) 的量子伪随机性, 基于Simon 量子算法构造了qCPA 下的高效区分器: 经过O(n) 次量子查询, 可有效地区分Even-Mansour 结构和真随机函数. Kaplan 等[2]推广了这种量子区分器构造方法, 将其应用到可调分组密码结构LRW : ˜Et,k(x) =Ek(x ⊕h(t))⊕h(t), 其中h是一个(almost) universal hash function. 他们构造了qCPA 下的高效区分器: 经过O(n) 次量子查询就可区分LRW 结构和理想的可调分组密码. 作为LRW 结构的实例化, XEX 或XE 也存在这种量子区分器.

关于Feistel 结构, 有qCPA 和qCCA 下的量子分析研究结果. Kuwakado 和Morii[65]构造了3 轮Feistel 结构的qCPA 区分器. Ito 等[66]构造了4 轮Feistel 结构的qCCA 区分器, 即4 轮Feistel 结构不是量子强伪随机的(实际上4 轮Feistel 结构是量子伪随机的[4]). 关于Feistel 结构的这些量子区分器构造中, 均假定对结构的量子查询Oracle 进行了截断输出, 但是并没有提出截断Oracle 的实现方法, 直到Hosoyamada 和Sasaki[43]给出一个简单的解决方案: 将存放输出结果的量子寄存器中需要截断的部分量子位都初始化为量子态|+〉.

关于广义Feistel 结构, Ito 和Iwata[67]针对Type-1 型广义Feistel 结构设计了3d-3 轮qCPA 区分器(即qCPA 模型下的多项式级量子区分器) 和d2-d+1 轮qCCA 区分器(即qCCA 模型下的多项式级量子区分器), 其中d为广义Feistel 结构的分支数.

Wang 和Ma[68]构造了3 轮和4 轮非平衡Feistel 结构的量子区分器; Dong 等[69]针对d分支Type-1 型GFN 设计了2d-1 轮量子区分器, 针对2d分支Type-2 型GFN 设计了2d+1 轮量子区分器. 针对4 分支Type-2 型GFN 的5 轮量子区分器, 罗宜元等[70]指出了其中的错误并作出修正. 由于4 分支Type-2 型GFN 需要迭代至少10 轮才能达到经典伪随机性, 因此仅仅构造5 轮量子区分器是没有价值的, 那么能否构造10 轮结构的量子区分器？该问题仍然有待研究. Ni 和Dong[71]继续对Type-1型GFN 的量子区分器做出改进, 分别在qCPA 和qCCA 情况下设计了3d-3 轮区分器. 罗宜元等[70]证明在qCPA 下基于Simon 算法的量子攻击技术可有效攻击3 轮MISTY-L 与MISTY-R 结构, 但不能攻击3 轮Lai-Massey 结构. 该结果由Gouget 等改进, 给出了4 轮MISTY-L 结构的qCPA 区分器[72].对于SM4 型Feistel 结构, Cid 等[73]和我们分别独立给出了7 轮结构的qCPA 区分器, 此外, 我们还设计了8 轮结构的qCCA 区分器.

对这些迭代结构的量子区分器设计进展情况如表1 所示. 易见, 在qCCA 模型下的研究尚不充分, 还存在许多未知项.

表1 Q2 模型下分组密码迭代结构的量子区分器设计进展情况Table 1 Research progress about quantum distinguisher of iterated cryptographic construction under Q2 model

以分组密码结构的量子区分器为基础, 研究人员开展了量子密钥恢复攻击技术研究. Leander 和May[28]提出组合使用Grover 算法和Simon 算法的量子攻击技术框架(简称为“Grover+Simon” 量子攻击框架), 可用于执行量子密钥恢复攻击, 并成功应用于对FX 结构的分析. 这里的FX 结构可描述为FXk0,k1,k2(x)=Ek0(x ⊕k1)⊕k2, 其中密钥长度|k0|=m,|k1|=|k2|=n. 在密码学研究中, FX 结构被用于扩展给定分组密码的密钥长度, 以获得更高的经典安全强度, 例如DESX、PRINCE 和PRIDE 的设计中均采用FX 结构. Leander 和May[28]以Even-Mansour 结构的量子区分器为基础, 采用Grover 算法来搜索给定分组密码的密钥(k0,k1,k2), 只需要O(m+n)2m/2次量子查询. 因此在Q2 模型下, 相对于原分组密码Ek0, 采用FX 结构进行扩展后并没有显著提升量子安全强度.

采用Leander 和May[28]提出的“Grover+Simon” 量子攻击框架, Hosoyamada 和Sasaki[43], 以及Dong 和Wang[51]分别研究了Feistel 结构的量子密钥恢复攻击技术. 前者针对6 轮Feistel 结构分析了恢复全部密钥的攻击复杂度, 其查询复杂度为O((m+n2)2n), 计算复杂度为O(n32n/2), 且只需要使用O(m+n2) 个qubits 的存储(不需要经典存储). 后者针对r轮Feistel 结构设计了量子密钥恢复攻击, 其量子查询次数为O(n2(r-3)n/4), 攻击所需量子比特数为O(n2).

除了对分组密码结构的量子攻击以外, 在Q2 模型下还可对许多认证和认证加密方案进行高效的量子攻击.

在认证方案的量子攻击方面, Boneh 和Zhandry[7]最早设计了一个量子算法, 可在量子多项式时间内攻击Carter-Wegman MAC. 即, 他们证明了该MAC 方案不是EUF-qCMA 安全的: 攻击者经过一次量子选择消息查询就能以高概率获得关键信息, 足以伪造任意消息的合法标记.

该量子攻击技术未能推广到对其它MAC 的攻击, 而基于Simon 量子算法的攻击技术后来被广泛使用, 其中影响较广的研究是Kaplan 等[2]提出的针对CBC-MAC、PMAC、GMAC 等认证模式的量子伪造攻击. 下面分别进行介绍.

CBC-MAC 是一种确定性的MAC, 它有多个变化版本. Kaplan 等[2]给出的量子攻击是针对Encrypted-CBC-MAC 的伪造攻击, 其中使用了两个密钥:k和k′. 但这里的攻击方法容易修改后用于其它版本, 包括CMAC. 对各版本的量子攻击都利用了它们的一个共性: 在对所输入消息块m1‖m2产生认证标记时都执行了形如m2⊕Ek(m1) 的计算, 从而容易设计得到周期函数, 以达到使用Simon 算法的前提条件.

GMAC 是一种随机性的MAC, 增加了一个nonce, 每次都选择一个不同的nonce 值. GMAC 的结构与CBC-MAC 类似, 可采用类似的基于Simon 量子算法的攻击方式, 即使每次查询都更换一个新的nonce, 基于GMAC 查询所构造的周期函数(该函数值必然与nonce 有关) 仍然保持一个与nonce 无关的周期值. 因此, nonce 在GMAC 中的使用方式并不能抵抗这种量子攻击.

Poly1305 是由Bernstein 设计的一个MAC, 已经标准化用于TLS1.2. 对于两分组长度的消息M=m1‖m2, Poly1305 定义为:c1= (m2+ 2128)rmod(2130- 5),c2= (m1+ 2128)r2mod(2130- 5),Poly1305(N,M) =c1+c2+Ek(N), 其中r,k为密钥,N为nonce. 该工作模式中采用“模加” 运算而不是bitwise XOR 运算. 基于Simon 算法的量子攻击无法使用, 但是Bonnetain 和Naya-Plasencia[26]提出基于Kuperberg 算法[75]的量子攻击技术: 根据Poly1305 来设计两个函数f和g, 这两个函数都可基于对Poly1305 的量子选择消息查询来实现, 而且两者存在隐藏移位r使得f(x) =g(x+r); 然后对Kuperberg 算法进行改进并用于寻找这个隐藏移位. Poly1305 的密钥r和k都是128 比特, nonce 和输出的tag 也是128 比特. 改进的Kuperberg 算法仍然是一个亚指数时间的量子算法, 虽然它无法达到Simon 算法那样高效的攻击, 但是对Poly1305 的量子攻击复杂度为238, 在此基础上应用Grover 加速,还可将攻击复杂度进一步降至231. 因此, Poly1305 的安全强度无法达到Q2 模型下的安全性[26].

认证加密工作模式GCM 和OCB 等都通过嵌入一个MAC 模式来产生关联数据的认证部分,Kaplan等[2]将上述对认证模式的量子攻击推广到这些带关联数据的认证加密模式. GCM 和OCB 都是基于nonce 的认证加密模式, 并且对关联数据的认证都与nonce 无关. 对于这两种模式, 当明文中只有关联数据(消息是空值) 时, GCM 正好就等同于GMAC, OCB 正好就等同于PMAC, 因此, 对GMAC 的攻击可直接应用于GCM, 对PMAC 的攻击可直接应用于OCB. 类似地, 还可以把对CBC-MAC 的攻击推广到CLOC,把对PMAC 的攻击推广到AEZ、COPA、OTR、POET 等CAESAR 候选方案. 另外, OMD、Minalpher 也是PMAC 的不同版本, 因此对它们也能采用量子攻击. 对于CAESAR 候选方案AEZ 的其它版本AEZv4、AEZv5 和AEZ10, Bonnetain[76]提出了基于Simon 算法的量子攻击方案, 至此AEZ的所有版本在Q2 模型下都可被完全攻破.

5.2 Q1 模型下的攻击

前面介绍了Q2 模型下对分组密码结构的量子攻击研究. 接下来介绍Q1 模型下的量子攻击研究进展. 与Q2 模型相比, Q1 模型下的量子攻击研究相对较少, 且部分结果是由Q2 模型下的攻击转换而来.

对于Even-Mansour 结构, Kuwakado 和Morii[64]基于量子claw finding 算法, 提出了一种量子密钥恢复攻击方法, 只需要O(2n/3) 次经典查询和O(2n/3) 时间的量子计算.

Hosoyamada 和Sasaki 提出了两类量子中间相遇(MITM) 攻击技术. 第一类是量子Demiric-Selcuk中间相遇攻击(量子DS-MITM)[43], 用于攻击6 轮Feistel 结构; 在经典DS-MITM 攻击下的数据复杂度、时间复杂度和存储复杂度分别为O(23n/4),O(23n/4) 和O(2n/2)[77], 而Q1 模型下DS-MITM 攻击给出的各项复杂度指标均降低至O(2n/2). 第二类被用于攻击一些超生日界安全的MAC 模式Chaskey、可调分组密码TDR、McOE-X、H2-MAC、keyed-sponge, 还可以用于FX 结构获得新的TMT:D·T6=23(n+m)(D ≤min{2n,23(n+m)/7})[42].

Bonnetain 等[29]提出一种全新的思路: 不是将经典模型下的攻击方法向Q1 模型推广, 而是利用离线“Grover+Simon” 算法, 将Q2 模型下量子区分器进行了“部分去量子化” 转换, 设计Q1 模型下的量子攻击. 基于这种思路, 他们设计或改进了针对许多密码结构和模式的量子攻击, 包括Even-Mansour 结构、FX 结构、迭代的FX 结构、轻量级密码Chaskey、Beetle 和SATURNIN 等. 其中, 针对Even-Mansour 结构改进了量子攻击, 只需要多项式规模的经典和量子存储, 针对FX 结构改进了量子攻击的TMT:D·T2=2n+m(D ≤2n).

6 结构和工作模式的量子可证明安全性

结构和工作模式的量子可证明安全性是当前抗量子对称密码研究的重要方向. Q1 模型和Q2 模型所允许的查询方式不同, 导致其安全性证明方面存在很大差异. Q1 模型只允许量子攻击者执行经典查询, 此时的证明方式更接近于经典可证明安全. 然而当允许攻击者执行量子叠加态查询时, 一次查询即可并行地完成对定义域全体元素的查询, 因此量子证明中需要新工具新技术. 下面分别从量子证明工具、带密钥密码原语的量子可证明安全、杂凑密码的量子可证明安全等方面来介绍.

6.1 量子证明工具

目前广泛使用的量子证明工具包括One-way-to-hiding Lemma (O2H 引理[78]) 和压缩预言机技术(compressed oracle technique[20]).

O2H 引理最早由Unruh[78]提出, 后来发展了多个改进版本[79–81], 成为量子安全性证明的主要工具之一. “games-playing” 方式被广泛用于密码安全性证明(特别是一些复杂的构造). 在设计一系列的games 的过程中, 非常关键的技术就是将game 进行随机化: 例如将一个计算值H(x) 替换成一个随机值y(将(x,H(x)) 替换成(x,y)); 如果攻击者可对H执行量子叠加态查询, 那么“如何估计随机化前后两个games 之间的差异” 就成为一个关键问题, 而O2H 引理正好解决了这个问题. 目前O2H 引理已经成为公钥密码在量子随机预言机模型下的安全性证明的重要工具[81–83], 并且它还被用于Q2 模型下的对称密码工作模式的安全性证明, 包括加密工作模式CBC 和CFB 的IND-qCPA 安全性证明[5].

压缩预言机技术用于动态地记录对随机函数的量子查询, 从而有效地模拟量子模型下的随机函数(事实上也可视为lazy-sampling 的量子版). 在经典安全性证明中经常需要记录对随机函数的查询输入/输出值. 但是将这些安全性证明向量子模型迁移的过程中将遇到困难, 因为在量子查询情况下, 实际上对所有叠加分量(即随机函数的定义域全体元素) 都并行地做了查询, 而这些查询的输入输出值无法全部直接记录下来. Zhandry[20]提出压缩预言机技术, 有效地解决了这个问题.

压缩预言机技术是记录量子查询的重要技术, 但是Zhandry[20]的压缩预言机技术是有局限的, 只适用于记录对随机函数的量子查询. 当要记录随机置换的量子查询时, 量子数据库中任何两条记录(x,u) 和(x′,u′) 是存在关联的(即x/=x′时u/=u′), 此时Zhandry 的压缩预言机技术就不能直接使用了. 该局限性已由Unruh[84]解决. Czajkowski 等[85]将压缩预言机技术推广到更一般的情况, 构造非均匀分布随机函数(non-uniformly distributed random functions) 的压缩预言机.

压缩预言机技术是一种重要的量子安全性证明技术, 它被成功地应用于量子叠加态查询情况下结构和模式的安全性证明. 此外, 在量子算法的查询复杂度下界的证明方面, 它也发挥了重要作用, 例如碰撞查找问题[19]、k碰撞查找问题[24], 以及k-xor 问题[86]等的量子求解算法的查询复杂度下界证明.

在经典可证明安全研究中, 伪随机函数-伪随机置换转换引理(PRF-PRP Switching Lemma) 是被广泛应用的工具之一. 利用压缩预言机技术可以证明得到一个量子版本的PRF-PRP 转换引理, 从而作为量子可证明安全的一个基本工具.

除了上述量子证明工具以外, 还有一些证明工具在密码协议的量子安全性研究中发挥了重要作用. 一般地, 在证明协议安全性时, 模拟器需将协议参与方回倒(rewinding) 至以前的状态, 而在协议方是量子参与者的情况下,常规的方式无法做到这一点. Watrous[87]和Unruh[88]各自提出了“quantum rewinding”技术, 分别应用于Goldreich–Micali–Wigderson 图同构零知识证明协议和Σ 协议的量子安全性证明. 现有的“quantum rewinding” 技术都局限于特定情形下的证明, Ambainis 等[89]发展了新的量子证明工具“pick-one trick”, 它是指从给定子空间中搜索满足一定条件的值的搜索技术. 该技术可用于证明协议在量子情况下的安全性或不安全性. “quantum rewinding” 和“pick-one trick” 技术能否用于对称密码的量子可证明安全？目前还有待探索.

与经典安全性证明相比, 通常在量子情况下的安全性证明过程都相当复杂, 对量子态和量子运算的推导也非常容易出错. 如果能够采用计算机辅助证明, 则可提高证明的可靠性. Unruh[90]提出了quantum relational hoare logic (qRHL), 适用于计算机辅助执行对密码算法(包括量子密码和抗量子密码) 的量子安全性形式化分析, 但是目前该工具还不够完善.

6.2 带密钥原语的量子可证明安全

现有的一些结构和工作模式被证明满足量子安全性, 即, 在量子安全模型下证明: 当底层函数满足伪随机性, 整体结构和工作模式也能达到伪随机性. 在具体介绍量子可证明研究结果之前, 我们约定将Q2模型下的伪随机函数和伪随机置换分别记为qPRF 和qPRP, Q1 模型下的伪随机函数和伪随机置换分别记为sPRF 和sPRP.

对于加密工作模式, Anand 等[5]证明了CBC、CFB、OFB 和CTR 模式在Q2 模型下的量子可证明安全性: 将CBC、CFB、OFB、CTR 等模式的IND-qCPA 安全性归约到底层分组加密函数在Q2模型下的伪随机性, 即, 这四种模式中任何一个都可将定长定义域上的qPRF 扩展得到一个变长定义域上的qPRF. 他们还研究发现, 工作模式要达到Q2 模型下的量子安全性并不一定要求底层分组加密函数是qPRF 或qPRP. 例如, 对于OFB 和CTR, 仅要求底层函数达到sPRF 的安全要求, 它们就能满足Q2模型下的IND-qCPA 安全性; 而对于CBC 和CFB, 如果底层函数是一个sPRF 但不是qPRF, 则它们也只能达到Q1 模型下的安全性.

对于认证工作模式, Song 和Yun[6]在Q2 模型下证明了NMAC、HMAC、AMAC 和定长输入的Cascade 构造都是量子伪随机的. 因此,它们都可作为由qPRP 构造qPRF 的变换. 由于qPRF 直接作为MAC 使用时就可以满足EUF-qCMA 安全性[7], 因此这4 种构造都是Q2 模型下量子安全的认证模式.他们的证明所确定的NMAC(或HMAC)的量子安全性界为O(2n/5)(或O(2n/8))次量子查询,其中n为输出长度. Hosoyamada 和Iwata[91]给出了更紧的量子安全界: 在量子随机预言机模型下, 区分HMAC(或NMAC) 和随机函数所需量子查询次数至少为Ω(2n/3). 由于通用量子碰撞攻击下需要O(2n/3) 次量子查询, 我们获得量子安全界Θ(2n/3).

对于Feistel 结构,3 轮迭代即可达到经典伪随机性,但是不满足Q2 模型下的伪随机性. Hosoyamada和Iwata[4]证明了4 轮Feistel 结构可达到Q2 模型下的伪随机性: 若f1,f2,f3,f4是独立的qPRF, 则4 轮迭代函数Feistel4(f1,f2,f3,f4) 就是一个qPRP. 在经典模型下, 4 轮Feistel 迭代结构能够达到强伪随机性, 然而在Q2 模型下需要迭代多少轮才能达到量子强伪随机性？这个问题还有待研究.

Czajkowski 等[3]证明当内部函数是带密钥的函数或置换时, Sponge 结构可达到Q2 模型下的伪随机性: 若内部函数f是qPRF 或qPRP, 则根据Sponge 结构进行扩展所得函数SPONGEf是一个qPRF.因此, Sponge 结构可用于Q2 模型下的抗量子对称密码设计.

6.3 杂凑的量子可证明安全

这里的杂凑函数都是指无密钥的函数, 而带密钥的杂凑函数可视为一种认证来研究. 目前, 杂凑结构的量子可证明安全研究主要涉及量子抗碰撞性、Collapsing 以及量子不可区别性(quantum indifferentiability) 等安全属性.

Sponge 结构是一种被广泛应用的杂凑结构, 对它的量子安全性研究也是最多的. Czajkowski 等[92]证明了Sponge 结构的量子抗碰撞性, 该结论要求内部函数f满足以下条件: 截断f输出的左半或右半部分时均满足抗碰撞性, 且截断f输出的左半部分时难以找到0 对应的原像. 他们还证明了Sponge 结构满足Collapsing 属性: 当内部函数f是随机函数或随机置换时, Sponge 结构满足Collapsing 安全属性(这里要求随机置换f不可有效求逆). 该结果存在局限性, 不能应用于SHA3 的量子安全性证明, 因为SHA3使用了一个有效可逆的置换作为f. Unruh[38]证明了Merkle-Damgaard 结构满足Collapsing 安全属性,即,当底层压缩函数f是Collapsing,则MDf也是Collapsing. 针对杂凑结构的Collapsing 证明,Fehr[93]提出一套证明框架, 允许我们以纯经典(不涉及任何量子推理) 的方式来证明杂凑结构的Collapsing 安全性. 基于这套证明框架, 他们重新证明了MD 结构和Sponge 结构是Collapsing, 并且新证明了HAIFA结构也满足Collapsing. Gunsing 和Mennink[94]将该框架应用到tree hash 的Collapsing 证明.

与量子抗碰撞性和 Collapsing 等安全属性的证明相比, 量子不可区别性的证明难度要大很多.Zhandry 提出的压缩预言机技术发挥了关键作用, 他证明了(在prefix-free encoding 情况下) Merkle-Damgaard 结构满足量子不可区别性. Czajkowski 等[85]改进Zhandry 的压缩预言机, 证明了: 当内部函数是随机函数或随机置换时, Sponge 结构是量子不可区别的, 并证明由量子不可区别性可推导出Collapsing, 因此Sponge 结构也满足Collapsing. 注意, 这里的Collapsing 证明不要求Sponge 结构的内部函数f不可有效求逆, 从而克服了他们早期证明结果[92]中的局限性.

Carstens 等[95]给出一个否定性的证明: Sponge 结构不满足完美的量子不可区别性. 注意这与Sponge 结构的量子不可区别性证明并不矛盾, 因为一般所说的量子不可区别性证明并不要求零区分优势.

上述量子可证明安全研究主要关注Collapsing 和量子不可区别性等. 量子抗碰撞性和量子抗原像性等都是在量子模型下对传统杂凑安全属性的增强, 我们还应该研究杂凑结构是否满足这些量子安全属性.Hamlin 和Song[37]证明了由Andreeva 等提出的杂凑结构ROX[96]的量子安全性: 当底层压缩函数f满足量子抗碰撞性/量子抗原像性/量子抗第二原像性时, ROXf也满足相应的量子安全属性. Hosoyamada和Yasuda[97]证明了基于Davies-Meyer 压缩函数的Merkle-Damgard 迭代构造满足量子抗原像性, 这意味着该构造是一个量子可证明安全的单向函数.

7 抗量子计算对称密码设计

与传统对称密码相比, 抗量子对称密码在设计方面尚未发现本质差异. 虽然一些对称密码方案遭受了不同程度的量子计算攻击, 但是仍然有很多传统对称密码方案是量子安全的; 并且对于遭受量子计算攻击的方案, 经过改造仍然可能达到量子安全性. 接下来具体介绍相关研究进展情况.

量子伪随机函数是抗量子对称密码研究中基本的密码学原语. 最早是在2012 年Zhandry[98]给出了Q2 模型下的3 种伪随机函数的设计方法: (1) 基于Q1 模型下的伪随机发生器, 采用Goldreich、Goldwasser 和Micali[99]的伪随机函数(即GGM-PRF) 的构造方法, 可获得Q2 模型下的伪随机函数(即qPRF);(2)基于Q1 模型下的伪随机合成器,采用Naor 和Reingold[100]的伪随机函数(即NR-PRF)的构造方法, 也可获得qPRF; (3) Banerjee、Peikert 和Rosen[101]基于LWE 困难问题构造的伪随机函数(即BPR-PRF) 也是一种qPRF. 与前两种不同, 后者是一种直接构造且其安全性基于标准的困难性假设. Mennink 和Szepieniec[102]提出一种XOR 设计方法:F(k1,k2,··· ,kr,x)=⊕Eki(x), 当E是Q1 模型下的伪随机置换(sPRP) 时,F就是Q1 模型下的伪随机函数(sPRF). 他们并没有考虑XOR 设计在Q2 模型下的安全性. Dottling 等[103]研究在Q2 模型下采用新的XOR 方式来设计qPRF: 给定一个小定义域(多项式规模) 上的PRF, 如果它满足Q1 模型下的伪随机性, 则根据他们的XOR 构造方法,可获得一个大定义域(指数规模) 上的qPRF. 由于Czajkowski 等[3]在Q2 模型下证明了Sponge 结构(使用带密钥的内部函数时) 的量子伪随机性, 理论上采用Sponge 结构也可构造qPRF, 例如后面将会介绍的对CBC-MAC 的“类Sponge” 改造也可视为一种qPRF 设计.

在量子伪随机置换设计方面, Zhandry[104]最早于2016 年提出了基于qPRF 构造qPRP 的设计框架,即函数-置换转换器(FPC):给定一个qPRF,就可用FPC 产生一个qPRP,未直接设计qPRP.虽然他提到了基于Feistel 结构来作为FPC 的想法, 但是缺乏量子证明工具而未能证明. 直到2018 年Zhandry提出压缩预言机技术(后正式发表于文献[20]) 之后, Hosoyamada 和Iwata[4]于2019 年利用该技术证明了4 轮Feistel 结构与随机置换是Q2 模型下量子不可区分的. 根据该结论, 4 轮Feistel 结构可作为由qPRF 向qPRP 转换的FPC.

在量子安全的MAC 设计方面, 目前研究人员尚未开展全新设计, 而是对不安全的旧MAC 方案进行改造设计, 从而获得量子安全的MAC. 在改造时需要考虑量子攻击的特点给出有针对性的防护设计.Boneh 和Zhandry[7]在Q2 模型下给出了Carter-Wegman MAC 的量子多项式时间攻击技术, 同时提出一条安全改造措施: 将原设计中的变换CWMAC(key,m) = (nonce,PRF(key,nonce)+H(m)) 改造成CWMAC(key,m) = (R(m),PRF(key,R(m))+H(m)), 其中H和R分别是从XOR-通用哈希函数族H和两两独立无关函数集合R中随机选取的. 其改造思路是将nonce 替换成一个与消息m相关的随机值,经过改造之后, 在量子叠加态查询时不同叠加分量之间就采用了独立无关的随机数R(m), 从而可有效预防Q2 模型下的量子伪造攻击. 他们严格证明了该改进版是EUF-qCMA 的[7]. 对于CBC-MAC 认证模式, 虽然它在Q2 模型下存在量子多项式时间伪造攻击[2], 但是可依据Sponge 结构的量子伪随机性[3],按以下“类Sponge” 的方式来安全改造CBC-MAC: (1) 将CBC-MAC 的输入消息分成r比特消息块mi ∈{0,1}r,i=1,2,··· ,N; (2) 每个消息块填充0c, 即mi →mi ‖0c, 以r+c比特块作为CBC-MAC的输入分组; (3) 将CBC-MAC 的输出截断为前r个比特. 经过这种填充和截断改造后的CBC-MAC 类似于Sponge 结构, 正好等价于Sponge 结构使用带密钥的内部置换的情形, 从而达到Q2 模型下的量子伪随机性. 因此改造后的方案是EUF-qCMA 的.

其它方面还有对可调分组密码结构和认证加密模式的安全改造设计. Hosoyamada 和Iwata[105]改造了可调分组密码结构 LRW, 改造后的版本记为 LRWQ, 简单描述为:(m) =Ek3(Ek1(m)⊕Ek2(tweak)), 他们在Q2 模型下利用压缩预言机技术证明结论: 若E是qPRP, 则LRWQ是可调的qPRP. Bhaumik 等[106]对认证加密模式OCB 进行改造, 设计了新的认证加密模式QCB, 并证明了该模式在Q2 模型下的量子可证明安全性.

为了应对基于Simon 量子算法的攻击技术, Alagic 和Russell[107]从底层运算改造的思路出发, 提出将分组密码结构或模式中普遍使用的XOR 运算替换成“模2n加” 运算, 从而抵抗基于Simon 算法的量子攻击, 但随后被Bonnetain 和Naya-Plasenci[26]指出这种改造未必有效, 因为它们还有可能受到改进的Kuperberg 算法的亚指数时间攻击, 例如Poly1305 认证模式在这种攻击下的量子安全强度可降低至231.

目前的抗量子设计研究主要关注密码结构或工作模式在量子安全模型下的整体安全设计, 然而在实例化的抗量子设计方面仍然缺乏研究. 如何进行实例化的密码算法设计以获得相对更高的量子安全强度？这是当前研究中的一个难点. 从对称密码算法设计角度来看, 抗量子设计与传统设计相比并没有本质区别,两者都要通过设计迭代结构和轮函数以及算法参数等来完成算法设计, 然而所设计对称密码算法能否抗量子计算攻击, 仍然需要通过量子安全性分析. 因此, 抗量子设计深度依赖于量子安全性分析成果, 通过开展量子安全性分析研究, 积累量子攻击技术和量子证明成果, 同时提炼抗量子设计准则, 保证算法设计中所用密码结构和密码部件都具有相对更高的量子攻击复杂度.

8 总结与展望

从目前的研究来看, 在量子计算攻击背景下, 对称密码设计技术所受影响相对较小, 原有的很多结构或模式被证明满足量子可证明安全性, 具体密码算法如AES 的安全强度虽然受到削弱, 但可通过增大算法参数来弥补. 但这并不意味着不必继续研究抗量子对称密码. 从密码学的发展历史来看, 密码设计与分析技术始终随着计算技术的进步而不断发展, 而量子计算是一种高效的物理可实现的全新计算技术, 因此量子计算融入密码学研究必然成为未来的发展趋势.

在抗量子对称密码研究中, 在量子计算攻击技术、量子安全性证明、量子安全强度量化评估、抗量子对称密码设计等方面亟需进一步加强研究, 具体可从以下几个角度进行探索.

(1) 面向密码分析研究领域的量子算法探索. 量子计算为数学问题求解提供了一些强大的算法, 但是目前尚未充分挖掘这些量子算法在密码分析中的潜力. 密码学者可将Grover 搜索算法、Simon 量子算法、Kuperberg 算法、HHL 算法等量子算法应用于更多密码算法的量子安全性分析; 还要继续发掘现有的其它量子算法, 研究能否应用于密码算法分析, 从而提供更多的量子安全性分析工具; 针对具体密码学相关数学问题设计新的量子算法, 应用于特定的对称密码方案的量子安全性分析.

(2) 抗量子计算安全强度及资源消耗量化评估. 目前的量子安全强度量化评估大多还停留在研究基于Grover 穷举搜索和量子碰撞查找等通用量子攻击下的安全强度量化评估, 而很少考虑专用的量子攻击技术, 因此不能全面地反映对称密码算法的量子安全强度. 此外, 还有必要结合量子计算机物理架构和发展程度, 综合选取适当的评价指标作为量子安全及资源量化评估标准, 从而优化对密码算法抗量子计算攻击的分析.

(3) 抗量子计算密码结构的可证明安全分析. 对称密码的量子安全性证明比经典模型下要复杂得多,遇到的困难也非常多. 由于密码结构的量子安全性证明过程通常都过于繁琐, 一方面需要开展量子证明工具研究从而简化证明; 另一方面还要开展计算机辅助证明技术研究, 特别是形式化证明技术. 此外, 还有一个重要的方向是开展具有一定普适性的抗量子安全机理研究, 建立从Q1 模型向Q2 模型的安全性提升变换框架, 在该框架下可将Q1 模型下的量子安全性证明提升到Q2 模型.

(4) 抗量子对称密码设计. 目前的研究成果集中于抗量子分析方面, 而抗量子对称密码设计相对较少.可以深入分析这些量子攻击和量子证明的共性机理, 归纳总结量子安全设计规范, 在此基础上改造旧方案获得量子安全的新设计. 此外, 在设计具体的密码算法实例时, 一般认为应该将密钥长度增加大约一倍以抵抗量子计算攻击. 然而密钥长度的增加将大大提高密码算法的设计难度和实现开销. 是否存在其它途径, 将密钥长度少量增加甚至不增加, 仍然能够达到预期的量子安全强度.

(5) 真实量子环境下的对称密码算法安全性. 还有一类非常重要但长期被忽视的问题: 密码算法在未来的真实量子计算机下的安全性. 对密码算法的量子攻击最终是要在真实的量子计算机上实施的, 然而目前的主流研究都在理想化的量子计算模型(即纯数学描述的量子计算框架) 下评估密码算法的量子安全强度. 在现实情况下, 量子比特都是一个个微观的量子物理系统, 利用它们执行计算时, 操控这些量子比特或者相互之间传递状态信息都将受到物理定律的限制, 那么现实的量子计算模型下密码算法的量子安全强度如何去评估？物理定律是否会限制量子计算的逻辑门深度或者量子比特数量的理论极限？杨理等[108,109]初步探索了离子阱量子计算机在物理定律限制下所容许的逻辑门深度, 然而解决上述这些难题还需要更多的努力. 此外, 对于n比特密钥的对称加密算法, 经典穷举攻击需要O(2n) 次经典计算, 而量子穷举攻击需要O(2n/2) 次量子计算; 那么考虑真实的量子计算时,O(2n/2) 次量子计算从物理实现角度是否具有现实可行性？即使可行, 那么实际的时间复杂度与O(2n) 次经典计算相比还有多少优势？目前这些问题仍然有待探索.