Paper 2024/2035

Add/XNOR Chains: An NP-Complete Boolean-Arithmetic Problem at the Meet-in-the-Middle Barrier

Ping Wang, Shenzhen University
Mengxin Lv, Shenzhen University
Zishen Shen, University of California, Berkeley
Fangguo Zhang, Sun Yat-sen University
Abstract

We introduce the Add/XNOR decision problem: given $n$ words of $n$ bits, decide whether they can be combined into zero by a left-associative chain in which each operator is either addition modulo $2^n$ or bitwise XNOR. We prove NP-completeness by a deterministic reduction from Subset-Sum{} in which four-bit guard fields and a parity normalization force every gadget to be all-additions or all-XNORs; hardness persists for every width that is a fixed rational power of the operand count, and 3-SAT reduces with linear parameter blow-up. The problem is a minimal model of Boolean--arithmetic mixing, and we give an exact theory of its linear and differential behaviour: a carry decomposition, closed forms for every single-bit linear correlation (for addition runs $z_1,\ldots,z_r$ the bit-$1$ correlation is $\prod_j2^{-z_j/2}\cos(z_j\pi/4)$, averaging exactly $(n+1)2^{-n}$), and an exact transposition differential with collision probability $2(5/8)^{m-1}-2^{-(m-1)}$, all confirmed experimentally. Both operations are triangular, which yields a low-bit dissection algorithm with worst-case time $\Ostar(2^{n/2})$ and space $\Ostar(2^{n/4})$ plus an explicit balance parameter; no technique we know of improves the exponent $1/2$. We explain why the representation technique that recently broke the $2^{n/2}$ barrier for Subset-Sum{} is not available to the natural formulation of non-commutative chains, report that CDCL solvers scale as roughly $2^{0.7n}$ in our experiments, and prove in an ideal chain model, where each operation is an independent random permutation, that planted search requires $\Omega(2^{(n-1)/2})$ oracle queries. We place the problem in the current fine-grained landscape, in which the 3SUM, APSP and (strong) exponential time hypotheses have been refuted: the conditional lower bound that the 3-SAT reduction would otherwise yield is void, and the exponential complexity of Add/XNOR is open in both directions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
NP-completenessAdd/XNORBoolean-arithmetic mixingmeet-in-the-middlegeneric lower boundsfine-grained complexity
Contact author(s)
wangping @ szu edu cn
2510044047 @ mail szu edu cn
zishen @ berkeley edu
isszhfg @ mail sysu edu cn
History
2026-11-02: last of 22 revisions
2024-12-17: received
See all versions
Short URL
https://ia.cr/2024/2035
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2024/2035,
      author = {Ping Wang and Mengxin Lv and Zishen Shen and Fangguo Zhang},
      title = {Add/{XNOR} Chains: An {NP}-Complete Boolean-Arithmetic Problem at the Meet-in-the-Middle Barrier},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2035},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.