Cryptographic Applications of Forrelation-based Quantum Algorithms

Examining Results Related to Boolean Functions
Erscheinungsjahr 2026
ISBN: 978-3-032-39590-0
Verlag: Springer International Publishing

Buch, Englisch, 93 Seiten, Format (B × H): 155 mm x 235 mm

Reihe: SpringerBriefs in Information Security and Cryptography

This book provides a research-level treatment of quantum algorithms for analyzing Boolean functions through the framework of Forrelation. It develops a unified account of how Forrelation, nega-Forrelation, and generalized Forrelation can be used to study major Boolean-function spectra, including Walsh-Hadamard, nega-Hadamard, crosscorrelation, and autocorrelation spectra, along with related questions on bent, negabent, and their hidden-shift structures. The central aim is to connect modern quantum query complexity related techniques with spectral problems that are fundamental in cryptography, coding theory, and the combinatorial theory of Boolean functions.

The book begins with the necessary background on Boolean functions and basics of quantum computing, making the later chapters substantially self-contained. It then develops three main contributions. First, it studies Forrelation as a tool for sampling and estimating Walsh-Hadamard, crosscorrelation, and autocorrelation spectra, including applications to resiliency testing and bounded-degree uncorrelatedness checking. Next, it introduces nega-Forrelation and uses it to design quantum algorithms for estimating nega-Hadamard, nega-crosscorrelation, and nega-autocorrelation spectra, while linking these methods to hidden-shift problems involving bent and negabent functions. Finally, it presents a generalized framework based on roots of unity, extending prior transform-based methods and introducing generalized Deutsch-Jozsa and generalized Forrelation algorithms.

The topic is timely because Forrelation is one of the landmark problems establishing a separation between the probabilistic classical and bounded-error quantum models, and the spectral analysis of Boolean functions remains central to the design and evaluation of cryptographic primitives. By bringing these strands together, the book offers both new algorithmic perspectives and a coherent mathematical framework for spectral analysis in the quantum setting. The primary audience of this book comprises researchers, advanced graduate students, and specialists in cryptography, discrete mathematics, and quantum computation.

Zielgruppe

Research

Autoren/Hrsg.

Dutta, Suman

Maitra, Subhamoy

Mukherjee, Chandra Sekhar

Stanica, Pantelimon

Inhaltsverzeichnis

.- Introduction.
.- Background.
.- Quantum algorithms following Forrelation.
.- Nega-Forrelation & related quantum algorithms.
.- Generalized Forrelation.
.- Concluding perspectives.

Über Autor(innen)

The authors bring complementary expertise in Boolean functions, cryptography, combinatorics, complexity theory, and quantum algorithms. Suman Dutta is a Visiting Assistant Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology, Dharwad. He has earned his doctorate from the Indian Statistical Institute, Kolkata. He has worked on quantum algorithms related to Boolean function spectra and Forrelation. Subhamoy Maitra is a Senior Professor (HAG), the Head of the Applied Statistics Unit, and the acting Head of the R. C. Bose Centre for Cryptology & Security at the Indian Statistical Institute, Kolkata. He is widely known for his contributions to cryptology, Boolean functions, and related areas. Chandra Sekhar Mukherjee is a post-doctoral fellow at the Fred Hutchinson Cancer Center, Seattle, USA. He obtained his doctorate from the University of Southern California, USA, and has published research articles on Boolean functions, query complexity, learning theory, and quantum computing. Pantelimon Stanica is a Professor in the Applied Mathematics Department at the Naval Postgraduate School, USA, where his work spans cryptography, coding theory, Boolean functions, combinatorics, and discrete mathematics. He is a recipient of the 2021 George Boole International Prize for his contributions to the theory of Boolean functions. Together, the authors have an established research record in Boolean functions and their applications to cryptography and quantum information. The present book emerges from their sustained collaboration and the development of these themes into a unified research monograph.