2
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Mar 4 '20 at 4:29
4
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ "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. $\endgroup$
    – Maeher
    Mar 4 '20 at 12:18
  • $\begingroup$ Shouldn't $a = b\ mod\ p$ be a one way function? Because, for any $a$ then $b = k \cdot p + a$. $\endgroup$
    – shumy
    Mar 4 '20 at 13:16
  • $\begingroup$ @shumy $a=b \bmod p$ is clearly not a OWF, since a itself is a preimage that's trivial to find. $\endgroup$
    – Maeher
    Mar 4 '20 at 13:55
  • $\begingroup$ 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? $\endgroup$
    – GEG
    Mar 4 '20 at 14:04
  • $\begingroup$ 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. $\endgroup$
    – Meir Maor
    Mar 4 '20 at 14:12

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.