🚀 go-pugleaf

In article <PHR.92Nov15203840@napa.telebit.com>, phr@telebit.com (Paul Rubin)
writes:
> ... It is true that if P=NP then all cryptography everywhere (not just RSA)
> is dead...

Actually, this is false.  If P=NP, then PUBLIC KEY cryptography is dead; but
private key cryptography can, in principle, be much stronger.  It can, in
fact, be arbitrarily strong.

The problem for public-key cryptography is that, given a ciphertext and the
public key, I can guess private keys and check that I've got the right one in
polynomial time by simply encrypting my proposed plaintext with the public
key.  If I get the ciphertext back, I've got the key.

For private-key cyptography, I can guess all I like, but there's no way I
can test the correctness of my guess with certainty.  Sure, as a PRACTICAL
matter, I may have some known plaintext, or i can just recognize that I
got English text back.  But we're not talking about "in practice" here.

Note that for a one-time pad, the system is unconditionally secure, even
given the ability to compute non-computable functions.

							-- Jerry