Affine-Hull Exchange Between Gaussian Elimination and Bitset Table Propagation

Many hard satisfiability problems combine two kinds of structure. One kind is linear over bits: parity constraints, or exclusive-ORs (XORs). Gaussian elimination solves these well. The other kind is small but nonlinear: a cipher's substitution box (S-box), a multiplier's partial-product cell, a gate recovered from clauses. These are naturally written as tables of allowed bit patterns. Today's strongest parity-aware solvers send the XORs to a Gaussian-elimination engine and flatten everything else into clauses, so the two kinds of reasoning only talk through individual variable assignments. We propose a two-way exchange between them. A reduced linear equation whose remaining variables fall inside one table's scope can delete table rows. Conversely, once a table's surviving rows all satisfy some linear relation, that relation is added to the linear system as a new equation.

The exchange is cheap because the tables involved are small. A DES S-box (6 inputs, 4 outputs) has exactly 64 allowed rows, so its live rows fit in one 64-bit machine word. The set of rows satisfying any parity condition over its 10 bits can be precomputed as one word per mask, 1024 words in total. Filtering a table by a linear equation is then a single AND. Finding which linear relations the survivors imply is a Gaussian elimination over at most 64 ten-bit vectors. The claim is that this conditional linear structure exists and is useful. It appears only under partial assignments, so static preprocessing cannot see it. Clause learning and per-variable propagation recover it only slowly.

What exists and what is missing

The parity side supplies the linear engine. BIRD runs Gauss-Jordan elimination inside CryptoMiniSat. To survive clause simplification, it converts XORs to clauses, simplifies, then recovers the XORs with Bloom-filter signatures. Tinted, Detached, and Lazy CNF-XOR Solving (BIRD2) adds bit-packed propagation using population counts, detaches clauses that elimination already covers, and builds explanation clauses only when conflict analysis asks for them. Gaussian Elimination Meets Maximum Satisfiability puts bit-packed elimination at every node of a MaxSAT search. All three reason only about linear rows and clauses. None has a representation for a nonlinear relation other than its clauses.

The table side supplies the data structures. Optimizing Simple Tabular Reduction with a Bitwise Representation and Extending Compact-Table to Negative and Short Tables keep live tuples as bitsets and prune with per-literal masks. Compact-MDD makes such bitsets reversible across backtracking. None of these works considers linear constraints spanning many tables.

The closest connector in the file is HYBRIDCEC. It switches wholesale between SAT and exact simulation using an XOR-density score, rather than combining the two engines inside one search.

Two results constrain the design. First, writing an XOR as a table is as bad as writing it as clauses: a $k$-variable XOR has $2^{k-1}$ allowed rows. So long XORs must stay in the elimination engine, and only small nonlinear relations become tables. Second, The Hard Problems Are Almost Everywhere For Random CNF-XOR Formulas shows exponential scaling across all densities of random CNF-XOR formulas. We therefore expect no gains on random instances and target structured ones.

Core Claim

Let $T$ be a table over bits $x_1,\dots,x_a$ and let $A \subseteq \{0,1\}^a$ be its currently live rows, stored as a bitset. For a mask $m \in \{0,1\}^a$ and a parity $c$, let $P_T[m,c]$ be the bitset of rows $t$ with $m \cdot t = c \pmod 2$.

The forward rule is as follows. When Gauss-Jordan elimination produces a row whose unassigned variables all lie in $T$'s scope, with mask $m$ and right-hand side $c$, we set $A \leftarrow A \wedge P_T[m,c]$. Per-variable pruning then proceeds through the usual support masks.

The backward rule computes the affine hull of $A$, meaning every pair $(m,c)$ such that $A \subseteq P_T[m,c]$. Each hull equation not already spanned by the linear system is pushed into it as a new row. The hull is computed by elimination on the vectors $t \oplus t_0$, where $t_0$ is any fixed live row. Recomputation is triggered only when $|A|$ halves, because the hull's dimension cannot drop otherwise.

Repeating the two rules propagates strictly more than either engine alone. The new deductions come from cases where neither the linear system nor any single table forces a variable, but a linear combination restricted to a table's scope does.

Explanations follow BIRD2's lazy scheme. A pruned table row or an exported equation is justified by the assignments that removed rows and the elimination rows that were combined. The corresponding clause is built only when conflict analysis requests it.

