Page 397 - 《软件学报》2026年第5期

2276 软件学报 2026 年第 37 卷第 5 期

第 1 节为预备知识, 主要介绍符号约定、相关性的定义及差分-线性分析的框架. 第 2 节介绍本文改进的差分-
线性区分器搜索算法. 第 3 节介绍所提搜索算法在 SPECK32 和 SPECK48 上的应用. 第 4 节是本文总结.

1 预备知识

1.1 符号和定义
表 2 给出了本文中用到的符号及其定义.

表 2 符号定义

符号 描述 符号 描述
⊕ XOR操作 · 向量内积
⊞ ⊟ 模加/模减操作 ° 函数复合
/
[i] 第 i 个分量取值为1, 其他分量取值为0的单位向量 ≪ 循环右移位
[i 0 ,i 1 ,...,i l ] 第 i 0 ,i 1 ,...,i l 个分量取值为1, 其他分量取值为0的向量 ≫ 循环左移位
|S | 集合 S 中元素的个数 ∪ 集合求并集

定义 n f : F → F 2 , 相关性被定义为:
n
2 2
1. 给定集合 S ⊆ F 和布尔函数
1 ∑
Cor x∈S ( f) := (−1) f(x) .
|S |
x∈S
1.2 差分-线性分析
Langford 等人 [7] 结合差分分析和线性分析, 提出了差分-线性分析, 接下来我们统称 Langford 等人的框架为原
始的差分-线性分析框架. 在原始的差分-线性分析框架中, 密码算法 E 被分解为 E 0 和 E 1 两部分, 即 E = E 1 ◦ E 0 , 其
E 0
中 E 0 和 E 1 部分的轮数分别为 r 0 和 . 在 E 0 部分有概率为 p 的差分 ∆ in −→ ∆ m , 在 E 1 部分有相关性为 q 的线性逼近
r 1
E
λ in −→ λ out , 如图 1 所示. 密码算法 E 的 r 0 +r 1 轮的差分-线性逼近 ∆ in −→ λ out 的相关性被计算为:
E 1

2
Cor(λ out · E(x)⊕λ out · E(x⊕∆ in )) = pq .

Δ in
E 0 E 0
p
Δ m
λ m λ m
q q
E 1 E 1
λ out λ out
图 1 原始的差分-线性分析框架

原始的差分-线性分析框架依赖于如下的两个假设.
(1) E 0 部分和 E 1 部分之间是相互独立的.
1
(2) 当 ∆ X = E 0 (x)⊕ E 0 (x⊕∆ in ) , ∆ m , λ out ·∆ X = 0 成立的概率为 .
2
然而, 后续的研究指出上述两个假设在实际中并不一定是满足的. Biham 等人 [8] 指出假设 (2) 在许多情况下是
不满足的, 并给出了相关的实验验证. 之后, Blondeau 等人 [9] 给出了在不依赖于假设 (2) 的情况下的差分-线性逼近
相关性的计算公式. 在假设 E 0 部分和 E 1 部分之间是相互独立的情况下, 差分-线性区分器的相关性被计算为:

∑
Cor(λ out · E(x)⊕λ out · E(x⊕∆ in )) = Cor(λ m · E 0 (x)⊕λ m · E 0 (x⊕∆ in ))·Cor(λ m ,λ out ).
λ m
关于 E 0 部分和 E 1 部分之间的依赖性问题很长一段时间内没有被解决. Boomerang 分析也是一种差分类的组
合分析方法, 在 boomerang 分析中也存在类似的依赖性问题. Cid 等人 [11] 给出了 BCT 表 (boomerang 连接表) 来解