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

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

SW 方法中部分无效的可分迹; 当异或操
两个变量中不存在相同的元素时, 该优化实现刻画的可分性传播会删除
作的两个变量中可能存在相同的元素时, 该优化实现刻画的可分性传播不仅会删除 SW 方法中部分无效可分迹,
同时也会引入 SW 方法中不包含的无效可分迹.
在文献 [12] 中, Hong 等人通过理论证明了利用 Paar 算法的优化实现刻画线性层可分性传播的精确程度不弱
SW 方法. 同时, 利用 BP 和 XZ SW 方法中的无效可
于 算法的优化实现刻画线性层可分性传播可以进一步减少
分迹, 但其也引入了一些 SW 方法中不存在的无效可分迹. 因此, 作者通过同时考虑上述几种优化实现构建线性
层可分性传播的 MILP 模型. 考虑到线性层优化实现算法中只是使用辅助变量减少了可分性传播过程中异或的次
SW 方法中的所有无效可
数, HZ 方法刻画的可分迹组成的子矩阵不一定都是可逆的, 该方法通常不能删除
分迹.
综上所述, ZR 方法和 HZ 方法均存在各自的优缺点. ZR 方法可以完全精确地刻画线性层的可分性传播, 但
SW 方法, 无
是它不能应用于非二元矩阵; 对于 HZ 方法, 它可以应用于任意复杂的线性层. 但是该方法仅能优于
法保证达到完全精确刻画线性层的可分性传播. 为了权衡精确性和实用性, 本节将介绍一种新技术刻画复杂线性
层矩阵的可分性传播.
2.2 基于动态选取策略构建线性层可分性传播的 MILP 模型
M
M ∈ F n×n i (1 ⩽ i ⩽ n−1) 的
在刻画复杂线性层矩阵 可分迹 u → v 的过程中, ZR 方法精确刻画输入汉明重量为
2
i ZR 方法刻画可分性传播
可分迹所需不等式的数量为 = C , 显然随着输入可分性汉明重量的逐渐增加使用
#L ZR i n
n/2 时达到最大. 事实上, 当输入可分性汉明重量
所需的不等式数量先增加后减少, 并在输入可分性汉明重量趋近
对应的可分迹刻画不等式数量较多时, 我们可以用 HZ 方法代替 ZR 方法, 且此时 MILP 模型可以在有限的时间
内求解, 我们将这种根据输入可分性汉明重量的不同而采取不同方法刻画可分迹构建 MILP 模型的方法称为动态
选取策略, 并且结合 Indicator 约束建模, 我们可以很自然的实现上述 MILP 建模.
对矩阵 M ∈ F n×n , 其输入可分性汉明重量 wt(u) ∈ {0,1,...,n} 共 n+1 情况, 我们将这 n+1 种情况根据 ZR 方法
2
所需不等式数量进行分类: 即将集合 {0,1,...,n} 划分为 {0,n},Θ ZR ,Θ HZ 这 3 个部分, 其中 Θ ZR 表示 ZR 方法中精确
刻画可分迹所需不等式数量较少的那些输入汉明重量的集合, Θ HZ = {1,2,...,n−1}\Θ ZR . 由于 Indicator 约束
z = f → L 中 f ∈ {0,1}, 而输入汉明重量的取值并不只有 0 和 1 两种情况, 在使用 Indicator 约束对输入汉明重量
⌊ ⌋
进行分类时需要借助临时变量表示不同的汉明重量. 具体地, 对 wt(u) ∈ {0,1,...,n}, 用 log n +1 维向量 a=
2
(a 0 ,a 1 ,...,a 2 ⌊ log 2 n⌋ a 0 +
⌊ log 2 n⌋ ) ∈ {(0,0,...,0),(0,0,...,1),...,(1,0,...,0)} 表示输入可分性汉明重量的全部情况, 其中
0
2 ⌊ log 2 n⌋ −1 a 1 +...+2 a⌊log 2 n⌋ = wt(u) . 然后将向量 a 的维数扩充 3 维:
 
 (0,0,...,0,0)  (0,0,...,0,0,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )
 
 | {z }  | {z }
 
 
 
 ⌊log 2 n⌋+1个0  ⌊log 2 n⌋+1个0
 
 
 (0,0,...,0,1)  (0,0,...,0,1,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )


 
 
 
 
 
 
  (0,0,...,1,0,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )

 (0,0,...,1,0)
 
 
 
 
 
 
 (0,0,...,1,1)  (0,0,...,1,1,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )


 
  ,
 → 
 
 .  .
 .  .
 
 .  .
 
 
 
 
 
 
 (0,1,...,1,0)  (0,1,...,1,0,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )




 
 
 
 
 
 (0,1,...,1,1)  (0,1,...,1,1,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )




 
 
 
 
 
(1,0,...,0,0) (1,0,...,0,0,a ⌊log 2 n⌋+1 ,a ⌊log 2 n⌋+2 ,a ⌊log 2 n⌋+3 )
 
⌋
a ,a ,a ⌊ log n +1 个变量表示的汉明重量以及汉明重量的分类情况{0, n},
其中, ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 ⌊ log 2 n⌋ +3 的取值根据前 2
a a = 1;
Θ ZR ,Θ HZ 分别取 (1,0,0),(0,1,0),(0,0,1) . 具体地, 当 wt(u) ∈ {0,n} 时, ⌊ log 2 n⌋ +1 = 1 ; 当 wt(u) ∈ Θ ZR 时, ⌊ log 2 n⌋ +2
当 wt(u) ∈ Θ HZ 时, a = 1. 然后对这 n+1 个扩充维数后的点集进行不等式刻画 (不等式记为 L wt ), 并将 L wt
⌊ log 2 n⌋ +3
,a
,a
添加到 MILP 模型中. 显然 a ⌊ log 2 n⌋ +1 ⌊ log 2 n⌋ +2 ⌊ log 2 n⌋ +3 与 Indicator 约束 z = f → L 中的 f 对应, 而相应的 L 分别选