Knot Diffie–Hellman Here's an idea for a knot-based Diffie–Hellman exchange:

*

*Public:  random (oriented) knot $P$.

*Private:  random (oriented) knots $A$ and $B$.

*Exchange:  Alice sends (randomized or canonical representation of) $A'=A\oplus P$, Bob sends (randomized or canonical representation of) $B'=P\oplus B$.  Here $\oplus$ is knot connected sum.

*Shared key:  (invariant of) $A\oplus P\oplus B=A\oplus B'=A'\oplus B$.

Questions:

*

*Why is this a good/bad idea?  References?

*What is the complexity of solving $P\oplus X=X'$ for $X$ given $P$ and $X'$?  Is factoring knots difficult?

*What are good digital representations of knots?  How to efficiently generate and randomize knot representations?  (E.g., Gauss codes and Reidemeister moves?)  "Diffusing" the sums $A'$, $B'$ (randomly or to some canonical form) would be important for security, assuming factoring is hard in the first place.

*What is a good choice of invariant in the last step?  Should be efficient to compute for Alice and Bob but infeasible knowing $P$, $A'$, and $B'$.

*If this makes sense, can it be done in reasonable space/time (e.g. $n\log n$ diagram storage for $n$ crossings, obfuscation/diffusion, final invariant computation)?

TL;DR:  Could the knot monoid be useful for public key cryptography?  Is connected sum of knots one-way, even knowing one of the factors?  Do random planar projections obfuscate knot factorizations?

EDIT:  To make this question more pointed, given a "random" planar projection of a "random" knot with $n$ crossings, I would like to know:

*

*First, what are good notions of random above?

*What is the distribution of factors of such a random knot, e.g. is it mostly filled with trefoils and other small knots?

*What computational methods are used to factor knots?

*What are some bounds for space/time complexity of such methods (as a function of $n$)?

*What is the "average" complexity (at least intuitively or in practice)?

*For the envisioned cryptographic purposes, $n$ on the order of 1000 or 10000 might be of reasonable size.  Where does this stand in regards to current computational capabilities?

Abandoning uniformly random instances, what is the state of producing hard instances?  (One of the answers states that this is currently infeasible.)
 A: Here I assume that by “addition” of knots you mean the usual connect sum, as defined here.  With that said, I think you correctly ask the relevant question: “Is factoring knots difficult?”
In favour of your idea is the fact that we do not (yet?) have a polynomial-time algorithm to factor knots.  Against your idea is the “issue” that there are methods (normal surface theory, sutured manifolds) that seem to work very well in practice.  Furthermore, we (well, three-manifold topologists) do not know how to produce “hard instances”.  Thus your proposal is probably a “bad idea”. :(

This should be compared to the situation of factoring numbers.  There we really don’t have good general techniques (disregarding quantum algorithms…).  Also, we have so many hard instances that your web browser is using one right now!
A: Edit: Thanks to @SamNead, for pointing out that the conjugacy problem is polynomial time, albeit with horrible constants. See video here
There is some literature on Braid group cryptography.
Here is an online preprint of a survey article Braid-based cryptography by Patrick Dehornoy which appeared in AMS' Contemporary Mathematics series, Vol. 360 in 2004, see link here.
In a scheme described on pp. 8–9 subgroups of Braid groups which commute are used to define a Diffie–Hellman cryptosystem.
The public key is a braid $p$ in a braid group $B_n$. Alice's secret key is a braid $s$ in $LB_n$ and Bob's secret key is a braid $r$ in $UB_n$. Here $LB_n$ and $UB_n$ are subgroups of $B_n$ where every element in one commutes with every element in the other, enabling the Diffie–Hellman scheme.

*

*Alice computes $p'=sps^{-1}$ and sends it to Bob.

*Bob computes $p''=rpr^{-1}$ and sends it to Alice.

*Alice computes $t_A=sp''s^{-1}.$

*Bob computes $t_B=rp'r^{-1}.$
$t_A=t_B$ is the common shared key. The specific hard problem is the following conjugacy problem:
Given the braids $p$, $p'$, $p''$ as above find $rp'r^{-1}$ (equivalently find $s p''s^{-1}$).
Tables I and II give some difficulty estimates for this problem. Perhaps a search through articles citing this may yield newer results or related system.
