Improved BV-based quantum attack on block ciphers

作     者：Sun, Hong-Wei Wei, Chun-Yan Cai, Bin-Bin Qin, Su-Juan Wen, Qiao-Yan Gao, Fei 

作者机构：Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China Henan Key Lab Network Cryptog Technol Zhengzhou 450001 Henan Peoples R China Luoyang Normal Univ Sch Math Sci Luoyang 471934 Peoples R China 

出 版 物：《QUANTUM INFORMATION PROCESSING》 (量子信息处理)

年 卷 期：2022年第22卷第1期

页      面：1-22页

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 

基　　金：National Natural Science Foundation of China Henan Key Laboratory of Network Cryptography Technology Natural Science Foundation of Henan 61972048 61976024 61902166 LNCT2021-A10 212300410062 

主　　题：Quantum cryptanalysis Quantum superposition attacks Related-key attack Block ciphers 

摘      要：Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results. Finding the linear structure of a vector function is an important task in cryptography. In this work, we study how to reduce the complexity of finding linear structure using the Bernstein-Vazirani (BV) algorithm and give a new quantum linear structure finding algorithm with complexity O(n). Our result realizes a quadratic speedup compared with the previous algorithm (with complexity O(n(2))). This leads to a more efficient analysis of symmetric cryptography, that is, the complexity of some previous BV-based attacks reduces from O(n(2)) to O(n). Besides, we find two new applications for this kind of BV-based attack, i.e., related-key attacks on iterated Even-Mansour ciphers and i-round Feistel ciphers with independent round keys.