$P \ne NP$: a proof relating complexity theory to block ciphers

Question

I started thinking about P vs NP after reading another question on this stack exchange. Here I propose a proof that relates P vs NP to the existence of a secure block cipher in the elf model.

Let's say I have a (normal) Turing machine and I want to model a nondeterministic machine with it. According to certain models, a nondeterministic Turing machine can branch at each decision to multiple instances of itself. If I have an input $N$ of $n$ bits, let's say I must make a decision for each of $n$ bits: that's $2^n$ possible branches, operating in parallel. Since a normal Turing machine must loop through every state of $N$, operating on each independently, wouldn't that mean $P \ne NP$ since I can construct a problem in $NP$ which requires me to operate on all possible $N$.

If we consider a an ideal block cipher we can say there exists a construction which requires you to operate on every possible input (consider the elf model). In the elf model, one must either form a lookup table of the entire mapping ($2^b$ blocks where $b$ is the block size) or iterate on every possible block. Therefore, if there exists a secure mode of operating on multiple blocks in the elf model, there must exist a problem in $NP$ which cannot be performed without iterating over every possible $N$. Since secure modes of operations are known to exist (if a secure block cipher exists), and the elf model proves a secure block cipher exists, this would prove $P \ne NP$.

If I can create a cipher which requires me to solve a cipher with a smaller block size (a perfect block cipher), I can force the decision to depend on every input bit, making the security rely only on obtaining perfect diffusion among the possible states, which many ciphers do already. This way I can create a secure block cipher from another secure block cipher, of smaller block size. Effectively, every SP-network is proof that $P \ne NP$.

Is this valid, or is there anything I'm missing? Is there anything unclear about my reasoning?

Answer 1

and the elf model proves a secure block cipher exists

It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally stronger settings. For example, there are lower bounds of $\Omega(\sqrt{|G|})$ on DL in the generic group model. This does not prove that DL is hard in "real life" though (and in fact, finite-field discrete log has $o(\sqrt{|G|})$ algorithms).

Secure block ciphers are not known to exist unconditionally. I don't know if your post precisely says this anywhere (this is the impression I get of the insight of your post though), but a proof that a secure block cipher exists immediately proves that $\mathsf{P}\neq \mathsf{NP}$. This is because:

1. Secure Block ciphers are Pseudo-Random Permutations (PRPs)
2. PRPs imply One-Way Functions (is this HILL89? Idk its one of those old results)
3. The existence of One-Way Functions directly shows $\mathsf{P}\neq\mathsf{NP}$ (the problem of inverting a poly-time computable function is easily shown to be in $\mathsf{NP}$. The function being one-way means this can't be done in $\mathsf{P}$, and therefore we've found an $\mathsf{NP}$ language which is not in $\mathsf{P}$.

---

[1] There are areas of complexity theory which try to do exactly this though. Look up "lifting theorems" in communication complexity in particular, where lower bounds in weak models (generally things like decision trees) are "lifted" to lower bounds (for slightly different problems generally) in stronger models. This all being said, I do not expect lifting theorems to be useful for your application.