Skip to main content

Section 3.4 The Deuring Correspondence (Maria Ines)

References:

  1. Voight ch. 16,17,42
  2. Hard and Easy Problems for Supersingular Isogeny Graphs - Christophe Petit and Kristin Lauter https://eprint.iacr.org/2017/962.pdf

Subsection 3.4.1 Background: Ideals and Ideal classes

Let \(B/\QQ\) be a quaternion algebra and \(\ints \subseteq B\) be an order. If \(I \subseteq B \) is a lattice, we can define \(\ints_L (I) = \{ \alpha\in B : \alpha I \subseteq I \}\text{.}\) This is an order , it's the left order of \(I\) similarly can define \(\ints_R (I) \text{.}\)

Definition 3.4.1.

A left (resp. right) fractional ideal is a lattice \(I \subseteq B\) s.t. \(\ints \subseteq \ints_L (I) \) resp \(\ints \subseteq \ints_R (I) \)

Definition 3.4.2. Compatibility.

For lattices \(I,J \subseteq B\) we say \(I\) is compatible with \(J\) if

\begin{equation*} \ints_R(I)= \ints_L(J)\text{.} \end{equation*}

A lattice \(I \) is invertible if there is a lattice \(I' \subseteq B\) s.t.

\begin{equation*} II' = \ints_L(I) = \ints_R(I') \end{equation*}
\begin{equation*} I'I = \ints_L(I') = \ints_R(I) \end{equation*}

with both products compatible

Definition 3.4.4. Principal ideals.

An ideal of the form

\begin{equation*} I = \ints_L(I) \alpha = \alpha\ints_R(I) \end{equation*}

is a principal ideal.

Definition 3.4.6. Reduced norms.

Let \(I \subseteq B\) be a fractional ideal the reduced norm of \(I \) is the positive generator of the fractional ideal generated by

\begin{equation*} \{ \operatorname{nrd} (\alpha) : \alpha \in I \} \end{equation*}

in \(\QQ\text{.}\) We denote it \(\operatorname{nrd}(I)\text{.}\)

Ideal classes.
Definition 3.4.7. Ideal classes.

Two left fractional ideals \(I,J \subseteq B\) are in the same left class

\begin{equation*} I\sim_L J \end{equation*}

if \(\exists \alpha \in B^\times\) s.t. \(I\alpha = J\text{.}\) Equivalently if \(\ints_L(I) = \ints_L(J)\) and \(I \sim J\) as left modules over this order. \(\sim_L\) is an equivalence relation \(\lb I \rb\) is the class of \(I\text{.}\) If \(I \) is invertible then every \(J \in \lb I \rb_L\) is invertible, and then we say \(\lb I \rb_L \) is invertible.

Definition 3.4.8. Class sets.

Let \(\ints \subseteq B\) be an order. The left class set of \(\ints\) is

\begin{equation*} \operatorname{Cls}_L \ints = \{ \lb I \rb_L : I \subseteq B \text{ is invertible and } \ints_L(I) = \ints\} \end{equation*}

its a pointed set with distinguished element \(\lb \ints \rb_L\text{.}\)

Types of orders.

