Skip to content

Instantly share code, notes, and snippets.

@defeo
Last active November 7, 2021 09:52
Show Gist options
  • Star 14 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save defeo/163444a53252ba90cca6a3b550e6dd31 to your computer and use it in GitHub Desktop.
Save defeo/163444a53252ba90cca6a3b550e6dd31 to your computer and use it in GitHub Desktop.
Key exchange in supersingular space-time

Key exchange in supersingular space-time

I was asked to vulgarize SIDH. Here is a very poor attempt!

Alice and Bob are space travelers. They both own a spaceship capable of traveling the galaxy through supersingular space-time at incredible speeds. They want to discuss a top-secret space mission, but they are afraid that the evil Zkptrx will spy upon their conversation, so they decide to meet on a secret planet. But how to agree on a secret planet while the evil Zkptrx are listening?

Supersingular space-time

Supersingular space-time¹ has a very peculiar structure: it is a complex network of high-speed links² connecting planets³ very far apart. Supersingular space-time is so huge that no one has ever mapped even the tiniest portion of it. It contains more than 10²⁰⁰ (a googol googols) planets, and every planet has infinite amounts of supersingular links connected to it.

However, not all supersingular links are born equal. Links have quantized energy levels⁴, that we measure in quanta (q). The higher the energy level, the more links in that level a planet will have, the more energy is needed to travel through one such link. For practical reasons, spaceships are often engineered to only travel on a very limited range of levels. For example, Alice's spaceship is currently tuned to only travel on 2q links, while Bob has tuned his to only travel on 3q links. Every planet has exactly three 2q links and four 3q links to other planets in supersingular space.

Classical, or even relativistic, distance⁵ has absolutely no bearing on energy levels: a 2q link from Earth may go to Mars as well as to a planet a million light years away. From a planet's perspective, apart from the energy level, there is nothing that tells one link from another: every 2q link looks essentially the same, and it is impossible to know where it goes until you take it.

To avoid getting lost, supersingular travelers use torsion transponders⁶. When a torsion transponder is activated at a location, it gives an orientation to the nearby supersingular space-time (nearby in terms of supersingular links, not in terms of classical distance!). By communicating with his transponder, a supersingular traveler knows which way is back, and can also give an orientation to the other supersingular links. For example when Alice is on a planet and prepares to go through one of the three 2q links, by communicating with her transponder on Earth she knows which link takes her back, and she can also name the two other links "left" and "right" in a reliable way that depends only upon the transponder settings.

Transponders are cheap and easy to manufacture, but they have several limitations. For one, they can only be activated on a single energy level. A transponder activated on an energy level, cannot travel through links of that same level without being destroyed; it can, however, travel through links of other energy levels, while retaining its settings and preserving orientation of its own level. More importantly, transponders only work over very limited (supersingular) distances: only a few hundred links away or so.

For the benefit of supersingular travel, the National Anabelian Supersingular Administration (NASA) constantly keeps activated on Earth public transponders for the most common energy levels. Any supersingular traveler can synchronize his own transponders on NASA's ones free of charge.

The SIDH protocol

Given the properties of supersingular space-time, Alice and Bob agree on the following protocol to meet at a secret location in the galaxy.

  1. Alice synchronizes her 2q transponder on NASA's, activates it and gives it to Bob.
  2. Bob does the same with his own 3q transponder.
  3. Alice leaves Earth on 2q links, maintaining contact with NASA's transponder to track her way. She never takes a link back to Earth; instead, at each new planet she takes note of what link (left or right) she is taking, and goes as far as the transponder allows her to do. When she stops, she radioes to Bob her astral coordinates, and leaves Bob's transponder where she has arrived.
  4. Bob does the same on 3q links. He takes note of his left, right and middle steps, then radioes his coordinates to Alice and leaves her transponder there.

Because Alice and Bob are most likely at two very distant points in the galaxy, their radio communication must be very strong. So, at any rate, the evil Zkptrx have listened to the broadcast and know where Alice and Bob are. However, they do not know which supersingular routes Alice and Bob took, nor can they guess it from the astral coordinates. That's the key to the protocol, which proceeds as follows.

  1. Upon receiving Bob's coordinates, Alice travels there using plain old hyperspace⁷ (more expensive and not as cool as supersingular space-time, but still effective).
  2. Bob travels through hyperspace to Alice's coordinates.
  3. Alice finds her transponder at Bob's coordinates. She starts traveling through 2q links, maintaining contact with her own transponder. She repeats exactly the same sequence of left and right steps she did in the first part.
  4. Bob does the same, repeating his sequence of left, right and middle steps starting from Alice's coordinates.

Because of the physics of supersingular space-time, if Alice's and Bob's transponders were synchronized correctly at the beginning, they will both end up on the same planet. The evil Zkptrx will know where Alice and Bob started from, and will even know how the transponders were set up (they were synchronized on NASA's public transponders, after all), but not knowing the sequence of left, right and middle steps they will be unable to find the final planet.

The whole security of the protocol relies on this last assumption: given the astral coordinates of Earth, and of Alice's (or Bob's) arrival planet, the evil Zkptrx are unable to find a path through supersingular space that goes from one to the other. As far as we know, neither the evil Zkptrx, nor anyone, has the technology to accomplish such a feat. Will you be the first to invent such technology?


footnotes for the mathematician

¹ Yes, that's a supersingular isogeny graph.

² Isogenies.

³ Supersingular elliptic curves (or, more precisely, j-invariants).

⁴ That's the degree of an isogeny.

⁵ For example, Hamming distance on the j-invariants.

⁶ Bases of prime-power-torsion of elliptic curves.

⁷ This is the worst analogy of all: in SIDH moving to a different curve is free, while here hyperspace travel sounds like something very expensive compared to supersingular travel.


Creative Commons License
Key exchange in supersingular space-time by Luca De Feo is licensed under a Creative Commons Attribution 4.0 International License.

@ineiti
Copy link

ineiti commented Oct 11, 2016

As far as I understood, making a copy of the transponders doesn't help the Zkptrx. They would need to know the route Alice and Bob will take once the transponders are picked up.

But how is this different from Diffie-Hellmann? Besides using another Group/Field/whatever?

@liamsi
Copy link

liamsi commented Oct 16, 2016

But how is this different from Diffie-Hellmann? Besides using another Group/Field/whatever?

@ineiti: In SIDH you are still doing (some slightly modified form) of Diffie-Hellman (Supersingular Isogeny DH ;-). That's why it might look so similar.
As far as I understood the main differences are structural differences. Without going into any details: instead of receiving and sending curve points (like in ECDH) in SIDH you deal with whole groups/curves in "isogney classes". Also, you don't try to hide scalars (like in ECDH) but instead your secret keys are isogenies (which are maps between curves/groups).
Last but not least, the hard problem (Zkptrx can't solve yet) is not finding a discrete log (or it's elliptic curve version) but rather, given a curve and its image under the isogney, finding the isogney that was used to produce that image.
Does that help?

@schancel
Copy link

Bob does the same, repeating his sequence of left, right and middle steps starting from Alice's coordinates.

Should this note that Bob uses 3q links? Or does he really use 2p links?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment