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: http://www.cs.bu.edu/fac/lnd/expo/icm94.htm http://en.wikipedia.org/wiki/One-way_function http://mathworld.wolfram.com/One-WayFunction.html.
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: http://arxiv.org/pdf/cs/0012023v5.pdf.
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:


x2+1

XOR x =

x2+x+1

{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

Irreducible?

T T

F

Irreducible?

T F

T

Irreducible?

F T

T

Irreducible?

F F

F


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: https://arxiv.org/abs/1609.01541

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

Advertisements

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) .

    See: http://antoanthongtin.vn/Portals/0/UploadImages/kiennt2/Sach/Sach-CSDL4/D039.pdf

    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 :

    http://www.cs.tau.ac.il/~iftachh/Courses/FOC/Spring13/SolvedExe/PS1_Solution.pdf

    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 […]

    Like


  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. […]

    Like


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: