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?

  • 6
    $\begingroup$ This question appears to be copied word-for-word from Quora, right down to the grammar error ("possible do design"). This amounts to plagiarism, which isn't cool and is not welcome on this site. Remember to always add prominent attribution when using other sources. $\endgroup$
    – D.W.
    Apr 29 '16 at 0:20
  • 1
    $\begingroup$ Also, we're looking for questions that are written in your own words -- they should be more than a copy-paste of material available elsewhere. We don't want to just be a place that copy-pastes entire questions or answers from Quora. It's fine to use small quotations from elsewhere, if you indicate clearly which part is a quotation and link to the source and credit the source, but the majority must be your own content. See also cs.stackexchange.com/help/referencing and stackexchange.com/legal. $\endgroup$
    – D.W.
    Apr 29 '16 at 0:22
  • $\begingroup$ n^2 is in P. So P=NP does not affect the answer to the question. $\endgroup$
    – Taemyr
    Apr 29 '16 at 8:32

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

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – D.W.
    Apr 29 '16 at 0:16


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.

  • 3
    $\begingroup$ There is no cryptanalysis algorithm for OTP, let alone an optimal one. The question was specifically about that, not whether any secure encryption would be possible. $\endgroup$
    – OrangeDog
    Apr 28 '16 at 21:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.