Page 406 - 《软件学报》2024年第4期

1984 软件学报 2024 年第 35 卷第 4 期

M
模型 3. i 阶可逆子矩阵 [10] . 记 (u 0 ,u 1 ,...,u n−1 ) → (v 0 ,v 1 ,...,v n−1 ) 表示复杂线性层矩阵 M 的可分迹, 下面的线性
约束可描述输入汉明重量 wt(u) = i (1 ⩽ i ⩽ n−1) 的可分性传播, 其中 M(j,∗) 表示由矩阵 M 的第 j 行组成的行
向量.
 ( )
t i−1
 ∑
 t i−1
 T
 ⊕ M( j,∗) (u 0 ,u 1 ,...,u n−1 ) − v j −(i−1), t 0 ,t 1 ,...,t i−1 ∈ {0,1,...,n−1}



j=t 0 .
 j=t 0






u 0 ,u 1 ,...,u n−1 ,v 0 ,v 1 ,...,v n−1 ∈ {0,1}
更为具体的描述请参考文献 [10].
2 基于动态选取策略刻画线性层可分性传播
本节提出一种基于动态选取策略构建 MILP 模型的新方法, 该方法针对线性层不同汉明重量的输入可分性,
n n/2 时, 利用
采取不同的技术刻画线性层的可分性传播. 对于一个 F 上的线性变换, 当输入可分性的汉明重量趋近
2
HZ 方法刻画线性层的可分性传播; 否则, 将利用 ZR 方法刻画线性层的可分性传播. 本节将首先介绍 ZR 方法和
HZ 方法, 并简要分析上述两种方法的优缺点; 其次, 详细介绍动态选取策略构建 MILP 模型的建模过程; 最后, 从
理论上证明动态选取策略构建 MILP 模型不弱于 SW 方法、 EY 方法、 HZ 方法.
2.1 两种刻画线性层可分性传播的方法
本文主要通过动态选择 ZR 方法和 HZ 方法构建可分性传播的 MILP 模型, 因此本节先详细介绍上述两种方法.
2.1.1 ZR 方法简介
Zhang 等人 [10] 通过研究线性层可分性传播和线性层可逆子矩阵之间的关系, 提出精确刻画线性层可分性传播
的方法.
M
定理 1 [10] . 对矩阵 M ∈ F n×n , 记 u,v ∈ F 分别为矩阵 M 的输入可分性和输出可分性, 即 (u 0 ,u 1 ,...,u n−1 ) → (v 0 ,v 1 ,
n
2 2
M
...,v n−1 ) u → v 是一条有效可分迹的充要条件是 M v,u 是可逆的, 其中 M v,u 表示以 I v = {i,v i = 1} 的索引作为行, I u =
.
{i,u i = 1} 的索引作为列构成的 M 的子矩阵.
根据上述定理, 线性层的有效可分迹对应的子矩阵一定是可逆矩阵. 因此, Zhang 等人通过一组不等式
L ZR ) 刻画了线性层的所有可逆子矩阵, 从而构建线性层的可分性传播模型. 然而, 上述不等式刻画仅适用于
(记为
′ ′ s×s ′ M = (m i,j ) n×n ∈ F n×n , 并将本原矩
二元矩阵. 对二元矩阵 M = (m ) s×s ∈ F m , 令 n = s×m , 可以将 M 表示成其本原矩阵 2
2
i,j
阵的行划分为 m 个陪集: S 0 ={0,m,...,(s−1)×m},S 1 ={1,m+1,...,(s−1)×m+1},...,S m−1 ={m−1,2m−1,..., sm−1} ,
则在不同陪集中对应元素的列没有相同的非 0 元素, 因此在刻画二元矩阵可分性传播的过程中可以分别考虑每
)
(∑
s−1
i
一列的异或, 即只需刻画每个陪集对应的行所组成的可逆子矩阵, 所需不等式的数量为 #L ZR = m C +1 =
s
i=1
s n×n 则无法与二元矩阵一样进行矩阵行的陪集划分. 通常
m×(2 −1). 对于非二元矩阵的本原矩阵 M = (m i,j ) n×n ∈ F 2
i 阶可逆子矩阵所
需要将矩阵的所有行作为一个集合, 从而刻画所有阶的可逆子矩阵. 当 i ∈ {1,2,...,n−1} 时, 刻画
i ZR 方法需
需不等式的数量为 #L ZR i = C ; 当 i ∈ {0,n} 时, 需要约束条件 w(u) = w(v) 刻画可分性的传播. 因此, 利用
n
n−1 n−1
∑ ∑
#L ZR = +1 = i n M ∈ F n×n 的所有有效可分迹. 目前, 大多
要 #L ZR i C +1 = 2 −1 个约束不等式刻画非二元矩阵 2
n
i=1 i=1
n 均大于等于
数密码算法线性层矩阵对应本原矩阵的阶数 16, 即利用 ZR 方法刻画非二元矩阵的可分性传播时,
#L ZR = 2 −1 = 65535 . 受限于约束不等式的数量, 自动化求解器无法在有限的时间求
16
需要的不等式数量至少为
解该方法构建的自动化模型.
2.1.2 HZ 方法简介
n
记密码算法线性层操作为 y = M x (x, y ∈ F , M ∈ F n×n ), 线性层优化实现算法按照可分性传播的角度可分为如
2 2
下两类: (1) 线性层优化实现算法中异或操作的两个变量中不存在相同的元素, 例如 Paar 算法 [18] ; (2) 线性层优化
实现算法中异或操作的两个变量中可能存在相同的元素, 例如 BP 算法 [19] 和 XZ 算法 [20] . 研究表明: 当异或操作的