New Search Tool Shrinks the Algebraic Equations Behind Cipher S-boxes for Quantum Attacks

Every modern block cipher hides its strength inside a substitution box, the small lookup table that scrambles chunks of data and supplies the nonlinearity that keeps encrypted messages safe from algebraic assault. A new open-source software package called SBoxQUBOSearch, described by Elżbieta Burek and Michał Misztal of the Military University of Technology in the journal SoftwareX, now automates the hunt for the most compact sets of algebraic equations that describe these tables exactly. The tool arrives at a moment when researchers are increasingly trying to translate cryptanalytic problems into formats that quantum annealers such as D-Wave machines can digest, and the size of those translations often decides whether an attack is even worth attempting.

An S-box is a function that maps an n-bit input to an m-bit output, and in ciphers like the Advanced Encryption Standard it is the primary source of nonlinearity. When analysts model a cipher algebraically, the equations describing the S-box are replicated for every occurrence of the box inside the cipher, so the number and structure of those equations directly shape the size of the full model. The simplest description writes out explicit algebraic normal form equations for each output bit, but that is not always the most efficient formulation. Instead, the researchers work in the Boolean ring, where a relation holds for a given S-box if it evaluates to zero at every valid input-output pair, and a system of relations uniquely describes the box only if it both accepts all valid pairs and rejects every incorrect output.

Why does this matter for quantum computing? Formulating cryptanalytic problems as quadratic unconstrained binary optimization, or QUBO, remains an active research direction tied to quantum annealing. The computational cost of solving QUBO or Ising problems depends heavily on the number of variables involved. Each quadratic monomial in an equation system must be replaced by a shared auxiliary variable during linearization, and each parity condition needs binary-encoded counter bits. The package therefore evaluates candidate equation systems using a cost measure that sums the counts of linearization variables and parity-counter bits. Minimizing this measure reduces the auxiliary-variable count in the adopted construction, although the authors are careful to note that it does not guarantee lower practical solution difficulty, and their software neither constructs the QUBO matrix nor solves the resulting problem.

The payoff from careful modeling can be dramatic. For the AES S-box, replacing the original 39-equation system with a 13-equation system proposed in earlier work by the same group reduces the number of auxiliary variables from 299 to 106 per S-box, shrinking the AES-128 QUBO model from 68,600 to 30,026 logical variables. Those earlier results, obtained through laborious manual construction for a single cipher, motivated the generalization now embodied in SBoxQUBOSearch. The new package extends the underlying theory of implicit-relation construction and variance-guided basis transformations beyond AES, wrapping the methods in optimized standalone programs, versioned data schemas, reproducible job files, and a partitioning scheme that lets searches run on independent machines without any communication between them.

The software is organized as three command-line programs driven by JSON job files. The first, eqgen, generates equations: explicit ones via an in-place Möbius transform of the truth tables, and implicit relations by building a catalog of all monomials up to a chosen degree, evaluating them at every valid input-output pair, and extracting relations from the left nullspace of the resulting evaluation matrix through packed-row Gaussian elimination. The second program, search-global, then lexicographically enumerates subsets of the generated relations of a specified size, checking each candidate system for exactness using a bit-packed evaluation table in which a bitwise AND with the selected-equation mask vanishes precisely when a pair satisfies all chosen equations. The third, search-local, explores equivalent bases of a chosen system by applying invertible transformations over the two-element field, guided by an LFSR-inspired state machine that uses the variance of equation lengths to steer the traversal.

The exhaustive search is where the tool shows both its power and its limits. For the AES S-box, with 39 quadratic relations available, no exact system of eight, nine, ten, or eleven equations exists; the search confirmed this by testing billions of subsets. Exact twelve-equation systems first appeared among roughly 3.9 billion candidates, and at thirteen equations the search found 611,109 exact systems, the best of which achieved a cost of 109. That unpartitioned run took 13.2 hours on a laptop-class processor, but splitting the enumeration across eight independent partitions reproduced all 611,109 systems and the same eight minimizers, with each partition finishing in roughly 2.5 hours. For the lightweight ciphers ARADI and Ascon, the searches were nearly instant: four equations suffice for ARADI with a cost of just 8, while Ascon yielded 42 exact five-equation systems, the best scoring 19.

The 16-bit MK3 S-box pushed the method to its practical boundary. Exhaustive enumeration of sixteen-equation subsets from 79 relations would require examining roughly 2.16 times ten to the sixteenth power combinations, which is infeasible, and the evaluation table alone occupies 64 gigabytes. The researchers instead used a deletion strategy, removing one equation at a time and verifying with search-global that exactness survived, eventually establishing 28 as an upper bound on the minimum number of equations needed. Verified deletions followed by local optimization reduced the auxiliary-variable count from 1014 to 501. For Ascon, the combination of subset search and local optimization cut the count from 110 to 17, and for ARADI subset search alone reduced it from 71 to 8.

The local optimization stage proved remarkably reliable across hundreds of runs. Fifty sampled AES systems were each evaluated under three configurations, and every one of the 150 runs improved the cost measure, with a median gain of five points and the best system reaching 105. For Ascon, all 42 exact systems were tested under five configurations, improving in 91 percent of the 210 runs with a median gain of two and a best value of 17. For MK3, all 120 runs across two subset sizes improved, with median gains of four. The variance-guided heuristic works because the cost measure includes a logarithmic term, meaning bases that mix very short and very long equations can be advantageous; since an invertible basis change preserves the space spanned by the equations, the linearization-variable count stays fixed and all improvement comes from trimming the counter-bit term.

Beyond the headline numbers, the package is designed as a reproducible, reusable stage in a larger cryptanalytic pipeline. Versioned JSON and JSONL schemas define the persistent interface between stages, streaming output accommodates enormous result collections, and the file holding all 611,109 exact AES systems compresses from 124.7 megabytes to 4.45 megabytes. An 85-test Python suite independently validates equations, metrics, partitioning, and input handling. The authors position the tool as an upstream component rather than a solver: its outputs can feed QUBO models, algebraic attacks, SAT, SMT, and MILP formulations, or Gröbner-basis engines such as PolyBoRi. Current limitations are clearly stated, including support only for relations of degree at most two and memory requirements that scale with the size of the S-box domain. Released under the MIT license with all experimental artifacts, SBoxQUBOSearch turns what was once a bespoke, cipher-specific craft into a systematic search, offering cryptographers a practical head start whenever they need to squeeze a cipher’s innermost component into the variable budget of a quantum annealer.

Subject of Research: Automated search for exact algebraic S-box equation systems to minimize QUBO model size in cryptanalysis

Article Title: SBoxQUBOSearch: Exhaustive subset search and local basis optimization for exact algebraic S-box models

Article References: Burek, E., & Misztal, M. (2026). SBoxQUBOSearch: Exhaustive subset search and local basis optimization for exact algebraic S-box models. SoftwareX, 36, Article 103113. https://doi.org/10.1016/j.softx.2026.103113

Image Credits: AI Generated

DOI: 10.1016/j.softx.2026.103113

Keywords: SBoxQUBOSearch, S-box, cryptography, QUBO, quantum annealing, AES, Ascon, ARADI, MK3, algebraic cryptanalysis, Boolean equations, open-source software