Skip to main content

Section 3.2 Supersingular isogeny graph cryptography (Asra)

Supersingular isogeny graph crypto is a candidate for post-quantum crypto, not based on factoring etc.

Recall last time we defined Ramanujan graphs, graphs with very good connectivity properties, a type of expander.

Upshot: supersingular isogeny graphs are \((l +1)\)-regular, undirected, Ramanujan, connected (technically, Ramanujan means connected already, but its worth emphasising).

Some of our algorithms are only dependent on having a graph with this property, not so much the interpretation in terms of isogenies.

Supersingular isogeny graphs first appeared in crypto as potential hash functions.

Subsection 3.2.1 Hash functions

(2010) (Charles, Goren, Lauter) proposed a cryptographically secure hash function based on the hardness of computing paths in a supersingular isogeny graphs.

Definition 3.2.2. Hash functions.

A hash function is a deterministic function \(h\colon \{0,1\}^* \to \{0,1\}^n\text{.}\)

Definition 3.2.3. Collision resistance.

A hash function \(h\) is collision resistant if its hard to find \(x_1,x_2\) with \(x_1\ne x_2 \) s.t. \(h(x_1) = h(x_2)\text{.}\)

Definition 3.2.4. Preimage resistance.

A hash function \(h\) is preimage resistant if given \(y\in \{0,1\}^n\) its hard to find \(x\) s.t. \(h(x) = y\text{.}\)

Cool example, private set intersection, say two groups, Starbucks and BU want to find a list of common customers (students who bought something at Starbucks) but don't want to reveal anything to each other about the students or customers not in the intersection. Compute hashes of the names of customers and share the hashes, can compute the size of, and the intersection itself.

Subsection 3.2.2 Supersingular isogeny hash functions

Parameters.

\(G_l(\FF_{p^2})\text{,}\) \(p \equiv 1 \pmod{12}\text{,}\) \(l\) to be small, fix an ordering on the edges, fix an initial vertex \(j_0\) and an incoming edge.

Protocol.

\(m \in \{0,1\}^*\) write this as an \(l\)-bit string, \(m \in \{0,1,\ldots, l-1\}^*\text{,}\) walk the graph based on \(m\) without backtracking.

Map the final \(j\) invariant to \(\{0,1\}^{n\approx \log p}\text{.}\)

Properties.

Difficult means exponential in the size of the input normally.

Subsection 3.2.3 Diffie-Hellman Key Exchange (1976)

Choose \(p,\, \ZZ/p, g\) then Alice computes \(g^a\) send to Bob, he computes \(g^b\) and sends it back, they both compute \(g^{ab}\text{,}\) which is their shared secret.

The security is based on the hardness of computing \(g^{ab}\) given \(g^a,g^b\text{.}\)

Subsection 3.2.4 Supersingular isogeny Diffie-Hellman (SIDH)

Parameters.

