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.)



Knot Diffie–Hellman
Here I assume that by “addition” of knots you mean the usual connect sum, as defined [here](https://en.wikipedia.org/wiki/Connected_sum#Connected_sum_of_knots). 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!


