A quantum algorithm to approximate the linear structures of Boolean functions

Abstract

We present a quantum algorithm for approximating the linear structures of a Boolean function $f$. Different from previous algorithms (such as Simon's and Shor's algorithms) which rely on restrictions on the Boolean function, our algorithm applies to every Boolean function with no promise. Here, our methods are based on the result of the Bernstein-Vazirani algorithm which is to identify linear Boolean functions and the idea of Simon's period-finding algorithm. More precisely, how the extent of approximation changes over the time is obtained, and meanwhile we also get some quasi linear structures if there exists. Next, we obtain that the running time of the quantum algorithm to thoroughly determine this question is related to the relative differential uniformity ${\delta }_f$ of $f$. Roughly speaking, the smaller the ${\delta }_f$ is, the less time will be needed.

16 pages

References in corpus (2)

• Quantum tests for the linearity and permutation invariance of Boolean functions
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance

Cited by in corpus (6)

• Quantum impossible differential and truncated differential cryptanalysis
• A quantum related-key attack based on Bernstein-Vazirani algorithm
• A quantum algorithm for approximating the influences of Boolean functions and its applications
• A Fast Quantum Algorithm for the Affine Boolean Function Identification
• Using Bernstein-Vazirani Algorithm to Attack Block Ciphers
• Quantum differential cryptanalysis to the block ciphers