Converting of Simon cipher multivariate polynomial equations to QUBO problem

Abstract

The use of quantum annealing in the cryptanalysis of symmetric cryptography is a new idea based on the concept of algebraic attacks. This paper shows how to describe the Simon cipher as a system of multivariate polynomial equations so that the obtained optimization problem in the form of QUBO consists of as small number of binary variables as possible.
According to our calculations, the use of quantum annealing to an algebraic attack on the Simon$128/128$ cipher, since the QUBO problem consists of $27,270$ binary variables, is more effective than the same attack on the AES$128$ cipher, for which the QUBO problem includes $29,770$ binary variables.