There's a number of questions on the internet (this site and others; e.g. Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? ) discussing NP hardness of different asymmetric cryptosystems. How well established are NP hard key-sharing systems? That is, systems for establishing a shared key (that can then by used in symmetric encryption) that are based on problems that are known to be NP hard.

I was prompted to this question upon reading about https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld_key_exchange and wondering if it could be shown to be NP complete when implemented on $GL_n(F_2)$ or $GL_n(\mathbb{R})$, cause these look like awfully hard constraint-satisfaction or quadratic optimization problems at a first glance. The corresponding problem this is based on is the Simultaneous Conjugacy Problem.

I'm aware that there is an important distinction between problems that are merely NP hard in the worst case -- but easy on most random instances, as opposed to problems that are "average-case NP" -- given a set of random instances, solving half of them is still hard. I'd be interested in hearing about key-sharing systems that rely on either notion of hardness.

  • 1
    $\begingroup$ Algorithms can not be NP-hard; it's a property of problems. $\endgroup$ – Raphael Aug 19 '16 at 4:36
  • 1
    $\begingroup$ Right, I mean the NP hardness of breaking the corresponding protocols. In the case of AAG then this corresponds to the Simultaneous Conjugacy Problem (which is known easy on some groups such as the symmetric group, and believed hard on others such as braid groups) $\endgroup$ – Alex Meiburg Aug 19 '16 at 4:38
  • $\begingroup$ Please define what you mean by a "key-sharing system". Are you talking about public-key key exchange, e.g., Diffie-Hellman and the like? $\endgroup$ – D.W. Aug 19 '16 at 5:36
  • 1
    $\begingroup$ Yes, a protocol (not necessarily authenticating) that allows to parties to arrive a key known (ideally) only to the pair of them, that can then be used in further encrypted communications e.g. AES $\endgroup$ – Alex Meiburg Aug 19 '16 at 6:13

There are no known public-key cryptographic algorithms that have been proven to be NP-hard to break. None. So we can't provide you examples, because none are known.

Answer to your original question:

The analysis at Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? also applies to public-key exchange.

Cryptography requires average-case hardness. NP-hardness relates to worst-case hardness; it has no notion of a distribution on inputs, probability, or any kind of "average". Worst-case hardness does not appear to imply average-case hardness: there are many problems that are believed to be hard in the worst case, but easy in the average case. Status of Impagliazzo's Worlds? has some pointers on this topic.

| cite | improve this answer | |

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.