Let \(\ints ,\ints' \subseteq B\) be orders.

Definition 3.4.10.

We say \(\ints,\ints' \) are of the same type if \(\exists \alpha \in B^\times\) s.t. \(\ints ' = \alpha \inv \ints \alpha\text{.}\) \(\ints,\ints'\) are locally of the same type if \(\ints_p, \ints_p'\) are of the same type for all primes in \(\ZZ\cup\{\infty\}\text{.}\) \(\ints\) is connected to \(\ints'\) if there exists an invertible fractional \(\ints,\ints'\)-ideal \(J \subseteq B\) called a connecting ideal.

Definition 3.4.12.

Let \(\ints \subseteq B\) be an order.

  1. The genus \(\operatorname{Gen}(\ints)\) of \(\ints \) is the set of orders in \(B \) connected to \(\ints\text{.}\)
  2. The type set \(\operatorname{Typ}(\ints)\) of \(\ints\) is the set of \(\ZZ\)-algebra isomorphism classes of orders in \(\operatorname{Gen} (\ints)\text{.}\)
Remark 3.4.14.
  1. Any two maximal orders in \(B\) are connected.
  2. In particular there are only finitely many conjugacy classes of maximal orders in \(B\text{.}\)
Example 3.4.15. Voight 17.6.3.

Let

\begin{equation*} B = \legendre{-1,-23}{\QQ} \end{equation*}

Then \(\ints= \ZZ + \ZZ i + \ZZ \frac{i+j}{2} + \ZZ i \frac{i+j}{2}\) is a maximal order and

\begin{equation*} \operatorname{Typ}(\ints) = \left\{ \lb \ints \rb , \lb \ints_2 \rb , \lb \ints_3 \rb \right\}\text{.} \end{equation*}

Subsection 3.4.2 The Deuring Correspondence

Fix a prime \(p\text{,}\) let \(E\) be an elliptic curve over \(\FF_q = \FF_{p^n}\text{.}\)

Let \(n \gt 0\) be prime to \(p \text{.}\) Then

\begin{equation*} E \lb n \rb \simeq \ZZ/ n \oplus \ZZ/n \end{equation*}

as groups so \(\End(E\lb n\rb ) \simeq M_2(\ZZ/n)\text{.}\)

Claim: The structure map \(\ints/n\ints \to \End(E\lb n \rb)\) is an isomorphism.

Check: suppose \(\phi \in \ints\) kills \(E\lb n \rb\text{,}\) then since \(\phi\) is separable then \(\exists\) \(\psi \in \ints\) s.t. \(\phi = n \psi\text{.}\) Hence \(\phi = 0 \in \ints/n\text{.}\) This gives injectivity.

As both rings are finite with the same order \(n^4\) we have an isomorphism.

Since \(\ints\) is a free \(\ZZ\) module

\begin{equation*} \ints_l = \ints \otimes \QQ_l = \ints \otimes \varprojlim _n \ZZ/l^n \end{equation*}
\begin{equation*} \simeq \varprojlim_n \ints/l^n \simeq \varprojlim_n \End(E[l^n]) \end{equation*}
\begin{equation*} \simeq \End_{\ZZ_l} \simeq M_2( \ZZ_l) \end{equation*}

for any \(l \ne p\) primes. This is an isomorphism as \(\ZZ\)-algebras.

In particular \(\ints_l\) is maximal in \(B_l \simeq M_2(\QQ_l)\) and \(B\) is split at \(l\) for all \(l\ne p\text{.}\) Since \(B\) is definite, it follows from the classification theorem that \(\operatorname{Ram}(B) = \left\{ p, \infty \right\}\text{.}\)

Fact: \(\ints_p\) is maximal in \(B_p\) (thm 42.1.9 of voight).

\(\ints\) is maximal in \(B\) because it is locally maximal.

Voight 42.4.7.

Definition 3.4.19.

Let \(I \subseteq \ints = \End(E)\) be an integral left \(\ints\)-ideal with \((\operatorname{nrd}(I), p) = 1\text{.}\) Define

\begin{equation*} E\lb I \rb = \{ P \in E(\overline \FF_q) : \alpha(P) = 0 \forall \alpha \in I\} \end{equation*}

Then there is a separable isogeny

\begin{equation*} \Phi_I \colon E \to E / E \lb I \rb \end{equation*}

with \(\ker \Phi_I = E \lb I \rb\text{.}\)

Subsection 3.4.3 Applications to SIG crypto

Problem 3.4.22. Constructive Deuring correspondence.

Given a maximal order \(\ints \subseteq B_{p,\infty}\) return a s.s. \(j\)-invariant \(j\) s.t. \(\ints \simeq \End(E_j)\text{.}\)

Problem 3.4.23. Inverse Deuring correspondence.

Given a supersingular \(j\) invariant \(j\text{,}\) compute a maximal order \(\ints \subseteq B_{p,\infty}\) s.t. \(\ints \simeq \End(E_j)\text{.}\) \(\ints\) is described by a \(\ZZ\)-basis.

Problem 3.4.24. Endomorphism ring computation problem.

Given a supersingular \(j\) invariant \(j\text{,}\) \(\End(E_j)\text{.}\) \(\End(E_j)\) should be returned as \(4\) or \(3\) rational maps that form a \(\ZZ\)-basis. Their representation should be efficient in storage and in evaluation time at points.

Remark 3.4.25.
  1. Problem 1 can be solved in polynomial time, (Prop. 14 in Petit-Lauter).
  2. P2 and P3 are polynomially equivalent but this isn't obvious (P-L sec.3.1 and 3.2)
  3. There is no known efficient algorithm to solve P3.

Recall: the (Charles-Goren-Lauter) CGL hash function is preimage resistant iff given 2 s.s. \(j\)-invariants \(j_1,j_2\) its computationally hard to compute a positive integer \(e\) and an isogeny \(\phi \colon E_{j_1} \to E_{j_2}\) of degree \(l^e\text{.}\)

Algorithm

Input: two s.s. \(j\)-invariants \(j_s,j_t \in \FF_{p^2}\text{.}\)

Output: sequence of \(j\)-invariants

\begin{equation*} j_s,\ldots,j_0,\ldots, j_t\text{.} \end{equation*}
  1. Compute \(\End(j_s),\End(j_t)\text{.}\)
  2. Compute \(\ints_s \simeq \End(E_{j_s})\text{,}\) \(\ints_t \simeq \End(E_{j_t})\)
  3. Compute ideals \(I_s\) and \(I_t\) connecting \(\ints_0 \) to \(\ints_s\text{,}\) \(\ints_t\)
  4. Compute ideals \(J_s \in \lb I_s \rb\text{,}\)\(J_t \in \lb I_t \rb\text{,}\) with norms \(l^{e_s},l^{e_t}\text{.}\)
  5. For \(J \in \{J_s,J_t\}\) and corresponding \(E \in \{E_s,E_t\}\) and \(e\in \{e_s, e_t\}\) compute \(J_i = \ints_0 p^2 + \ints_0 l^i\) for \(i = 0,\ldots, e\text{.}\) For \(i = 0,\ldots, e\) compute \(K_i \in \lb J_i \rb_L\) with powersmooth norm. Translate \(K_i\) into an isogeny
    \begin{equation*} \phi\colon E_0 \to E_i \end{equation*}
    Deduce a sequence \((j_0, j(E_1),\ldots,j(E) = j_e)\text{.}\)
  6. Return \((j(E_s), \ldots,j_0, \ldots,j(E_t))\text{.}\)

Except for step 1 everything can be done efficiently.

Remark 3.4.27.

The converse is also true.