LAUSR

In classical cryptography, many cryptographic primitives could be treated as multi-output Boolean functions. The analysis of such functions is of great interest for cryptologists owing to their wide ranges of applications. Since each multi-output Boolean function can be uniquely determined by its Walsh transform, the Walsh spectra could reveal the properties of multi-output Boolean functions. In this paper, several quantum algorithms for learning Walsh spectra of multi-output Boolean functions are proposed. Firstly, with the usage of the amplitude estimation algorithm based on the Monte Carlo method, we present a quantum algorithm that allows one to estimate the Walsh coefficient of a multi-output Boolean function at a specified point with an additive error $$\epsilon $$ϵ and probability at least $$1-\delta $$1-δ. The corresponding query complexity is $${\mathrm O}( {{\epsilon }^{-1}}\log {{\delta }^{-1}} )$$O(ϵ-1logδ-1). There is an almost quadratic speedup over the classical algorithm. Secondly, we propose a generalized phase kick-back technique for multi-output Boolean functions to encode multiple Walsh coefficients on the amplitudes of states. Based on this generalized technique, a quantum Goldreich–Levin algorithm for arbitrary multi-output Boolean function $$F:{{\{ 0,1 \}}^{n}}\rightarrow {{\{ 0,1 \}}^{m}}$$F:{0,1}n→{0,1}m where $$m,n\in \mathbb {Z}$$m,n∈Z is proposed to find those Walsh coefficients satisfying the threshold boundary condition $$\tau $$τ with probability at least $$1-\delta $$1-δ. The whole query complexity is $${\mathrm O}\left( \frac{{{2}^{m+5+n/2}}}{{{\tau }^{3}}}\log \frac{{{2}^{m+5}}n}{\delta {{\tau }^{2}}} \right) $$O2m+5+n/2τ3log2m+5nδτ2. Finally, by using the same idea of the swap-test circuit, the query complexity of the modified quantum Goldreich–Levin algorithm could be lowered to $${\mathrm O}\left( \frac{{{2}^{m+9}}n\pi }{{{\tau }^{4}}}\log \frac{{{2}^{m+3}}n}{\delta {{\tau }^{2}}} \right) $$O2m+9nπτ4log2m+3nδτ2 achieving a further speedup when $$\tau $$τ is no less than $${\mathrm O}( {{2}^{-n/2+6}}n)$$O(2-n/2+6n). Those two quantum Goldreich–Levin algorithms have their own advantages in implementation and query complexity.