Examples of NP Complete key exchange algorithms There's a number of questions on the internet (this site and others; e.g. Why hasn&#39;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.
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&#39;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.