Quantum claw-finding attacks on 5-round Feistel structure and generalized Feistel schemes

期刊论文
发表日期：

2025年2月7日

查看全文

Xiaoning Feng,
Hongyu Wu,
Kejia Zhang,
Hongwei Sun

摘要

Feistel structure is a fundamental symmetric cryptographic primitive. In this paper, we investigate the security of 5-round Feistel structure and generalized Feistel scheme (GFS) in a quantum environment and propose a family of quantum claw-finding attacks in both Q1 and Q2 models. The quantum attack uses claw-finding algorithm with the period function’s approximate promise. By employing the constructed functions g and h as inputs for claw-finding algorithm, secret information can be extracted. The attack on 5-round Feistel structure in Q1 model, which is easier to implement than Q2 model, enriched the diversity of the attack scenarios. The attacks on 5-round Feistel structure, Type-I, Type-II, and Type-III GFS in Q2 model, exhibit an exponentially lower product indicator for quantum and classical query complexity. The strongest reduction occurs in attacks on Type-I and Type-II GFS, decreasing from $2^{4n}$ $2^{4 n}$ to $2^{2n}$ $2^{2 n}$ .