Quantum computing cryptography: Finding cryptographic Boolean functions with quantum annealing by a 2000 qubit D-wave quantum computer
This addresses the challenge of super-exponential search spaces in cryptography for secure communication systems, though it appears incremental as it builds on existing quantum annealing methods.
The authors tackled the computationally hard problem of designing cryptographic Boolean functions by encoding constraints into an Ising Hamiltonian for quantum annealing, demonstrating the capacity to devise bent functions using a D-Wave machine with local search improvements.
As the building block in symmetric cryptography, designing Boolean functions satisfying multiple properties is an important problem in sequence ciphers, block ciphers, and hash functions. However, the search of $n$-variable Boolean functions fulfilling global cryptographic constraints is computationally hard due to the super-exponential size $\mathcal{O}(2^{2^n})$ of the space. Here, we introduce a codification of the cryptographically relevant constraints in the ground state of an Ising Hamiltonian, allowing us to naturally encode it in a quantum annealer, which seems to provide a quantum speedup. Additionally, we benchmark small $n$ cases in a D-Wave machine, showing its capacity of devising bent functions, the most relevant set of cryptographic Boolean functions. We have complemented it with local search and chain repair to improve the D-Wave quantum annealer performance related to the low connectivity. This work shows how to codify super-exponential cryptographic problems into quantum annealers and paves the way for reaching quantum supremacy with an adequately designed chip.