Add/XNOR Chains: An NP-Complete Boolean–Arithmetic Problem at the Meet-in-the-Middle BarrierResearch Paper
Addition modulo and bitwise XOR are the two cheapest operations on machine words, and mixing them is the standard way of destroying algebraic structure: it underlies ARX (add–rotate–XOR) ciphers and most hash functions in use. The paper of Wang, Lv, Shen and Zhang isolates the decision version of this mixing in its simplest form. A chain of words is…