2
$\begingroup$

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?

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ The main point of my reasoning is that secure block ciphers can be proven to exist according to the elf model, and can therefore be extended into larger block ciphers. $\endgroup$ – Serpent27 Sep 28 '20 at 1:28
  • $\begingroup$ @Serpent27 You haven't mentioned how you conclude "secure block ciphers exist outside of the elf model", which I imagine is the barrier in this proof working. I'm unfamiliar with the elf model, but conceptually this is the part of the proof which seems like the "magic happens here" part. If you can show this magic happens, great! But given the difficulty in showing $\mathsf{P}\neq \mathsf{NP}$, it is the part I imagine where difficulties would arise. $\endgroup$ – Mark Sep 28 '20 at 1:30
  • $\begingroup$ blog.cryptographyengineering.com/2013/04/11/… $\endgroup$ – Serpent27 Sep 28 '20 at 1:31
  • 3
    $\begingroup$ It is not. In general the complexity of breaking a block cipher cannot be much bigger than $2^k$, where $k$ is the key size. Regarding 2. in the answer: I don't think it's HILL, HILL shows OWF -> PRG. I think that PRP -> OWF is just folklore and easy. $\endgroup$ – Geoffroy Couteau Sep 28 '20 at 11:11
  • 2
    $\begingroup$ @Serpent27 The last comment outside the boundaries of polite conversation so I've removed it. $\endgroup$ – Maarten Bodewes Oct 6 '20 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.