New complexity results clarify choosing parity subsets in cryptography
The Complexity of Choosing Parity Projections
Computational Complexity
Summary
This paper explores the difficulty of finding special groups of true/false variables called cubes in cryptanalysis, which help analyze the security of encryption methods. The authors show that two similar problems about these cubes differ greatly in how quickly they can be solved, depending on subtle details. They establish that without size limits, these problems are very hard computationally and difficult to approximate closely. The researchers provide exact classifications of these problems' difficulty and offer some algorithms for specific structured cases, along with evidence that improving these algorithms is unlikely.
What this means in practice
- •For cryptography engineers: Determine when algorithms can efficiently find small parity-based weaknesses in Boolean functions relevant to cryptanalysis of encryption.
- •For circuit designers: Assess complexity limits when analyzing parity properties in low-treewidth or restricted branching program circuits to guide design and testing.
A theory result. No direct application yet.
Authors
Karthik Sheshadri, Nicholas Smirnov
Abstract
Cube attacks in cryptanalysis seek small sets of Boolean variables (cubes) whose parity sum is constant. We study the bounded constant derivative problem introduced by Smirnov (2026), which seeks a smallest cube with sum 1, and its sum-0 analogue. Despite their similarity, the problems differ sharply in parameterized complexity: the sum-1 problem admits a $2^{O(k^2)}\operatorname{poly}(N)$-time algorithm, where $k$ is cube size, whereas the sum-0 problem is not fixed-parameter tractable unless $\mathrm{FPT}=\mathrm{W}[1]$. Without a bound on cube size, both problems are $Σ_2^{\oplus\mathrm{P}}$-complete and NP-hard to approximate within $N^{1-\varepsilon}$ for every fixed $0<\varepsilon<1$. Our hardness proofs use a crown construction that embeds maximal monomials of parity-projected circuits into positive 2CNF. This yields completeness and inapproximability results, as well as a dichotomy for Boolean constraint languages of arity at most two: the bounded constant derivative problem is in P when all relations are affine and $Σ_2^{\oplus\mathrm{P}}$-complete otherwise. We also give algorithms parameterized by the number of quadratic rounds, treewidth, or ordered branching-program width, with lower bounds for the first two unless $\mathrm{NP}\subseteq\mathrm{SUBEXP}$. The treewidth lower bound holds for circuits; the case of 2CNF remains open.