Research Program

We would build this inside CryptoMiniSat so that it shares BIRD2's elimination engine. Tables would enter in one of three ways: given directly (S-boxes from a cipher encoding), extracted from small cuts of an and-inverter graph (multiply-add datapath circuits), or recovered from clauses by extending Barbet's signature matching from XOR gates to arbitrary gates of up to about 10 inputs. Live-row sets would use reversible sparse bitsets as in Compact-MDD. Exported equations would be tagged with their decision level and retracted on backtracking.

The analysis would measure how often the forward and backward rules fire, and how often an exported equation feeds a conflict. We would also characterise when hull drops happen. For DES S-boxes, the hull is full-dimensional with no inputs assigned, because S-boxes are designed to be nonlinear. It shrinks only after a few inputs are fixed. That is exactly the conditional structure the proposal relies on.

Baselines

The naive reference point is a plain clause-learning solver given the flattened clause encoding. We would use Kissat with no XOR or table reasoning, run on the same machines with the same timeout.

The strongest competitor is CryptoMiniSat with BIRD2's Gauss-Jordan elimination, tinted propagation, and detaching, as in Tinted, Detached, and Lazy CNF-XOR Solving. It is the strongest because it already handles the linear layer natively, and our system is that same codebase plus the exchange. Its reported result on the 1,896-instance counting suite is that ApproxMC4 solved 77 more instances than ApproxMC3, with model-counting PAR-2 improving from 4146 to 3701. For the DES instances there is no reported result on Lacuna for BIRD2. The historical reference is Integrating Equivalency Reasoning into Davis-Putnam Procedure: EqSatz sped up 3-round DES, but no method in that work solved 4-round DES within reasonable limits.

Both systems would use identical encodings, timeouts, and default parameters, with an equal parameter-tuning budget on a held-out split. Beating BIRD2 means solving more instances, or lowering PAR-2, on DES and datapath instances. It also means no more than noise-level PAR-2 regression on the counting suite, where tables are rare.

Three ablations isolate the exchange. The first runs tables propagated by bitsets inside the clause-learning solver with no link to elimination. The second uses the forward rule only. The third computes hull equations once, statically, before search, and adds them to the linear system.

Why not just…?

Why not just let clause learning discover the interaction? BIRD2 already shares variable assignments between elimination and clauses. The question is whether learned clauses recover the conditional linear relations fast enough. The forward-only and full-exchange ablations against BIRD2 answer this directly. If the backward rule never contributes to conflicts, the claim fails.

Why not just precompute each table's linear relations once? This is the most serious threat on instances whose tables are only partly nonlinear, such as recovered gates or datapath cells. For DES S-boxes, the unconditional hull adds nothing, because the boxes are deliberately nonlinear. The static-hull ablation settles this. If it matches the dynamic exchange, the dynamic machinery is unnecessary and we would report that.

Why not just use a constraint solver with Compact-Table and write XORs as tables? Tables for long XORs grow as $2^{k-1}$ rows, which is the same blow-up as clauses. This gives no global elimination across the cipher's linear layer. We include such a configuration on 3-round DES to show this concretely.

Why not just conjoin everything into a decision diagram? Compact-MDD's own analysis notes that ordering decision-diagram variables is NP-hard. Cipher linear layers interleave every S-box with every other, which is the worst case for a single variable order.

Proposed Experiments

The primary experiment uses Massacci's 3-round and 4-round DES key-search encodings (Using Walk-SAT and Rel-Sat for Cryptographic Key Search), with S-boxes given as tables. We measure solved count, PAR-2, and conflicts to solution. The decisive check is whether 4-round instances, unsolved by EqSatz, become solvable while BIRD2 fails on them.

The second experiment uses the 50 industrial datapath circuits from HYBRIDCEC, with tables taken from cuts of up to 6 inputs. HYBRIDCEC solved 45 of 50 and ABC solved 25. We report our count inside a single SAT search alongside both.

The third experiment is the 1,896-instance counting suite run through ApproxMC, with tables recovered from clauses. This is a no-regression check against the 3701 PAR-2 reference.

We also report time per propagation, to confirm that the one-word AND keeps overhead negligible. Given the slowdown that Optimizing Simple Tabular Reduction with a Bitwise Representation reports for bitset structures on small tables, we expect the overhead to show up most on instances with many tiny tables.