10
$\begingroup$

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:
Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Ryan Budney
    Commented Mar 31 at 3:03
  • $\begingroup$ 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)$. $\endgroup$
    – dvitek
    Commented Mar 31 at 16:50
  • $\begingroup$ 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. $\endgroup$
    – dvitek
    Commented Mar 31 at 17:03
  • $\begingroup$ For more general thoughts along these lines see a 2018 paper of Partala, "Algebraic generalization of Diffie–Hellman key exchange". $\endgroup$
    – dvitek
    Commented Apr 1 at 0:42

2 Answers 2

Reset to default
10
$\begingroup$

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!

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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?" $\endgroup$
    – yoyo
    Commented Jan 27, 2023 at 20:41
  • $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Commented Jan 27, 2023 at 22:00
  • $\begingroup$ Perhaps you will be interested in this old post: mathoverflow.net/questions/53471/… or in this one: mathoverflow.net/questions/68063/… $\endgroup$
    – Sam Nead
    Commented Jan 27, 2023 at 22:10
  • 1
    $\begingroup$ Actually, if it's a modern web browser it's probably using elliptic curve groups rather than $\mathbb{Z}/pq\mathbb{Z}$ $\endgroup$
    – Peter Taylor
    Commented Jan 28, 2023 at 0:29
  • 1
    $\begingroup$ (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. $\endgroup$
    – yoyo
    Commented Jan 31, 2023 at 1:24
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Link to the published version: Dehornoy - Braid-based cryptography. $\endgroup$
    – LSpice
    Commented Jan 26, 2023 at 18:05
  • 3
    $\begingroup$ The conjugacy problem in a fixed braid group (and more generally a fixed mapping class group) is now known to be polynomial time. The constants are terrible (they depend on the number of strands). But that will probably not be enough to save this idea…. $\endgroup$
    – Sam Nead
    Commented Jan 26, 2023 at 19:36
  • 1
    $\begingroup$ @SamNead, interesting. Do you have a reference $\endgroup$
    – kodlu
    Commented Jan 26, 2023 at 20:09
  • $\begingroup$ birs.ca/events/2021/5-day-workshops/21w5094/videos/watch/… $\endgroup$
    – Sam Nead
    Commented Jan 26, 2023 at 20:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .