Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
- PDF / 443,282 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 169 Views
Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions Xuexuan Hao1,2,3 · Fengrong Zhang1,2,3 · Shixiong Xia1,3 · Yong Zhou1,3 Received: 25 December 2019 / Accepted: 17 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Quantum algorithms for the analysis of Boolean functions have received a lot of attention over the last few years. The algebraic normal form (ANF) of a linear Boolean function can be recovered by using the Bernstein–Vazirani (BV) algorithm. No research has been carried out on quantum algorithms for learning the ANF of general Boolean functions. In this paper, quantum algorithms for learning the ANF of quadratic Boolean functions are studied. We draw a conclusion about the influences of variables on quadratic functions, so that the BV algorithm can be run on them. We study the functions obtained by inversion and zero-setting of some variables in the quadratic function and show the construction of their quantum oracle. We introduce the concept of “club” to group variables that appear in quadratic terms and study the properties of clubs. Furthermore, we propose a bunch of algorithms for learning the full ANF of quadratic Boolean functions. The most efficient algorithm, among those we propose, provides an O(n) speedup over the classical one, and the number of queries is independent of the degenerate variables. Keywords Bernstein–Vazirani algorithm · Boolean function · Quantum cryptanalysis · Quantum computation
B
Fengrong Zhang [email protected]
1
School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, People’s Republic of China
2
Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, People’s Republic of China
3
Mine Digitization Engineering Research Center of Ministry of Education, China University of Mining and Technology, Xuzhou 221116, People’s Republic of China 0123456789().: V,-vol
123
273
Page 2 of 22
X. Hao et al..
1 Introduction Lately, Google claimed that it has attained quantum supremacy [1], that is, its quantum computer performed a calculation that would be practically impossible for even the best supercomputer. This has greatly raised concerns about quantum computation. Traditional cryptography has been threatened by the excellent power of quantum computation, not only asymmetric cryptography, but also symmetric cryptography. As is well known, Shor’s algorithm [2] could break many public-key cryptographic schemes (e.g., RSA and ECC) in polynomial time. In the past few years, some quantum algorithms applied to symmetric cryptanalysis have been studied, such as Grover’s algorithm [3], Simon’s algorithm [4] and the Bernstein–Vazirani (BV) algorithm [5]. Construction and analysis of Boolean functions play an important role in symmetric cryptography. As is well known, Boolean functions with low nonlinearity are vulnerable to linear approximation attacks [6]. On top of this, quadratic approximation h
Data Loading...
