If P=NP, are there cryptosystems that would require n^2 time to break?

Problem Detail: 

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?

Asked By : S.LAKSHMINARAYAN

Answered By : Gilles

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.

1. 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).
2. 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).
3. 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.

After Merkle invented his puzzles, Diffie and Hellman published a key agreement protocol based on the discrete logarithm problem. This protocol is still used today.

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, …

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56662