One Way Bijection Over GF(2)

April 1, 2015

Guest post by Alexandre De Castro:

Phillip, thank you for the reference to my paper on one-wayness in Bennett’s cycle. In that paper, I explored the possibility of unidirectionality in bijections from the thermodynamic point of view. But here, I would like to show a mathematical point of view of one-way bijections.

It is known that the existence of one-way bijections would be a much stronger statement than the quantification of P<NP. See:
Leonid Levin has proposed that there is an explicit bijection in GF(2) that is one-way, if and only if one-way functions exist. See:
The problem of determining the existence of one-way functions is thus reduced to the problem of proving that Levin’s bijeciton is one-way.

Then, consider GF(2) as the smallest finite field, a two-element Galois field, with Z2 = {0,1}. Let P1 be equal to x2+1 and P2 equal to x. The following are equivalent representations of the same value in a characteristic 2 finite field: Polynomial (P1): x2+1 Binary: {101} and Polynomial (P2): x Binary: {010} Remembering that a sum in GF(2) corresponds to the bitwise XOR operation, P1 ⊕ P2 =x2+x+1. See:


XOR x =


{1 0 1}

{0 1 0} =

{1 1 1}

So, since the XOR operation for making the sum P1+P2 is used, now check the truth table of XOR gate. Remembering that the polynomial x2+x+1 is the irreducible polynomial in finite field GF(2), because x2+x+1 has no solution (try plugging in 0 or 1 to see). In other words, x2+x+1 is a polynomial that may not be factored into the product of two non-constant polynomials:

x2+1 x x2+x+1













Now, note that x2+1 corresponds to the NOT gate in GF(2), thus being a bijection. Note also that x cannot be non-invertible, then, so that x2+x+1 is irreducible in the truth table of its XOR gate, x2+1 must be one-way.
This true contradiction is the core of Gödel’s Pvs.NP problem and the proof of Levin’s one-way bijection (universal one-way function) which we have recently shown in:

Alexandre de Castro is a research scientist of the Laboratory of Computational Mathematics at Embrapa Agriculture Informatics.


4 Responses to “One Way Bijection Over GF(2)”

  1. vznvzn Says:

    thx for dropping by my blog. the result sounds interesting but it also sounds a little to brief to be a correct proof. would be interested in chatting further on this & other CS topics with either of you on stackexchange. try it, its not hard/ useful/ fun!

    Liked by 1 person

  2. AdC Says:

    Hi vznvzn,

    This problem of the post is in p.94 of Foundations of Cryptography, 2004(Oded Goldreich) .


    Exercise 9 – Refute the following conjecture:

    For every length-preserving one-way function f, the function f'(x) = f(x) ⊕ x is one-way.

    A solution for the refutation can be found in :

    That is the core of Levin’s function. Note that the solution for the refutation is short too. However, the conjecture can only be refuted for even input. In my proof I show that f(x) ⊕ x is equal to x²+x+1, which shows that this polynomail may not have ever input. Then, f'(x) = f(x) ⊕ x is one-way.

    Pr[f(f(A(f(x)))=f(x)] = ½ for f((x)=NOT(x), A is a randomized algorithm .

    and Pr[f(f(A(f(x)))=f(x)]< 1/p(n) for p(n)=x²+1.

    This condition above asserts both x²+1 and f(x) ⊕ x are one-way.

    Liked by 1 person

  3. […] some ‘key’differences between the involution logic of the Alex DeCastro work presented here and the PRG, temporal error feed-forward of my […]


  4. […] page in September. I suppose it represents a rigorous development of the work mentioned here & here previously, whilst also extending the scope to demonstrate quantum information theory equivalence. […]


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: