Mixing xor with modular addition Having two known constant A and B, and one unknown X, can we solve the following equation :

(A xor X)+ X=B

where xor is the bit-wise xor operator and + is the modular addition. For example, A,B and X can belong to the set{0,1,...,255} so the addition is modulo 256.
This equation can be a replacement for classical xor operation used by stream ciphers. If this equation cannot deterministically be solved then a known plain-text attack cannot be mounted against the cipher to deduce the keystream....
For any $n&gt;0$ and any fixed $A$ the function $f_A : x \mapsto (A \oplus x) + x \bmod 2^n$ is affine over the field with 2 elements, i.e., $f_A(x\oplus y) = f_A(x)\oplus f_A(y)\oplus A$ (as $A = f_A(0)$).

A proof that the analog map $g_A : x \mapsto (A \oplus x) - x \bmod 2^n$ is affine, you can find in Louis Goubin's CHES 2001 paper A Sound Method for Switching between Boolean and Arithmetic Masking. For $f_A$ I do not know any published reference.

$f_A(x) = B$ is equivalent to $f_A(x)\oplus A = B\oplus A$, so you have to find out if the vector $B\oplus A$ is in the image of the $\mathbb F_2$-linear map $x\mapsto f_A(x)\oplus A$, and if it is, a preimage $x$. This is linear algebra, hence easy from a complexity-theoretical point.

For solving the linear equation you have first to check if $B\oplus A$ is a linear combination of the image of a bases, so taking the base $1, 2, 4, 8, 16, \dots$ you have to look if $B\oplus A$ can be written as a sum of a subset of the vectors $f_A(1)\oplus A=((A\oplus 1)+1\bmod 2^n)\oplus A$, $f_A(2)\oplus A=((A\oplus 2)+2\bmod 2^n)\oplus A$, $f_A(4)\oplus A=((A\oplus 4)+4\bmod 2^n)\oplus A, \dots$ using something like Gaussian elimination.

If it is, and let's say, for $I\subseteq \{0, 1, \dots, n-1\}$ you get $B\oplus A = \bigoplus_{i\in I} (f_A(2^i)\oplus A)$, then $x = \bigoplus_{i\in I} 2^i$ is your solution. EDIT: In general, you will get all solutions in this way. Linear algebra tells us that the set of solutions is either empty or an affine subspace, i.e., of the form $\{x_0+v| v\in W\}$ where $x_0$ is any solution and $W$ is an $\mathbb{F}_2$-subspace of the $n$-dimensional vector space of $n$-bit vectors.



So from a security point, I do not expect an improvement using this equation,  (EDIT:) as the solution set can be efficiently calculated and described (using one solution and a basis of $W$ of order $\le n$).