Supersingular elliptic curve of smooth order: fix \(p\) to be big enough \(p = l_A^{e_A} l_B^{e_B} f \pm 1\text{.}\) \(l_A,l_B\) small primes, \(f\) is a number chosen such that \(p\) is big. Construct a supersingular elliptic curve \(E\) such that \(\# E(\FF_{p^2}) = (l_A^{e_A}l_B^{e_B} f)^2\text{,}\) using Broker's algorithm.

Construct bases \((P_A, Q_A)\) for \(E\lb l_A^{e_A}\rb\text{,}\) \((P_B, Q_B)\) for \(E\lb l_B^{e_B}\rb\text{.}\)

Protocol.

Alice takes \(m_A,n_A \in \ZZ/l_A^{e_A}\)

Bob takes \(m_B,n_B \in \ZZ/l_B^{e_B}\)

Alice finds \(R_A = m_AP_A + n_AQ_A\)

Bob finds \(R_B = m_BP_B + n_BQ_B\)

Alice finds \(\phi_A \colon E \to E/\langle R_A\rangle = E_A\)

Bob finds \(\phi_B \colon E \to E/\langle R_B\rangle = E_B\)

They send each other \(E_i, \phi_i(P_i),\phi_i(Q_i)\text{.}\)

Both compute \(\phi'_A\colon E_B \to E_B/\langle m_A\phi_B(P_A) + n_A\phi_B(Q_A)\rangle\) or analogous.

Shared secret is \(j(E_{AB})\text{.}\)

Hardness.
  1. (Decisional supersingular isogeny problem) Given \(E, (P_A,Q_A)\) a basis for \(l_A^{e_A}\) torsion, let \(E_A\) be another curve, is \(E_A\) \(l_A^{e_A}\) isogenous to \(E\text{?}\)
  2. (Computational supersingular isogeny problem) Let \(\phi_A \colon E \to E_A\) be an isogeny with a kernel of the form \(\langle m_AP_A + n_AQ_A \rangle\text{.}\) Given \(E_A\) and \(\phi_A(P_B)\) \(\phi_A(Q_B)\text{,}\) find \(R_A\text{.}\) \(p^{1/4}\) classical, \(p^{1/6}\) quantum.
  3. Given \(E_A, E_B, \phi_A(P_B), \phi_A(Q_B), \phi_B(P_A), \phi_B(Q_A)\) find \(j\)-invariant of \(E_{AB}\text{.}\)

Subsection 3.2.5 Supersingular isogeny public key

Classically DH key-exchange \(\leadsto\) ElGamal encryption.

  1. Key generation.

    Alice: secret \(\phi_A \colon E \to E_A\text{,}\) public \(E_A\) and \(\phi_A(P_B), \phi_A(Q_B)\text{.}\)

  2. Encryption.

    Bob: choose \(\phi_B \colon E \to E_B\text{,}\) compute \(j(E_{AB})\text{.}\)

    Send Alice \(c = (E_B, \phi_B(P_A), \phi_B(Q_A), m\oplus j(E_{AB}))\)

  3. Decryption.

    Alice use \((E_B, \phi_B(P_A), \phi_B(Q_A))\) to compute \(j(E_{AB})\text{.}\) Computes \((m\oplus j(E_{AB})) \oplus j(E_{AB}) = m\text{.}\)

\(E(\FF_{p^2})\text{,}\) \(p = l_A^{e_A} l_B^{e_B} f \pm 1\text{,}\) for \(128\)-bit security use a \(512\)-bit key.

Subsection 3.2.6 Algorithmic aspects

  1. (Choosing \(f\)) Prime number theorem for arithmetic progressions gives you a bound on the density of primes of the form \(l_A^{e_A} l_B^{e_B} f \pm 1\)
  2. Choosing a s.s. e.c. with the right group order, Broker's algorithm.

  3. Finding a basis for \(E\lb l_A^{e_A}\rb\text{.}\)

    1. Find a random point in \(E(\FF_{p^2})\) say \(P\text{.}\)
    2. Check the order of \((l_B^{e_B} f)^2 \cdot P\text{.}\) If its \(l_A^{e_A}\) set \(P_A = P\text{.}\) Otherwise repeat from 1.
    3. Do the same with \(Q_A = Q\text{.}\)
    4. Check independence by seeing if \(e(P_A,Q_A) \) has the right order, so that it is in \(E\lb l_A^{e_A} \rb\) torsion.
  4. Computing the kernels generated by \(R_A = m_A P_A + n_A Q_A\text{,}\) \(m_A, n_A \in \ZZ/l_A^{e_A} \ZZ\text{.}\) Analogue of double and add. Set \(R_A = P_A + \lb m_A\inv n_A\rb Q_A\text{.}\) Use differential addition (when you compute \(A+B\) with side info \(A-B\)) and a Montgomery ladder
  5. (Computing smooth degree isogenies) Decompose the \(l_A^{e_A}\) isogeny into \(e_A\) different \(l_A\)-isogenies, \(\phi_i\colon E_i \to E_{i+1}\) the kernel of \(\phi_i\) is \(\langle l_A^{e_A - i - 1} R_A\rangle\text{.}\) Vélu's formula runs in \(O(l)\) for \(l\)-isogeny.