Finding cryptographic Boolean functions with D-wave quantum annealer

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.

Read more.