A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

This paper presents a novel, compact QUBO encoding method for cryptographic algorithms that significantly reduces the number of logical variables and coefficient magnitudes compared to previous approaches, thereby increasing the vulnerability of systems like AES-256 to future quantum annealers.

The Gist

Imagine you are trying to crack a safe. The safe is locked with a complex combination of tumblers (the encryption algorithm), and you have a master keyring of tools (a quantum computer) designed to find the right combination. However, the master keyring is heavy, clumsy, and can only hold a limited number of tools at once. If the combination you are trying to crack requires too many tools, the keyring breaks, and you can't open the safe.

This paper is about making the tools smaller and lighter so that the master keyring can hold enough of them to crack the safe.

Here is a breakdown of the paper's ideas using everyday analogies:

1. The Problem: The "Heavy Suitcase" of Logic

The researchers are working with a type of math problem called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a giant, complex puzzle where you have to arrange thousands of switches (on/off) to find the one perfect configuration that solves a problem.

• The Issue: When you try to translate complex computer logic (like the math behind encryption codes AES, MD5, or SHA) into this QUBO puzzle, the "suitcase" of switches becomes incredibly heavy.
• The Consequence: Current quantum computers (specifically "quantum annealers") are like small backpacks. They can only carry a certain number of switches. If the puzzle requires 100,000 switches, but the backpack only holds 30,000, the puzzle is impossible to solve.

2. The Solution: "Compression" and "Smart Packing"

The authors developed a new way to translate these logic puzzles into QUBO format. They didn't just shrink the suitcase; they invented a new way to pack it.

• The Old Way (Tseitin Transformation): Imagine trying to pack a suitcase by throwing in every single item individually. If you have a complex sentence like "If A is true AND B is false, then C happens," the old method would create a separate, bulky box for every tiny logical step. This creates a massive suitcase full of redundant items.
• The New Way (ILP & Patterns): The researchers used a "smart packing algorithm" (called Integer Linear Programming or ILP). Instead of packing every item individually, they looked for patterns.
  • Analogy: Imagine you have 100 socks. The old way puts each sock in its own box. The new way realizes, "Hey, these 100 socks are all the same color and type," so it bundles them into a single, compact cube.
  • They found mathematical shortcuts (like "Root Squeezing") that allow them to represent a huge range of possibilities using very few switches.

3. The "Magic Trick": Squeezing the Range

One of their key discoveries is a technique they call Root Squeezing.

• The Metaphor: Imagine you need to represent numbers from 1 to 100.
  • Standard Method: You need a lot of switches to count up to 100.
  • Their Method: They realized that if you have two different ways to represent the numbers that are "close" to each other (like 49 and 50), you can use a single mathematical trick to cover both with the same set of switches. It's like having a single key that fits two slightly different locks because the locks are so similar. This allows them to cut the number of required switches in half (or more).

4. The Results: Cracking the Unbreakable (Almost)

They tested this new packing method on famous encryption algorithms:

• AES (The Gold Standard): This is the lock used to secure banking and government data.
• SHA/MD5 (The Digital Fingerprint): These are used to verify that a file hasn't been tampered with.

The Outcome:

• For AES-256 (a very strong lock), previous methods required a suitcase with about 250,000 switches.
• The authors' new method shrunk that suitcase down to about 30,000 switches.
• The Impact: That is an 8x reduction. While 30,000 is still too big for today's quantum computers, it brings the problem much closer to the edge of what is possible. It's the difference between trying to lift a car versus lifting a heavy motorcycle.

5. Why This Matters

The authors aren't trying to hack your bank account today. Instead, they are sounding an alarm.

• The Warning: They are showing that as quantum computers get better (able to carry bigger backpacks), the "heavy suitcases" of current encryption will become light enough to crack.
• The Future: By making these encodings so efficient, they are proving that we need to start designing new types of locks (post-quantum cryptography) that are resistant to these efficient quantum attacks.

Summary

Think of this paper as a master Tetris player. For years, people tried to fit the complex shapes of encryption logic into a small quantum computer, but the pieces were too big and the board was too small. These researchers invented a new way to rotate and stack the pieces (using smart math patterns) so that the same complex logic fits into a much smaller space. This proves that the "unbreakable" locks of today might not be so unbreakable tomorrow, urging us to upgrade our security systems before the quantum backpacks get big enough to carry the new, smaller suitcases.

Technical Summary

1. Problem Statement

The paper addresses the challenge of efficiently mapping complex computational logic problems, specifically cryptographic algorithms, into the Quadratic Unconstrained Binary Optimization (QUBO) framework.

• Context: QUBO is the native format for quantum annealers (e.g., D-Wave). Solving cryptography problems (like key recovery) via quantum annealing requires finding the exact global minimum, as sub-optimal solutions are meaningless in this context.
• The Bottleneck: Existing methods for converting Boolean logic (SAT) to QUBO often result in:
  • An excessive number of binary variables (ancillary/substitution variables).
  • High density in the QUBO matrix.
  • Large coefficient magnitudes that exceed the numerical precision limits of current hardware.
• Goal: To develop a methodology that minimizes the number of variables and coefficients while maintaining sparsity, thereby making cryptographic problems (AES, SHA, MD5) more feasible for future quantum hardware capable of handling ~30,000 logical variables.

