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 Z_{2} = {0,1}. Let P1 be equal to x^{2}+1 and P2 equal to x. The following are equivalent representations of the same value in a characteristic 2 finite field: Polynomial (P1): x^{2}+1 Binary: {101} and Polynomial (P2): x Binary: {010} Remembering that a sum in GF(2) corresponds to the bitwise XOR operation, P1 ⊕ P2 =x^{2}+x+1. See:
x^{2}+1 |
XOR | x | = |
x^{2}+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 x^{2}+x+1 is the irreducible polynomial in finite field GF(2), because x^{2}+x+1 has no solution (try plugging in 0 or 1 to see). In other words, x^{2}+x+1 is a polynomial that may not be factored into the product of two non-constant polynomials:
x^{2}+1 | x | x^{2}+x+1 | |
Irreducible? |
T | T |
F |
Irreducible? |
T | F |
T |
Irreducible? |
F | T |
T |
Irreducible? |
F | F |
F |
Now, note that x^{2}+1 corresponds to the NOT gate in GF(2), thus being a bijection. Note also that x cannot be non-invertible, then, so that x^{2}+x+1 is irreducible in the truth table of its XOR gate, x^{2}+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.
April 3, 2015 at 4:03 pm
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!
LikeLiked by 1 person
April 7, 2015 at 6:13 am
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.
LikeLiked by 1 person
March 6, 2016 at 3:44 am
[…] some ‘key’differences between the involution logic of the Alex DeCastro work presented here and the PRG, temporal error feed-forward of my […]
LikeLike
November 29, 2016 at 3:15 am
[…] 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. […]
LikeLike