Skip to main content
1 of 6
yoyo
  • 609
  • 3
  • 10

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$.
  • 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?

yoyo
  • 609
  • 3
  • 10