A quantum related-key attack based on Bernstein-Vazirani algorithm
This work addresses cryptographic security for block ciphers against quantum adversaries, providing guidance for design, but it is incremental as it builds on existing quantum algorithms.
The paper tackles the problem of related-key attacks on block ciphers in a quantum setting by proposing an attack that uses the Bernstein-Vazirani algorithm to efficiently recover keys under certain conditions, demonstrating its validity and analyzing complexity.
Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting, and proposed a specific related-key attack which can recover the key of block ciphers efficiently, as long as the attacked block ciphers satisfy certain conditions. The attack algorithm employs Bernstein-Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. Afterwards, we rigorously demonstrate the validity of the attack and analyze its complexity. Our work shows that related-key attack is quite powerful when combined with quantum algorithms, and provides some guidance for the design of block ciphers that are secure against quantum adversaries.