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 consistsof assmall number of binary variables aspossible. According to our calculations, the use of quantum annealing to an algebraic attack on the Simon128 / 128 cipher, since the QUBO problem consists of 27, 270 binary variables, is more effective than the same attack on the AES128 cipher, for which the QUBO problem includes 29, 770 binary variables.
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 consistsof assmall number of binary variables aspossible. According to our calculations, the use of quantum annealing to an algebraic attack on the Simon128 / 128 cipher, since the QUBO problem consists of 27, 270 binary variables, is more effective than the same attack on the AES128 cipher, for which the QUBO problem includes 29, 770 binary variables.
This paper presents the transformation method of the system of algebraic equations describing the symmetric cipher into the QUBO problem. After transformation of given equationsf0,f1,…,fn−1f0,f1,...,fn-1to equations over integersf0′,f1′,…,fn−1′f0',f1',...,fn-1', one can linearize each, obtainingflini′=lin(fi′)flini'=lin(fi'), fori=0,n−1i=0,n-1¯, wherelinlindenotes linearization operation. Finally, one can obtain problem in the QUBO form as(flin0′)2+⋯+(flinn−1′)2+Pen−C(flin0')2+⋯+(flinn-1')2+Pen-C, wherePenPendenotes penalties obtained during linearization of equations,nnis the number of equations andCCis constant appearing in the polynomial(flin0′)2+⋯+(flinn−1′)2+Pen(flin0')2+⋯+(flinn-1')2+Pen. This paper presents the transformation method of SPN block ciphers to the QUBO problem. What is more, we present the results of the transformation of the complete AES-128 cipher to the QUBO problem, where the number of variables of the equivalent QUBO problem equals approximately 30,026. It is worth noting that AES-128 is much easier to solve using quantum annealing than the factorization problem and the discrete logarithm problem of a similar level of security. For example, factorizing a 3072 bit long RSA integer using quantum annealing requires a QUBO problem of about 2,360,000 variables.
This paper presents a new method to reduce the optimization of a pseudo-Boolean function to QUBO problem which can be solved by quantum annealer. The new method has two aspects, one is coefficient optimization and the other is variable optimization. The former is an improvement on the existing algorithm in a special case. The latter is realized by means of the maximal independent point set in graph theory. We apply this new method in integer factorization on quantum annealers and achieve the largest integer factorization (4137131) with 93 variables, the range of coefficients is [-1024,1024] which is much smaller than the previous results. We also focus on the quantum attacks on block ciphers and present an efficient method with smaller coefficients to transform Boolean equation systems into QUBO problems.
Polynomial systems over the binary field have important applications, especially in symmetric and asymmetric cryptanalysis, multivariate-based postquantum cryptography, coding theory, and computer algebra. In this paper, we study the quantum annealing model for solving Boolean systems of multivariate equations of degree 2, usually referred to as the multivariate quadratic problem. We present different methodologies to embed the problem into a Hamiltonian that can be solved by available quantum annealing platforms. In particular, we provide three embedding options, and we highlight their differences in terms of quantum resources. Moreover, we design a machine-agnostic algorithm that adopts an iterative approach to better solve the problem Hamiltonian by repeatedly reducing the search space. Finally, we use D-Wave devices to successfully implement our methodologies on several instances of the multivariate quadratic problem.
Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system FS has a solution and compute one if FS does have solutions with any given success probability. The runtime complexity of the algorithm is polynomial in the size of FS and the condition number of FS. As a consequence, we give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are small, say polynomial in the size of FS. We apply our quantum algorithm for solving Boolean equations to the cryptanalysis of several important cryptosystems: the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large. This leads to a new criterion for designing cryptosystems that can against the attack of quantum computers: their corresponding equation systems must have large condition numbers.
The security level of a cipher is a key parameter. While general-purpose quantum computers significantly threaten modern symmetric ciphers, other quantum approaches like quantum annealing have been less concerning. However, this paper argues that a quantum annealer specifically designed to attack Grain 128 and Grain 128a ciphers could soon be technologically feasible. Such an annealer would require 5,751 (6,761) qubits and 77,496 (94,865) couplers, with a qubit connectivity of 225 (245). This work also shows that modern stream ciphers like Grain 128 and Grain 128a may be vulnerable to quantum annealing attacks. Although the exact complexity of quantum annealing is unknown, heuristic estimates suggest that for many problems withNvariables, aNexponential advantage over simulated annealing may hold. We detail how to transform algebraic attacks on Grain ciphers into the QUBO problem, making our attack potentially more efficient than classical brute-force methods. We demonstrate that applying our attack to rescaled Grain cipher versions, Grainland Grainla, overtakes brute-force and Grover’s attacks for sufficiently largel, assuming quantum annealing’s exponential benefit over simulated annealing.
Obtaining Quadratic Unconstrained Binary Optimisation models for various optimisation problems, in order to solve those on physical quantum computers (such as the the DWave annealers) is nowadays a lengthy and tedious process that requires one to remodel all problem variables as binary variables and squeeze the target function and the constraints into a single quadratic polynomial into these new variables. We report here on the basis of our automatic converter from MiniZinc to QUBO, which is able to process a large set of constraint optimisation and constraint satisfaction problems and turn them into equivalent QUBOs, effectively optimising the whole process.