Page 392 - 《软件学报》2026年第5期

杜小妮 等: 三类非平衡广义 Feistel 结构的量子中间相遇攻击 2271

ℓ
(1) 显然, 数据复杂度为 O(2 ) 个选择密文.
′ ℓ ℓ/ 2 ℓ ℓ 3ℓ/ 2 ·ℓ) 次量子查
(2) 由于构造表 T 和运行爪搜索算法 (l = 2 ) 的时间复杂度分别为 O(2 +2 ) ≈ O(2 ) 和 O(2
9
询. 因此, 总的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询.
′ ℓ 2ℓ ℓ 2ℓ
(3) 构造表 T 和运行爪搜索算法筛选密钥 (l = 2 ) 需要 O(2 ·ℓ +2 ·ℓ) ≈ O(2 ·ℓ) 个量子比特.
9
4.2 n-cell 型 GFS 的 DS-MITM 攻击和量子 DS-MITM 攻击
本节将第 4.1 节的相关结论推广至 n-cell 型 GFS. 具体地, 在预计算阶段分别固定输入和输出差分 (∆x,0 ℓ ,
ℓ
,
0 ℓ ,0 ℓ ,...,0 ℓ ) 和 (∆z,0 ℓ ,∆z,0 ℓ ,...,0 ℓ ) ∆x, ∆z ∈ F , 与命题 2 类似, 可得到一类 2n 轮中间相遇区分器, 对其分别向前向
2
后扩展 1 轮进行 2(n+1) 轮 DS-MITM 攻击, 并在 Q1 模型下对该结构进行 2(n+1) 轮量子 DS-MITM 攻击. 分析过
程与第 4.1 节一致, 故不再详细叙述, 仅给出复杂度分析.
n-cell 型 GFS 的 2(n+1) 轮 DS-MITM 攻击的复杂度:
ℓ
(1) 数据复杂度为 O(2 ) 个选择明文.
2ℓ
(2) 由于预计算阶段构造的存储 ∆-序列 的表 T 13 和在线阶段猜测密钥所需的时间复杂度均为 O(2 ) 次 2(n+1)
2ℓ
轮加密, 因此, 攻击所需的时间复杂度为 O(2 ) 次 2(n+1) 轮加密.
2ℓ b T 14 存储在线阶段得到
(3) 存储表 T 13 和 T 14 所需的存储复杂度为 O(2 ) 个长度为 (2 −1)ℓ 的比特块, 其中, 表
∆-序列.
的
n-cell 型 GFS 的 2(n+1) 轮量子 DS-MITM 攻击的复杂度:
ℓ
O(2 ) 个选择明文.
(1) 数据复杂度为
ℓ
ℓ
ℓ
(2) 由于构造表 T ′ 和运行爪搜索算法 (l = 2 ) 的时间复杂度分别为 O(2 ℓ/ 2 +2 ) ≈ O(2 ) 和 O(2 3ℓ/ 2 ·ℓ) 次量子查
13
询, 因此, 该攻击所需要的总的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询.
2ℓ
ℓ
2ℓ
(3) 构造表 T ′ 和运行爪搜索算法筛选密钥 (l = 2 ) 需要 O(2 ·ℓ +2 3ℓ/ 2 ·ℓ) ≈ O(2 ·ℓ) 个量子比特.
13
5 总 结
本文研究了 3 类 GFS 的 DS-MITM 攻击, 并在 Q1 模型下对 3 类 GFS 进行了量子 DS-MITM 攻击. 首先, 针
对 3 分支 Type-III 型 GFS, 采用多重集和差分枚举技术构造了 4 轮中间相遇区分器, 并利用 Grover 算法和量子爪
搜索算法对其进行了 6 轮量子 DS-MITM 攻击, 攻击的时间复杂度为 O(2 3ℓ/ 2 ·ℓ) 次量子查询. 其次, 对 3 分支 Type-I
型 GFS 的 9 轮中间相遇区分器分别进行了 11 轮 DS-MITM 攻击和量子 DS-MITM 攻击, 相应的时间复杂度分别
O(2 ) 次 11 3ℓ/ 2 ·ℓ) 次量子查询. 最后, 对 n-cell 型 GFS 2(n+1) 轮 DS-MITM 攻击和量子
2ℓ
为 轮加密和 O(2 进行了
2ℓ
DS-MITM 攻击, 且攻击所需要的时间复杂度分别为 O(2 ) 次 2(n+1) 轮加密和 O(2 3ℓ/ 2 ·ℓ) 次量子查询. 结果表明,
本文提出的量子 DS-MITM 攻击有效降低了经典 DS-MITM 攻击的复杂度. 然而遗憾的是, 本文的方法在应用于
n 分支 Type-I/III 型 GFS 时仍有局限性, 未来我们希望通过借助其他工具分析其 DS-MITM 攻击效果, 并通过量子
算法更好地降低时间复杂度.

References
[1] Feistel H. Cryptography and computer privacy. Scientific American, 1973, 228(5): 15–23. [doi: 10.1038/scientificamerican0573-15]
[2] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 1991, 4(1): 3–72. [doi: 10.1007/
BF00630563]
[3] Zheng YL, Matsumoto T, Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In:
Brassard G, ed. Advances in Cryptology—CRYPTO 1989. New York: Springer, 1990. 461–480. [doi: 10.1007/0-387-34805-0_42]
[4] Choy J, Chew G, Khoo K, Yap H. Cryptographic properties and application of a generalized unbalanced Feistel network structure. In:
Boyd C, González Nieto J, eds. Proc. of the 14th Australasian Conf. on Information Security and Privacy. Brisbane: Springer, 2009.
73–89. [doi: 10.1007/978-3-642-02620-1_6]
[5] Diffie W, Hellman ME. Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer, 1977, 10(6): 74–84.
[doi: 10.1109/C-M.1977.217750]