If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption algorithms? Do any such algorithms already exist?
Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure Communications over Insecure Channels" by Ralph Merkle, where he proposed to use “puzzles”. This is a key agreement protocol.
- Alice sends $n$ encrypted messages (called puzzles), each containing a unique identifier $I_i$ and a session key $K_i$, with the keys for each messages chosen among a set of $n$ keys. This takes $O(n)$ time ($O(1)$ per message).
- Bob decrypts one of the messages by brute force and sends back $I_i$ encrypted with $K_i$. This takes $O(n)$ time ($O(1)$ per key, times $n$ possible keys).
- Alice tries all the keys to decrypt the message. This takes again $O(n)$ time.
Each party requires only $O(n)$ computation, but an eavesdropper who wishes to find $K_i$ needs to try out half the puzzles on average to calculate the right key (the eavesdropper does not know which message Bob chose to decrypt), so the eavesdropper requires $\Theta(n^2)$ computation on average.
The problem with Merkle puzzles, or anything where the amount of work to be done by the attacker only increases as the square of the legitimate party, is that it takes huge key sizes and amounts of computation to achieve a decent security margin.
In any case, it is not clear that merely proving that P=NP will invalidate existing cryptographic algorithms. If the polynomial increase is a high enough power, it might not matter so much in practice. See How will security need to be changed if P=NP?, Can we say that if P=NPP=NP there is no CPA secure public key encryption?, P = NP and current cryptographic systems, …
A One Time Pad is secure regardless of complexity, as long as your numbers are truly random.
Even if you can try every key quickly, it's useless because this will reveal every possible message, and there's no way to know which one was the desired one.
For what you describe, if the analysis only took the square of the encryption time, it would be considered insecure by modern standards. Encryption needs to happen in seconds or even less , so a quadratic increase would allow messages to be decoded in a few hours.
protected by Community♦ Apr 28 '16 at 17:44
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?