10

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

Some references for anyone stumbling across this:
yoyo
  • 507
  • The algorithm to compute the connect-sum decomposition (and full satellite decomposition) of a knot in $S^3$ is either exponential or double-exponential run-time, as implemented in Regina. In practice it's quite quick, and you only run into the full "slow" computations rarely. I imagine you can find the proper run-time estimate in a paper of Ben Burton's. – Ryan Budney Mar 31 '24 at 03:03
  • One major difference between this proposal and finite-field Diffie-Hellman (FFDH) is that in FFDH the public key $(p,g)$ is a very different type of object than the secrets $(a, b)$, whereas here $P$, $A$, $B$ are all knots. This has a very concrete negative effect on your proposal, because it means that any knot invariant $I$ with nice connect-sum properties is likely to be unsuitable, since we can write something like the equation $I(P \oplus A \oplus B) = I(P \oplus A) + I(P \oplus B) - I(P)$ and get lots of information about the supposedly-secret value $I(P \oplus A \oplus B)$. – dvitek Mar 31 '24 at 16:50
  • I wonder whether replacing connect-sum with an operation like taking satellites would work better, though I don't know offhand whether an "iterated satellite knot" construction is sensitive to the order of the companion knots. (Even if iterated satellite knots are sensitive to the order of companions, this might not show up at the level of whatever invariant you pick.) This would largely sidestep the problem I mentioned above. – dvitek Mar 31 '24 at 17:03

2 Answers2

10

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!

Sam Nead
  • 26,191
  • Thanks for your answer. I edited the question with more pointed questions. In particular, could you elaborate if possible on the computational state-of-the-art and on the (in)ability to generate "hard instances?" – yoyo Jan 27 '23 at 20:41
  • Instead of editing your question (and me editing my answer, and etc, etc) may I suggest that you accept this answer, and post a new question? This will make both the question and answer easier to read. – Sam Nead Jan 27 '23 at 22:00
  • Perhaps you will be interested in this old post: https://mathoverflow.net/questions/53471/are-there-any-very-hard-unknots or in this one: https://mathoverflow.net/questions/68063/are-there-any-very-hard-unlinks – Sam Nead Jan 27 '23 at 22:10
  • 1
    Actually, if it's a modern web browser it's probably using elliptic curve groups rather than $\mathbb{Z}/pq\mathbb{Z}$ – Peter Taylor Jan 28 '23 at 00:29
  • 1
    (Well, the TLS for this page is currently TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, so ECC and RSA are both represented, soon to be deprecated in favor of PQC, hence the question. The PQC landscape is quite lacking in diversity.) I'll gladly accept your answer if you can provide exposition or references for your claims of "methods... that seem to work very well in practice" and "do not know how to produce 'hard instances'." Any references for computation knot theory are welcome I suppose. – yoyo Jan 31 '23 at 01:24
  • I provided some mathoverflow posts in my comment above. There you can find many of the ideas regarding algorithms (that is, upper bounds). In addition to these methods, there are also implementations, in the form of Snappy and Regina. The latter has been used to find the complete list of knots with at most 20 crossings (there are about 8 billion of them!). – Sam Nead Jan 31 '23 at 21:10
  • Finally, here is a link to a paper that discusses old and new "hard instances": https://arxiv.org/abs/2104.14076 ... However, these instances are actually not very hard; the given diagrams (of the unknot) can be simplified after adding at most three crossings. – Sam Nead Jan 31 '23 at 21:13
5

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.

  1. Alice computes $p'=sps^{-1}$ and sends it to Bob.
  2. Bob computes $p''=rpr^{-1}$ and sends it to Alice.
  3. Alice computes $t_A=sp''s^{-1}.$
  4. 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.

kodlu
  • 10,131
  • 2
  • 34
  • 53