# Why does the one-time pad not imply $P \not= NP$?

I apologize that this is a rather trivial question, but I haven't been able to find an answer anywhere. If the one-time pad is unconditionally secure and impossible to crack (with just ciphertext), why does this not imply $$P \not= NP$$? If not the one-time pad, what properties would a cryptographic system need to exhibit in order to imply $$P \not= NP$$?

• What properties? Well, one possibility would be that a decision problem associated with the cryptographic system be provably within NP, and provably not within P. – poncho Mar 4 '20 at 4:29

A one time pad is secure regardless of complexity. When you have a ciphertext all plaintexts are equally likely and you have no way to verify a guess. Even an attacker which enumerates all possible keys will not learn anything he didn't know already. Thus it doesn't have anything to do with complexity.

A one way function on the other hand implies $$P \ne NP$$. Any function which is easy to compute in one direction but hard to find a pre image. Since finding a preimage of a polynomial time function is in $$NP$$.

Note it is possible that no one way functions exist and and still $$P$$ does not equal $$NP$$.

A one time pad is not a one way function. It is trivial to find a preimage We can find as many preimages as we want we can't tell them apart.

• "Since finding a preimage of a polynomial time function is in NP." Strictly speaking that's not true, since a search problem cannot be in NP. The corresponding decision problem is in NP though. – Maeher Mar 4 '20 at 12:18
• Shouldn't $a = b\ mod\ p$ be a one way function? Because, for any $a$ then $b = k \cdot p + a$. – shumy Mar 4 '20 at 13:16
• @shumy $a=b \bmod p$ is clearly not a OWF, since a itself is a preimage that's trivial to find. – Maeher Mar 4 '20 at 13:55
• I am unclear what you mean by it is easy to compute a preimage. Do you mean it is easy because we just pick a random key and random message and they look the same? – GEG Mar 4 '20 at 14:04
• If we look at the encryption as a function it's input is both message and key, and for any cipher text we can produce any number of plaintext,key pairs to match the ciphertext. – Meir Maor Mar 4 '20 at 14:12