7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Algorithms can not be NP-hard; it's a property of problems. $\endgroup$
    – Raphael
    Commented Aug 19, 2016 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
    Commented Aug 19, 2016 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. ♦
    Commented Aug 19, 2016 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
    Commented Aug 19, 2016 at 6:13

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0

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