2. Methodology

The authors propose a hybrid approach combining Integer Linear Programming (ILP) for pattern discovery and algebraic theorems for scalable encoding.

A. ILP-Based Pattern Discovery

Instead of solving the SAT problem directly, the authors use ILP to find the optimal encoding patterns.

• Objective: Find a quadratic function $g(x, s)$ where $x$ are input variables and $s$ are substitution variables.
• Constraints:
  • $g(x_{min}, s_{valid}) = 0$ for all valid "min-terms" (satisfying assignments).
  • $g(x, s) > 0$ for all other inputs.
• Process: The authors perform an exhaustive search over small SAT instances to determine the minimum number of substitution variables ($N_s$) and the optimal coefficients. They utilize symmetry breaking and counter-example guided optimization to solve these ILPs efficiently.

B. Theoretical Encoding Strategies

Based on the ILP results, the authors derived general theorems for encoding different logic forms:

1. Root Squeezing Theorem: A mathematical proof showing that the product of two linear functions, $g(X)h(X)$, where the roots differ by at most 1, creates a non-negative quadratic form that is zero only at the desired roots. This allows encoding range constraints without the quadratic penalty of direct squaring.
2. Range Encoding Theorem: Using the Root Squeezing concept, they encode multi-input OR and population count constraints using one fewer substitution variable than traditional methods. This is achieved by mapping a single substitution bit-string to two adjacent integer values ($2t-1$ and $2t-2$).
3. Logic Gate Encoding:
   • XOR (Parity): Encoded by minimizing the squared difference between the sum of inputs and an odd integer target.
   • AND/OR: Encoded using the "Root Squeezing" product form or specific quadratic forms that reduce coefficient magnitude.
   • CNF/DNF/ANF: The authors propose a strategy of assigning substitution variables to sub-clauses (strong equivalence) and then encoding the outer logical structure using the optimized patterns above.

C. Cryptographic Application Strategy

For complex circuits like AES and SHA:

• Logic Markers: Instead of converting the entire circuit to CNF via Tseitin transformation (which creates many variables), they identify specific multi-input gates (AND, OR, XOR) and apply the optimized QUBO patterns directly.
• Modular Arithmetic: For addition in hash functions, they use a block-wise strategy (breaking 32-bit additions into smaller blocks of size $B$) to control coefficient magnitudes, trading off variable count for numerical stability.

3. Key Contributions

1. Novel Encoding Theorems: Introduction of the Root Squeezing Theorem and Range Encoding Theorem, which mathematically prove that range constraints and multi-input OR functions can be encoded with fewer variables than previously thought possible.
2. ILP-Driven Optimization: A systematic method to discover optimal substitution variable counts and coefficients for specific logic gates, moving beyond heuristic Tseitin transformations.
3. Cryptographic Benchmarks: The first demonstration of these techniques on full-scale cryptographic primitives (AES-128/192/256, MD5, SHA-1, SHA-256), providing concrete QUBO instances.
4. Variable Reduction: A strategy to significantly reduce the "logical variable" count, which is the primary bottleneck for embedding problems onto quantum annealers.

4. Results

The authors compared their encoding against state-of-the-art methods (specifically Ref. [36] and [74]).

Algorithm	Previous Best (Ref [36])	This Work (Variables)	Reduction
AES-128	~90,000	21,294	~76% reduction
AES-192	~200,000	24,264	~88% reduction
AES-256	~250,000	29,330	~88% reduction (8x smaller)
SHA-256	47,808	30,255 (Block $B=6$)	~37% reduction
MD5	17,280	10,272 (Block $B=6$)	~40% reduction

• Sparsity: The resulting QUBO matrices are highly sparse (0.04% – 0.52% density), which is crucial for embedding on hardware with limited connectivity (Chimera/Pegasus/Zephyr graphs).
• Coefficient Magnitude: By using block-wise addition ($B=6$), they kept coefficients manageable, though a trade-off exists where smaller blocks ($B=1$) reduce coefficients further but increase variable counts.

5. Significance and Implications

• Quantum Vulnerability: The drastic reduction in variable count (e.g., AES-256 reduced to ~30k variables) brings these cryptographic problems closer to the capabilities of near-future quantum annealers (projected to handle ~30k logical variables). This highlights a potential vulnerability in current cryptographic standards against future quantum hardware.
• Hardware Compatibility: The method produces sparse matrices with controlled coefficient magnitudes, directly addressing the two main hardware constraints of current quantum annealers: connectivity and numerical precision.
• Generalizability: While demonstrated on cryptography, the "Root Squeezing" and ILP-based pattern discovery are applicable to any combinatorial optimization problem involving logic constraints (e.g., scheduling, partitioning).
• Future Work: The authors note that while they found optimal encodings for small components, finding the absolute optimal Boolean circuit for complex functions (like GF($2^8$) multiplication) remains an NP-hard challenge. Future work will focus on improving the ILP solvers to handle larger boolean functions and further reducing variable counts.

In conclusion, this paper provides a foundational shift in how logic is mapped to QUBO, moving from generic transformations to mathematically optimized, compact encodings that significantly lower the barrier for solving hard cryptographic problems on quantum hardware.