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

黄明 等: 分组密码复杂线性层可分性传播的 MILP 刻画方法 1987

算法 1. 构建基于动态选取策略刻画线性层可分性传播的 MILP 模型.

n
n
输入: 一个复杂线性层矩阵 M ∈ F n×n , 其输入可分性 u = (u 0 ,u 1 ,...,u n−1 ) ∈ F , 输出可分性 v = (v 0 ,v 1 ,...,v n−1 ) ∈ F ,
2 2 2
n+1 个点的集合 D = {(a 0,0 ,a 0,1 ,...,a 0,⌊ log 2 n⌋ +r ),...,(a 1,0 ,a 1,1 ,...,a 1,⌊ log 2 n⌋ +r ),(a n,0 ,a n,1 ,...,a n,⌊ log 2 n⌋ +r )} , 集合元素 (a 0 ,a 1 ,...,
⌊ ⌋
0
a ) ∈ D 中 a i ∈ {0,1}(0 ⩽ i ⩽ log n +r) , 且 2 ⌊ log 2 n⌋ a 0 +2 ⌊ log 2 n⌋ −1 a 1 +...+2 a⌊log 2 n⌋ ∈ {0,1,...,n} ; 另外, r 表示将输

⌊ log 2 n⌋ +r 2
,a
入可分性汉明重量分为 r 种情况: {0,n},Θ ZR 0 ,Θ ZR1 ,...,Θ ZR r−3 ,Θ HZ , 相应每种分类中对应元素 (a ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 ,...,
a ) (1,0,...,0),(0,1,...,0),(0,0,...,1) ;
⌊ log 2 n⌋ +r 分别取
输出: 矩阵 M 可分性传播的约束条件 L .
1) begin
2) L ← 刻画集合 D 中元素 (a 0 ,a 1 ,...,a ) 的约束集 L wt
⌊ log 2 n⌋ +r
0
3) L ← 2 ⌊ log 2 n⌋ a 0 +2 ⌊ log 2 n⌋ −1 a 1 +...+2 a⌊log 2 n⌋ = wt(u) // (a 0 ,a 1 ,...,a ) 与输入可分性汉明重量 wt(u) 对应
⌊ log 2 n⌋
4) for i = 0 to n do

5) if i ∈ {0, n}
6) L ← (a = 1 → w(u) = w(v))
⌊ log 2 n⌋ +1
7) else if i ∈ Θ ZR 0 ∪Θ ZR 1 ∪...∪Θ ZR r−3

8) for j = 0 to r −3 do
9) L ← (a ) // 表示用 ZR 方法刻画 wt(u) = i 可分性传播所需不等式
⌊ log 2 n⌋ +j+2 = 1 → L ZR i L ZR i
10) end for
11) else if i ∈ Θ HZ
12) L ← (a = 1 → L HZ ) // L HZ 表示用 HZ 方法刻画可分性传播所需不等式
⌊ log 2 n⌋ +r
3) end if
14) end for
15) return L
16) end

值得注意的是: 当 Θ HZ = ∅ 时, 此时动态选取策略退化为 ZR 方法, 且不适用于复杂线性层矩阵 M ∈ F n×n , 因
2
Θ ZR ,Θ HZ 的取值范围需要进行进一步的限制, 我们建议当 n=16 时, 分类为{0, 16},
此对上述分类情况中{0,n},
Θ ZR ⊆ {1,2,3,4,12,13,14,15}, Θ HZ ={1,2,...,15}\Θ ZR ; 当 n=32 时, 分类为{0, 32}, Θ ZR ⊆ {1,2,3,29,30,31},

Θ HZ = {1,2,...,31}\Θ ZR ; 当 n > 32 时, 分类为 {0,n}, Θ ZR ⊆ {1,2,n−2,n−1} Θ HZ = {1,2,...,n−1}\Θ ZR .
,
2.3 动态选取策略刻画线性层可分性传播的分析
ZR 方法刻画输入汉明重量对应可
动态选取策略刻画线性层可分性传播的方法并不局限于用 HZ 方法代替
分迹不等式较多的情况, SW 方法同样适用. 本文采用 HZ 方法的主要原因是 HZ 方法刻画线性层可分性传播
SW 方法 [12] HZ 方法刻画线性层的可
的精确程度不弱于 . 本质上动态选取策略是通过 ZR 方法结合 SW 方法或
分性传播. 假设 X 方法为 SW 方法和 HZ 方法中的任意一种, 并将 ZR 方法结合 X 方法记为 Z + X. 接下来, 本节
将讨论 ZR + X 方法不弱于 X 方法的理论依据.
n
给定一个可逆矩阵 P ∈ F n×n , 记其输入可分性为 u = (u 0 ,u 1 ,...,u n−1 ) ∈ F . 假设将线性层的输入可分性按照汉明
2 2
重量的不同划分为 m (2 ⩽ m ⩽ n) 类情况, 随后将上述 m 类情况分别通过 ZR 方法或 X 方法刻画线性层的可分性
传播. 根据定理 1, 当使用 ZR 方法刻画线性层的可分性传播时, 其可分迹对应的 wt(u) 阶子矩阵一定为可逆矩阵.
然而根据文献 [12], 当使用 X 方法刻画线性层的可分性传播时, 其可分迹对应的 wt(u) 阶子矩阵一定包含置换矩
ZR + X ZR 方法刻
阵. 因此, 方法刻画线性层可分性传播的可分迹由如下两部分组成: (1) 当某些输入可分性采用
画线性层可分性传播时, 其可分迹对应的子矩阵一定为可逆矩阵. (2) 当某些输入可分性采用 X 方法刻画线性层