Return to Question

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

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

• Someone suggesting something similar: Knot-based Key Exchange protocol
• A a nice survey of random knots: Models of Random Knots

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, i.e. primality testing for knots? (One of the answers states that this is currently infeasible.)

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

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?

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, i.e. primality testing for knots? (One of the answers states that this is currently infeasible.)