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

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

uBlock [12] 和 Saturni [13] 算法的积分区分器, 且均获得了比之前最优积分区分器长一轮的区分器, 具体的代码与实验
结果分别见 https://gitee.com/hm0813/MILP_BDP 与表 1, 其中 C , A , B , U 分别表示 i 个常数比特, 活跃比特, 平衡
i
i
i
i
比特, 以及未知比特. 值得注意的是: 在文献 [13] 中, 作者提出一种完全精确刻画复杂线性层矩阵的可分性传播方
法, 但是该方法受限于约束条件为高次约束, 因此不能直接应用于 MILP 建模, 且该方法限制矩阵的阶数最大为
64 阶, 而本文的方法可以应用于更高阶数的线性层矩阵.

表 1 密码算法的积分区分器

密码算法 轮数 积分区分器 数据复杂度 参考
( ) ( )
4 124
7 C A → B 128 2 124 [14]

( )
( )
2
4 124
8 C A → (BU B) 32 2 124 [15]

uBlock128
( ) ( 2 32 ) 124
4 124
8 C A → (BUB ) 2 第3.1节

( )
( )
3
9 ACA 124 → (U B) 32 2 127 第3.1节

( ) ( )
4 252
8 C A → B 256 2 252 [14]

( ) ( )
32 96 2
8 (C A ) → (U B) 64 2 192 [15]
3

( )
( )
8 248
2
uBlock256 9 C A → (BU B) 64 2 248 [15]

( )
( ) 64 253
10 C A → (U B) 2 第3.1节
3 253
3

( ) ( )
10 ACA 253 → B 256 2 255 第3.1节
8 － 2 253 [16]
Saturnin256 ( ) ( )
20 236
9 C A → B 256 2 236 第3.2节
注: －表示文献[16]仅给出代数次数评估, 未提供具体的积分区分器

1 基础知识
本节将介绍一些常用符号, 比特可分性的相关性质与二元矩阵定义以及 MILP 的 Indicator 约束和建模规则.
1.1 符 号
F 2 表示只含有 0 和 1 F 2 和整数
本节将对文中常用符号进行描述. 两个元素的有限域, ⊕ 和+分别表示有限域
n n
i
环 Z 上的加法, F 表示 F 2 上的 n 维向量空间. 对于任意向量 a ∈ F , 记 a 的第 个的坐标为 a i , 则 a 的汉明重量可
2
2
∑ n−1
n
′
′
′
′
以表示为 wt(a) = a i . 给定任意两个向量 k = (k 0 ,k 1 ,...,k n−1 ), k = (k ,k ,...,k ′ n−1 ) ∈ F , 若对于任意的 i 都有 k i ⩾ k ,
i
2
1
0
i=0
′ ′
则称 k ⩾ k ; 否则, k ⩾̸ k .
n n n
● 比特乘积函数 π u (x) : 给定任意的 u ∈ F , 记 π u (x) 为一个 F → F 2 的函数. 对任意的 x ∈ F 定义 π u (x) 如下:
2 2 2
n ∏
π u (x) = x i .
u i
i=1
● 代数正规型 ANF: 若 f(x) 为一个 F → F 2 上的布尔函数, 则 f(x) 的代数正规型表示为:
n
2
 
n
∏ 
f   u i  f

f(x) = ⊕ a  x i  = ⊕ a (π u (x)),
u∈F n u    u∈F n u
2 2
i=1
f
其中, a u ∈ {0, 1} 表示单项式 π u (x) 的系数, 它的具体取值只与 f 和 u 有关.
1.2 比特可分性的相关性质与二元矩阵定义
比特可分性包括二子集比特可分性和三子集比特可分性. 本文只考虑二子集比特可分性, 因此本文提到的比