2021/04/25 by Suman Dutta, Subhamoy Maitra, Dutta, Suman +3 · 3 citations
Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2104.12212
openalex publication_date 2021/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Here we revisit the quantum algorithms for obtaining Forrelation [Aaronson et al, 2015] values to evaluate some of the well-known cryptographically significant spectra of Boolean functions, namely the Walsh spectrum, the cross-correlation spectrum and the autocorrelation spectrum. We introduce the existing 2-fold Forrelation formulation with bent duality based promise problems as desirable instantiations. Next we concentrate on the 3-fold version through two approaches. First, we judiciously set-up some of the functions in 3-fold Forrelation, so that given an oracle access, one can sample from the Walsh Spectrum of f. Using this, we obtain improved results than what we obtain from the Deutsch-Jozsa algorithm, and in turn it has implications in resiliency checking. Furthermore, we use similar idea to obtain a technique in estimating the cross-correlation (and thus autocorrelation) value at any point, improving upon the existing algorithms. Finally, we tweak the quantum algorithm with superposition of linear functions to obtain a cross-correlation sampling technique. To the best of our knowledge, this is the first cross-correlation sampling algorithm with constant query complexity. This also provides a strategy to check if two functions are uncorrelated of degree m. We further modify this using Dicke states so that the time complexity reduces, particularly for constant values of m.