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 (22^n) of the space.
Researchers at University of the Basque Country and Shanghai University have introduced a codification of the cryptographically relevant constraints in the ground state of an Ising Hamiltonian, allowing them to naturally encode it in a quantum annealer, which seems to provide a quantum speedup.
Additionally, the team has benchmarked small n cases in a D-Wave machine, showing its capacity of devising cryptographic Boolean functions with certain relevant properties. They 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.