When I attended university, there was one class that defied all of my expectations: Theory of Computation.

First of all, it did not have much theory. Second, it had a lot of applied math. Third, I expected it to be useless, but I came out of that class with two fantastically important things.

This post is about the first: a math problem that annoyed me.

The problem was the P versus NP problem, a problem that was ostensibly so important that it has a million dollar bounty.

And yet, it hasn’t been solved yet.

Since I was young, naive, and cash-strapped college student, the P v NP problem intrigued me. I spent spare brain cycles on it.

Over time, I graduated, started working, got married, and generally became less cash-strapped. So I didn’t care about the million dollars anymore.

But…

It still annoyed me. P v NP is central to knowing the soft limits of computers. It seemed like there was a hole in the bottom of computer science, and there are a lot of obviously smart people in computer science who could do something about it but just…didn’t.

Why wasn’t it solved?

I still spent spare brain cycles on it.

But then I ran into an even larger problem.

You see, I started studying cryptography because I wanted to be a Level 3 cryptographer.

I learned a lot (and am still learning), but I quickly found out that, like computer science, cryptography had a hole in its foundation.

Except that this time, it wasn’t just a hole; there was no foundation at all!

The problem is this: no one knows if one-way functions exist.

This may not seem like a big deal, but it’s everything.

First of all, if one-way functions exist, then P ≠ NP, so proving the existence of one-way functions would solve the P v NP problem.

Second, all of cryptography assumes one-way functions exist.

Wat.

Cryptography didn’t start out with a lot of proofs, but it has grown that over time.

Just about every proof in cryptography has assumptions.

The vast majority are practical. Most of them are about that attacker’s power/abilities. Some are about the lack of information leaks elsewhere. A few might be more about mathematical axioms.

And underlying them all is an implicit assumption: that there are some functions that cannot be easily reversed without some specific knowledge.

That’s right; we don’t know if cryptography actually works. It may not, and the NSA might be laughing at us as they read everything.

Why does this matter?

Well, if any computable function could be easily reversed, for some definition of “easy,” then it doesn’t matter what you encrypt; the attacker can just reverse the mathematical function of encryption without the specific knowledge you have: the key.

Voilà! No encryption is effective.

It’s a terrifying prospect to contemplate.

And yet, we have based our modern economies on this assumption. The world depends on cryptography!

You could not safely move money over the Internet without it. You could not keep your information safe. You could not keep governments at bay.

That’s why this problem annoys me: everything depends on it.

I want someone to prove one-way functions exist, and I want it done in such a way that we could make unbreakable cryptographic primitives by construction.

I know, I’m a dreamer.

I’m also spending spare brain cycles on the problem, even though I’m stupid.

But why am I tackling this problem instead of the easier P v NP problem?

Because I think it might be easier to solve.

Honestly, it’s probably because of my stupidity that I think proving one-way functions exist may be easier than cracking the P v NP problem.

But I see P v NP as more difficult because if P ≠ NP, you need to prove that there is no algorithm to solve an NP problem quickly. That’s gobs harder than finding one counterexample.

Solving the one-way functions problem would entail finding one, just one counterexample: a function that cannot be reversed without knowing all or some of the original inputs, for all possible inputs.

This sounds hard, but there’s already an example of solving this kind of problem: Alan Turing and the Entscheidungsproblem.

Alan Turing proved that some functions are not computable. He proved that some functions will cause a computer, a Turing Machine, to never halt.

“Well, that’s all good. Doesn’t that prove that one-way functions exist?”

No. Uncomputable functions are impossible for the attacker and the defender!

We need a function that is computable for defenders and impossible for attackers.

But I think that’s the key: if someone could construct a reversible Turing Machine that will halt in reverse when given the right input(s), but never halt when given the wrong input(s), that could be a great first step to proving that one-way functions exist.

The second and final step would be to prove that there cannot exist a Turing Machine that could return the correct input(s).

Yes, this is like what is required for proving the P v NP problem, but I think it will be easier because the Turing Machine could be constructed in a way to make it impossible to compute the function any other way by ensuring that all candidate Turing Machines never halt.

In other words, I believe we can customize the Turing Machine to the proof to make it easier.

Now, why am I giving away my current thoughts, even if it means someone beats me to a million dollars?

Because it probably won’t work.

But also because I want this proven!

Go ahead, use my ideas! Prove that one-way functions exist! Please!

I want this mind virus gone!