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

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


 2 ℓ −1 2 ℓ −1 2 ℓ −1
 ∑ 1 ∑ ⟩ Grover ∑ 1
 ⟩

 √ |∆y⟩|∆x⟩ t 1,1 −−−−→ √
 |∆y⟩|∆x⟩t 1,1

 ℓ ℓ
 2 2
 ∆y=0 t 1,1 =0 ∆y=0





 2 ℓ −1 2 ℓ −1 2 ℓ −1 ∆z,∆y=2 ℓ −1
∑ 1 ∑ 1 ∑ ∑ 1
 ⟩ Grover ⟩


 √ |∆z⟩ √ |∆y⟩ t 2,1 −−−−→ √
 |∆z⟩|∆y⟩t 2,1

 ℓ ℓ 2ℓ
 2 2 2
 ∆z=0 ∆y=0 t 2,1 =0 ∆z,∆y=0
,



 2 ℓ −1 2 ℓ −1 2 ℓ −1
∑ 1 ∑ ∑ 1
 ⟩ Grover ⟩


 √ |∆z⟩|∆x⟩ t 3,1 −−−−→ √ |∆z⟩|∆x⟩t 3,1

 ℓ ℓ
 2 2

 ∆z=0 t 3,1 =0 ∆z=0




 2 ℓ −1 2 ℓ −1 2 ℓ −1
 ∑ ∑ ∑
 1 1
 ⟩ Grover ⟩

 √ |∆y⟩|∆x⟩ t 3,2 −−−−→ √
 |∆y⟩|∆x⟩t 3,2

 ℓ ℓ
 2 2
∆y=0 t 3,2 =0 ∆y=0
从而得到叠加态:

∆z,∆y=2 ℓ −1
∑ 1 ⟩ ⟩ ⟩ ⟩
|φ 2 ⟩ = √ |∆z⟩|∆y⟩|∆x⟩t 1,1 t 2,1 t 3,1 t 3,2 .

2 2ℓ
∆z,∆y=0
2 b −1 |r⟩ 作为输入, 根据定理 1 ∆-序列 Γ 1 , 制备叠加态:

(1.3) 将 ⊗ 中的 b-δ-集 M 计算
r=0
∆z,∆y=2 ℓ −1
∑ 1
|φ 3 ⟩ = √ |∆z⟩|∆y⟩|∆x⟩|Γ 1 ⟩,
2 2ℓ
∆z,∆y=0
b
并将其存储在量子寄存器的 O(ℓ ·2 ) 个比特中.
(1.4) 基于 Grover 算法, 对 |φ 3 ⟩ 使用 2 2ℓ 个并行的单量子处理器进行搜索, 以获得 (∆z,∆y) 对应的所有可能的
′
|Γ 1 ⟩, 并将其存储在以 (∆z,∆y) 为索引的表 T 中.
1
2) 在线阶段. 在经典环境中, 确定第 3.2 节步骤 (2.2) 的 ∆-序列 Γ 2 需要使用 O(2 ) 经典内存进行 O(2 ) 次计
2ℓ
2ℓ

算, 而在量子环境下可使用以下步骤降低时间复杂度.
⊗2ℓ
(2.1) 将 2ℓ 个量子比特初始化为 |0⟩ , 并制备叠加态:

1
∑
|ψ 1 ⟩ = √ |I 1 ⟩|I 2 ⟩,
2 2ℓ
I 1 ∈T P ,I 2 ∈T C
|I 1 ⟩ 和 |I 2 ⟩ 分别表示第 3.2 节步骤 (1.1) 和 2 2ℓ 组明密文对, 并
其中, 长度均为 6ℓ 个量子比特的叠加态 (1.2) 所得的
将其存储在表 T PC 中, 以 (I 1 ,I 2 ) 为索引.
|ψ 1 ⟩ 作为地址, 使用 qRAM |ψ 2 ⟩, 即:
(2.2) 将 从表 T PC 中查询一组明密文对 (P 0 ,C 0 ) 和 (P,C), 得到
U qRAM
|ψ 1 ⟩|T PC ⟩|0 6ℓ ⟩|0 6ℓ ⟩ −−−−→ |ψ 1 ⟩|T PC ⟩|P 0 ,C 0 ⟩|P,C⟩ = |ψ 2 ⟩.
{P 0 ,P 1 ,...,P 2 b −1 }, 得到叠加态:

(2.3) 计算 b-δ-集 M 对应的明文集

|ψ 3 ⟩ = |ψ 2 ⟩|P 0 ,P 1 ,...,P 2 b −1 ⟩.
|ψ 3 ⟩ 作为地址, 使用 qRAM 查询明文集得到对应的密文集, 可得:
(2.4) 将

|ψ 4 ⟩ = |ψ 3 ⟩|C 0 ,C 1 ,...,C 2 b −1 ⟩.
r ∈ [2 −1], 依次执行以下 3 个步骤.
b
(2.5) 对每个
′ ′
(2.5.1) 选取一组明密文对 (P 0 ,C 0 ) 和 (P r ,C r ), 计算相应的差分 (∆x,∆x ) 和 (∆z,∆z ), 得到叠加态:

|ψ 5 ⟩ = |ψ 4 ⟩|∆x,∆x ⟩|∆z,∆z ⟩.
′
′
,
(2.5.2) 对叠加态 |ψ 5 ⟩ 使用 Grover 算法搜索 t 0,2 t 5,1 和 t 5,2 , 即:

2 ℓ −1 2 ℓ −1 2 ℓ −1
∑ ∑ ∑
⟩ ⟩ ⟩ Grover ⟩ ⟩ ⟩

|ψ 5 ⟩ t 0,2 t 5,2 t 5,1 −−−−→ |ψ 5 ⟩t 0,2 t 5,1 t 5,2 ,
t 0,2 =0 t 5,2 =0 t 5,1 =0
从而获得叠加态:

⟩ ⟩ ⟩
|ψ 6 ⟩ = |ψ 5 ⟩t 0,2 t 5,1 t 5,2 .

,
(2.5.3) 猜测子密钥 k 0,2 k 5,1 和 k 5,2 , 得到叠加态: