# 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

Encryption:

What your equation system shows is that the encryption is equivalent to multiplying two polynomials of degree N/2 on GF(2) (algebra of two elements {1,0} where 1+1=0, that is to say + = XOR).

"Proof":

Let A1 be an array of the coefficients of A1: $A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...$

Same goes for A2

Let B be the product polynomial of $B=A1\times A2$

Polynomial multiplication gives you:

$B=(A1[1]\times x^0+A1[2]\times x^1+A1[3]\times x^2+...)\times(A2[1]\times x^0+A2[2]\times x^1+A2[3]\times x^2+...)$

$B=(A1[1]\times A2[1]\times x^0+(A1[2]\times A2[1]+A2[2]\times A1[1])\times x^1+...)$

In general $B[i]=Sum(A1[n]\times A2[l],n+l==i+1)$ (%2 because of GF(2))

You wrote:

$B[5] = (A1[1] & A2[4]) ^ (A1[2] & A2[3]) ^ (A1[3] & A2[2]) ^ (A1[4] & A2[1])$

This is exactly the previous formula for i=4, you have $B[1]=0$ so there's a shift: your $B[5]$ is the coefficient in front of x^3.

Decryption:

If the encryption is polynomial multiplication of two polynomials of degree N/2, the decryption is polynomial factorisation into two parts of degree less than N/2. This can be done with the Berlekamp Algorithm or Cantor–Zassenhaus Algorithm

Note these algorithms will work because we are on a finite field GF(2) where the coefficients have finite possible values.

-
What is your question? Please make use of MathJax – user190080 Sep 11 '15 at 13:04
Thanks for the MathJax link, looks a bit better now. I'm just trying to give a more detailed answer along the lines of adam W's comments because it is the answer to this problem and the question has no accepted answer. If someone wants to post a clearer answer they are welcome to do so. – Agade Sep 11 '15 at 13:17
sorry, I somehow mistook your post as a possible question and not as an answer – user190080 Sep 11 '15 at 13:21