EPR-Redux; (We’re so sorry, Uncle Albert!)

2015 marks the 80th. anniversary of the EPR paradox.

“One can give good reasons why reality cannot at all be represented by a continuous field. From the quantum phenomena it appears to follow with certainty that a finite system of finite energy can be completely described by a finite set of numbers (quantum numbers). This does not seem to be in accordance with a continuum theory and must lead to an attempt to find a purely algebraic theory for the representation of reality. But nobody knows how to find the basis for such a theory.” A. Einstein; Appendix 2: The Meaning of Relativity, 1935

In 1935 Albert Einstein, along with two colleagues, Boris Podolsky and Nathan Rosen, published a work known as the EPR paper, challenging the foundations of quantum mechanics. The three scientists argued that extra pieces of information – hidden variables – were necessary to perform the unitary evolution of the wave function and make quantum mechanics a complete theory. In the following, we show that the idea of hidden variables can be understood from the measurement-based implementation of a controlled-NOT (CNOT) quantum gate.

In quantum mechanics, the EPR paradox is a thought experiment which challenges long-held ideas about the completeness of quantum theory. The core of the EPR paradox is that quantum mechanics cannot be both consistent and complete unless hidden variables exist.

The EPR paradox has been strongly debated over for eighty years and almost all of the arguments, including the work of John Bell, have refuted the hidden variables theory. Here we show in a fairly simple way, how the concept of hidden variables advocated by Einstein, Podolsky and Rosen can be understood with the aid of a most common quantum device: the controlled-NOT gate.

The controlled-NOT gate (CNOT) is used to entangle and disentangle EPR states. Its unitary operator  can be written on two-bits operationally,  and , where the former is the control bit, the latter is the target bit, and  is the Galois field of two elements :

where,

The matrix  for this operation is:

	1	0	0	0
	0	1	0	0
	0	0	0	1
	0	0	1	0

Now, note that the state transformation can be replaced with , where .
In , the inverter gate corresponds to the polynomial representation , and every element satisfies the property .
Hence, the logical negation can also be represented by the polynomial .

The exclusive disjunction corresponds to the field’s addition (mod2) operation in Galois field of two elements, therefore, .
It follows that the mapping becomes for .

As quantum logic gates are reversible, the action of a CNOT gate must be undone when/if a second CNOT is applied. Hence, the transformation  must be a bijective map that is its own inverse, so that there exits the involution for .

But, the polynomial in one variable  is irreducible over , namely, it always outputs 1 for equal to 0 or 1. Therefore,  requires some hidden variable for the state transformation  to be two-way.

This is exactly the core of the EPR paradox advocated by Einstein, Podolsky and Rosen, because, if a unitary operation needs one extra piece of information outside the reach of the binary system, then the quantum theory cannot be complete.

A. DeCastro

One Way Bijection Over GF(2)

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₂ = {0,1}. Let P1 be equal to x²+1 and P2 equal to x. The following are equivalent representations of the same value in a characteristic 2 finite field: Polynomial (P1): x²+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²+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 x²+x+1 is the irreducible polynomial in finite field GF(2), because x²+x+1 has no solution (try plugging in 0 or 1 to see). In other words, x²+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 x²+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²+x+1 is irreducible in the truth table of its XOR gate, x²+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.

State of the Art

There was a small flurry of cryptography theory papers last year addressing inputs obfuscation of varying form & degree as it relates to poly-span pre-image, correlated inputs, auxiliary inputs and deterministic public key schemes.

Most notable from my reading were, On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input by Garg, Gentry et al., along with, Poly-Many Hardcore Bits for Any One-Way Function and a Framework for Differing-Inputs Obfuscation, published by Bellare et al in September.

Those two papers seem to reach opposing conclusions or at least disagree as to the degree of obfuscation possible under certain pre-image & auxiliary input assumptions. That’s my take anyhow, please feel free to add any clarification?
Getting into the ‘meat & potatoes’ section of my paper, I have to dissect this theory and decide where & how I fit in?

On a more practical but no less complex level, I’m trying to understand the relative logarithmic, cryptographic ‘hardness’ of correlated bits at differing decimal place of significance. This is related to the function’s relaxation time to a fixed attraction point, or when inverted, the number of iterations needed to go ‘out of range’ on any given error magnitude.
If anyone could point me to a relevant function condition formula, thanks!

It’s the EOWFAWKI!

Modern cryptograpy is a sprawling subject and the latest illumination in my endless education is the existence of extractable one way functions, EOWF’s…
“A function f is extractable if it is possible to algorithmically “extract,” from any adversarial program
that outputs a value y in the image of f, a preimage of y.” : On the Existence of Extractable One-Way Functions. Bitansky et.al, May 2014.
That’s potentially bad news for my OWF as, if you’ve studied it, it’s obvious that any ‘within parameter’ guess of x yields a preimage x’. The good news is, the hash fn & trapdoor file in this OWF are obfuscated by virtue of each recieving only half of the stream identity. Some up-to-date discussion of obfuscation here: Poly-Many Hardcore Bits for Any One-Way Function and a Framework for Differing-Inputs Obfuscation Bellare et.al, Sept 2014. 
Additionally, even if an adversary guesses a preimage correctly, they still have to know the iterative private key. An in parameter guess may yield a trivial sequence of preimages but it’s a ‘Tar-Baby’ in terms of discerning where & when the sequence diverges. It’s diabolical & I don’t believe it can be ‘black boxed’ or even ‘non black boxed’ given its poly pre-image span and trapdoor obfuscation.
Comment and corrections welcome.
*Papers linked in Related-Useful archive.

Re-Write in the Offing.

I’m working up a re-write of my paper…
The working title is, “Forward Feed of Algorithmic Error Yields Trapdoor Permutation.”
I’ve learnt a fair bit over the past few months about the formal definitions of one-way functions and feel that I can better explain the composite morphology of the functions ‘injective-ness’, as well as explaining how this elicits ‘one-way-ness’.
It’d be nice to see this theory in a publishable form. Without getting too bogged down in cryptography & complexity theory, perhaps I can pitch it at such an expository level that it might fall within my capabilities? Then there’s the problem of referees…
As always, I’ll be looking for feedback, especially with regard correctness of formulae.
Phill.S

You Are Here;

Taking a moment to mull over morphism while contemplating a re-write…
I believe the hash function presented in the ‘One-Way‘ paper to be essentially, a binary modulated, fractionally iterated, derivative of a quadratic discriminant?
Algorithmic error is used as a ‘quantised’ form of  binary forward feed for the hash function.
(I’m not concerned with the pragmatics of this approach, yes it’s computationally intensive…)
How do you denote the morphism of a function which is ternary-surjective but also preserving of a binary structure?
The binary conservation of a single ‘bit’ by the hash function, effectively cancels out all but ‘half-a-bit’ of ternary ‘onto’ surjectiveness.
The trapdoor table then conserves the required ‘auxiliary-bit’ via indexing between lateral, L-R (deterministic) inheritance leaves and the middle (non-deterministic) leaf, where the binary hash identity is freed to encode an external bit.
Perhaps that Master-of-Morphism, J.A, would care to comment? How would you categorize and describe this hybrid cryptographic primitive? How do you describe the traversal of its informtion space? Does this all come under a new taxonomy of ‘Pseudo’-One-Way Functions?

Update: ‘Pidgin’ Formalism

Attempt made at clarification (or obfuscation?) of One-Way-Function paper.
Discussion/conclusion section added.
Comments welcome.

April Foolishness

Not the most auspicious date to post a draft pre-print for a mathematical paper you’d like to have taken seriously…
See paper; one.way.function