# How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode that uses bit arrays (1-indexed):

N is a power of 2 strictly greater than 1.

encode(A : Array of N bits) -> B : Array of N bits

// Split the input into two halves.
Var A1 : Array of N/2 bits := A[1 .. N/2]
Var A2 : Array of N/2 bits := A[N/2+1 .. N]

// Initialize the result with all bits to zero.
For k from 1 to N
B[k] := 0

// Do the work.
For i from 1 to N/2
For j from 1 to N/2
B[i+j] := B[i+j] XOR (A1[i] AND A2[j])

Return B


For illustration, here's a "live" C++ program: http://ideone.com/NBGGPS

For example I have unrolled it for N = 8, then B is like this (symbols: & for AND, ^ for XOR):

B[1] = 0
B[2] = (A1[1] & A2[1])
B[3] = (A1[1] & A2[2]) ^ (A1[2] & A2[1])
B[4] = (A1[1] & A2[3]) ^ (A1[2] & A2[2]) ^ (A1[3] & A2[1])
B[5] = (A1[1] & A2[4]) ^ (A1[2] & A2[3]) ^ (A1[3] & A2[2]) ^ (A1[4] & A2[1])
B[6] =                   (A1[2] & A2[4]) ^ (A1[3] & A2[3]) ^ (A1[4] & A2[2])
B[7] =                                     (A1[3] & A2[4]) ^ (A1[4] & A2[3])
B[8] =                                                       (A1[4] & A2[4])


That resembles a system of N equations with N variables (knowing that for bits a XOR b = (a + b) mod 2 and a AND b = (a × b) mod 2 = a × b):

$$\begin{eqnarray} b_1 & = & 0 & & & & & & & \\ b_2 & = & x_1 \cdot x_5 & & & & & & & \\ b_3 & = & x_1 \cdot x_6 & + & x_2 \cdot x_5 & & & & & \pmod 2 \\ b_4 & = & x_1 \cdot x_7 & + & x_2 \cdot x_6 & + & x_3 \cdot x_5 & & & \pmod 2 \\ b_5 & = & x_1 \cdot x_8 & + & x_2 \cdot x_7 & + & x_3 \cdot x_6 & + & x_4 \cdot x_5 & \pmod 2 \\ b_6 & = & & & x_2 \cdot x_8 & + & x_3 \cdot x_7 & + & x_4 \cdot x_6 & \pmod 2 \\ b_7 & = & & & & & x_3 \cdot x_8 & + & x_4 \cdot x_7 & \pmod 2 \\ b_8 & = & & & & & & & x_4 \cdot x_8 & \\ \end{eqnarray}$$

Some (informal) thoughts:

1. It is kind of "symmetric": you get the same result if you swap the two halves of A.
2. I have seen examples that you can get the same result for several different inputs ("different" not only by symmetry), so it is "lossy".
3. It looks like a "keyless XOR encryption" (well, not sure this one even makes sense...).

Now the challenge is to "reverse" it, i.e. to write some decoding algorithm such that decode( encode(A) ) = A.

But after bullet 2 above (and also 1) we know that the solution is not unique, so we must rather find one possible solution such that encode( decode_one( encode(A) ) ) = encode(A), or maybe we can find all possible solutions i.e. an algorithm such that decode_all( encode(A) ) = { X | encode(X) = encode(A) }.

(Of course "brute force" is not interesting.)

Now I'm just completely stuck on that... For example, if B[2] = 1 then I know that both A1[1] and A2[1] are 1, but if B[2] = 0 then I can only say that A1[1] and A2[1] are not both 1 (they could be both 0, or one 0 and the other 1). Then for B[3] the XOR comes in and multiplies the possibilities...

I tried to somehow "combine" several equations from the unrolling but it's not linear.

What would be the way to go?

(Also feel free to edit the post e.g. to add relevant tags.)

-
If it helps, this is multiplication of polynomials with coefficients mod 2. (Which is also convolution.) Thus the problem is to factor a degree 8 polynomial into two degree 4 polynomials. –  adam W Oct 12 '13 at 16:57
@adamW Thanks for your hint. I have looked up "convolution" on the web but that's Greek to me :'( Also about "degrees 8 and 4", I guess it's for the N=8 example, so it's generally "degrees N and N/2"? Then can you please point me to an online resource that explains the process to factor? (All that looks overly complicated to me, while the encoding algorithm is so simple...) I have also added a link to a C++ program, and a "math" equation system. –  Wilhelm Siret Oct 13 '13 at 10:01
Yes, it is degrees N and N/2 generally speaking. And it is possible to be easy one direction (encoding) while difficult in the other (decoding). I am only able to recognize that it is polynomial multiplication and cannot help further--I wish you luck. If I learn anything more helpful, I will let you know about it. –  adam W Oct 13 '13 at 13:54