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

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

特可分性均表示二子集比特可分性.
定义 1. 比特可分性 [5] . 令 X 是元素在 F 上的多重集, K 是元素在 F 上的集合, u ∈ F . 如果 X 满足如下条件,
n
n
n
2 2 2
1,n
那么称 X 有可分性 D K :
{
未知, 如果存在k ∈ K,使得u ⩾ k;
⊕ π u (x) =
x∈X 0, 其他.
n,m
定义 2. 可分迹 [8] . 记 f r 为一个迭代分组密码的轮函数, 假设算法的输入集合有初始可分性 D , 记可分性经
K 0
n,m
过轮函数 f r 传播 i 轮后的可分性为 D , 则有如下的可分性传播链:
K i
f r f r f r f r
{k} ≜ K 0 →K 1 →K 2 →...→K r ,
∗ ∗ ∗ ∗
并且对任意的 k ∈ K i (i ⩾ 1), 一定存在向量 k i−1 ∈ K i−1 使得 k i−1 可以传播到 k . 进一步地, 对于 (k 0 , k 1 ,..., k r ) ∈ K 0 ×K 1 ×...
i
i
(k 0 , k 1 ,..., k r ) 为一条 r 轮的可分迹.

×K r , 如果对于任意的 i ∈ {1,2,...,r}, k i−1 都可以传播到那么就称
定义 3. 二元矩阵 [13] . 对矩阵 M = (m ) s×s ∈ F m , 我们将其内部元素 m ′ i,j 表示成一个扩域 F 2 m ≃ F[x]/(g(x)) 上的
s×s
′
′
i,j
2
M 中的元素均为 0 或者 M 为一个二元矩
′
′
一个多项式, 其中 g 是 F 2 上的一个 m 次不可约多项式, 如果矩阵 1, 则称
′
阵. 否则, M 为一个非二元矩阵.
1.3 MILP 的 Indicator 约束与可分性的建模规则
MILP 模型是一种在线性约束条件下求解线性目标函数的数学问题, 该模型 M 通常包含目标函数 (记为 M.obj ),
约束条件 (记为 M.con ) 和变量的取值范围 (记为 M.var ). 例如, 公式 (1) 给出了一个简单的 MILP 模型.

M.obj ← min{x 1 +2x 2 + x 3 }



M.con ← x 1 + x 2 + x 3 ⩾ 2



(1)
M = 

 M.con ← x 1 + x 2 ⩽ 1





M.var ← x 1 , x 2 , x 3 ∈ {0, 1}
当求解 M 的目标函数 x 1 +2x 2 + x 3 的最小值时, 变量 x 1 , x 2 , x 3 ∈ {0, 1} 需要同时满足约束条件 x 1 + x 2 + x 3 ⩾ 2
x 1 + x 2 ⩽ 1, 即上述变量的取值范围为所有约束条件的交集. 对于上述一般的 MILP 模型, 其变量需要满足所有
和
的约束条件. 为了提高 MILP 模型的实用性, MILP 求解器一般内置了各种广义约束的添加方法, 例如 Indicator 约
束. 相比于一般的 MILP 模型, 使用 Indicator 约束的 MILP 模型可以根据不同的初始条件设置不同的约束条件, 约
′ f ∈ {0,1}. 例如, 公式 (2) 给出了使用 Indicator 约束的
束条件的形式为 M .con ← z = f → L, 其中 MILP 模型.
 ′
M .obj ← min{x 1 +2x 2 + x 3 }



′

M .con ← x 3 = 1 → x 1 + x 2 + x 3 ⩾ 2

′  (2)
M = 

 M .con ← x 3 = 0 → x 1 + x 2 ⩽ 1
′




 ′
M .var ← x 1 , x 2 , x 3 ∈ {0, 1}
′ x 3 = 0 时, 变量
模型 M 中的约束条件表示当 x 3 = 1 时, 变量 x 1 , x 2 , x 3 需要满足约束条件 x 1 + x 2 + x 3 ⩾ 2, 而
x 1 , x 2 , x 3 则可以违反约束条件 x 1 + x 2 + x 3 ⩾ 2, 但需要满足约束条件 x 1 + x 2 ⩽ 1. 关于 Indicator 约束的详细内容请
参考文献 [17].
本文利用 Indicator 约束构建 MILP 模型的过程中, 主要涉及以下 3 个建模规则, 更多建模规则请参考文献 [9,10].
复制
模型 1. 复制 [9] . 记 a → (b 0 ,b 1 ,...,b l−1 ) 表示将比特变量 a 复制为 个比特变量 b 0 ,b 1 ,...,b l−1 , 下面的线性约束
l
可描述复制操作的可分性传播.
{
a−b 0 −b 1 −...−b l−1 = 0
.
a,b 0 ,b 1 ,...,b l−1 ∈ {0,1}
异或
模型 2. 异或 [9] . 记 (a 0 ,a 1 ,...,a l−1 ) → b 表示将 个比特变量 a 0 ,a 1 ,...,a l−1 异或为比特变量 b, 下面的线性约束
l
可描述异或操作的可分性传播.
{
a 0 +a 1 +...+a l−1 −b = 0
.
a 0 ,a 1 ,...,a l−1 ,b ∈ {0,1}