11institutetext: University of Colorado Boulder, USA
11email: Joseph.Macula<EMAIL_ADDRESS>
# Extending class group action attacks via sesquilinear pairings

Joseph Macula 11 0000-1111-2222-3333 Katherine E. Stange 11
0000-0003-2294-0397

###### Abstract

We introduce a new tool for the study of isogeny-based cryptography, namely
pairings which are sesquilinear (conjugate linear) with respect to the
$\mathcal{O}$-module structure of an elliptic curve with CM by an imaginary
quadratic order $\mathcal{O}$. We use these pairings to study the security of
problems based on the class group action on collections of oriented ordinary
or supersingular elliptic curves. This extends work of [4] and [13].

###### Keywords:

Isogeny-based cryptography Pairings Elliptic Curves.

##  1 Introduction

The use of isogeny graphs in cryptography dates to [8, 10, 24]. The latter
proposals were for public-key cryptography based on an ordinary isogeny graph.
In particular, the class group $\operatorname{Cl}(\mathcal{O})$ of an order
$\mathcal{O}$ in an imaginary quadratic field $K$ acts on the set of ordinary
elliptic curves over $\overline{\mathbb{F}}_{p}$ with CM by $\mathcal{O}$. For
efficiency, CSIDH was proposed [6], making use of supersingular curves with an
action by the class group of the Frobenius field. More recently, this was
generalized to OSDIH [9], making use of other imaginary quadratic fields in
the endomorphism algebra. This paper concerns _oriented_ elliptic curves,
which refers to attaching the data of an embedding of a particular imaginary
quadratic order $\mathcal{O}$ into the endomorphism ring. All these public-key
proposals are examples of class group actions on oriented curves.

The security of these schemes relies on variants of the Diffie-Hellman problem
for the class group action. The security of these problems has drawn a great
deal of interest, and not all instances of the problem have so far proven to
be secure. If the class group is even, the decisional Diffie-Hellman problem
is broken by the use of genus theory [7, 5]. These papers make use of the Weil
and Tate pairings to compute certain associated characters. More recently, [4]
makes use of generalizations of Weil and Tate pairings to break certain
instances of the class group action problem (i.e., determining which class
group element takes one given oriented curve to another) when the discriminant
has a large smooth square factor and the degree is known. Pairings have also
appeared in the study of oriented elliptic curves in [17], to navigate the
isogeny graph.

The attacks in [4] use pairings to reduce a hidden isogeny problem with known
degree for the class group action to the SIDH problem recently broken using
higher dimensional abelian varieties [2, 20, 23]. In short, if the degree of a
secret isogeny $\phi:E\rightarrow E^{\prime}$ is known, and it is known that
$\phi P\in\mathbb{Z}P^{\prime}$ for $P\in E$ and $P^{\prime}\in E^{\prime}$,
then we can make use of a relationship of the form

$\langle P,P\rangle^{\deg\phi}=\langle\phi P,\phi P\rangle=\langle
kP^{\prime},kP^{\prime}\rangle=\langle P^{\prime},P^{\prime}\rangle^{k^{2}}$

by solving a discrete logarithm to obtain the relationship
$k^{2}\equiv\deg\phi\pmod{m}$, and thereby solve for $k$. With this, we
(essentially) obtain the image $\phi P$ of $P$, which is the type of
information provided in the SIDH problem. The classical SIDH problem (for
which we now have efficient methods) requires the image of two basis points,
and this provides only one. To close the gap, [4] uses results of [13] which
reduce SIDH1, in which only one torsion point is provided, to classical SIDH,
provided the order of the point is square. More recent work presented but not
yet available [3] uses pairings to generalize the SIDH attacks so that torsion
images of any sufficiently large subgroup suffice.

These attacks require that the degree of the secret isogeny is known, which is
the case in some implementations; see [4] for some details. Furthermore, in
[13, Lemma 14], the authors give a heuristic reduction from the group action
problem to the same problem with known degree. In this paper we will assume
throughout that the degree of the secret isogeny is known.

In this paper we introduce a new tool for understanding these results and
pushing such attacks further. In [26], certain new generalized pairings
$\widehat{W}$ and $\widehat{T}$ (generalizing the usual Weil and Tate
pairings) are defined, which are $\mathcal{O}$-sesquilinear, meaning that

$\langle\alpha x,\beta y\rangle=\langle x,y\rangle^{\overline{\alpha}\beta}$

for $\alpha,\beta\in\mathcal{O}$. In particular, they take values in an
$\mathcal{O}$-module formed by extending scalars from the usual domain
$\mathbb{F}_{q}^{*}$.

In particular, we can now assume only that $\phi P\in\mathcal{O}P^{\prime}$
and obtain a relationship

$\langle P,P\rangle^{\deg\phi}=\langle\phi P,\phi P\rangle=\langle\lambda
P^{\prime},\lambda P^{\prime}\rangle=\langle
P^{\prime},P^{\prime}\rangle^{N(\lambda)},$

where $\lambda\in\mathcal{O}$. The new pairings are amenable to a Miller-type
effective algorithm for their computation, and carry all the useful properties
of the Weil and Tate pairings, especially compatibility with
$\mathcal{O}$-oriented isogenies.

The paper [4] provides a taxonomy of known generalized pairings, but all of
these are only $\mathbb{Z}$-bilinear with image in $\mathbb{F}_{q}^{*}$.

One important difference of these sesquilinear pairings from the generalized
pairings previously considered is their non-degeneracy. In [4], there is a
classification theorem for _cyclic self-pairings_ , namely homogeneous
degree-$2$ functions $f_{m}:C\rightarrow\mu_{m}$ where $C$ is a cyclic
subgroup of $E[m]$ whose image under $f_{m}$ spans $\mu_{m}$. As shown in [4],
these can often be formed from generalizations of the classical reduced
$m$-Tate pairing; for a simple such construction, see [4, Example 4.4]. In
particular, such functions are helpful when they are compatible with oriented
isogenies $\phi$, meaning $f_{m}\circ\phi=f_{m}^{\deg\phi}$. They essentially
show that compatible cyclic self-pairings can only be non-trivial for $m$
dividing the discriminant $\Delta_{\mathcal{O}}$ of $\mathcal{O}$. This limits
the applicability of their attacks on the class group action to situations
where the discriminant has a good factorization. We demonstrate that by
extending to $\mathcal{O}$-sesquilinear pairings, whose domain is not
$\mathbb{Z}$-cyclic but instead $\mathcal{O}$-cyclic, we obtain many more non-
trivial self-pairings to work with.

The use of these new $\mathcal{O}$-sesquilinear pairings offers several
clarifying conceptual advantages, and partially answers several of the open
problems posed in [4]. However, they are not a magic bullet: we show (Theorem
4.4) that the computation of these pairings is essentially equivalent to the
computation of the $\mathcal{O}$-orientation, provided discrete logarithms are
efficient in $\mu_{m}$ (for example, if $m$ is smooth).

Conceptual contributions.

  1. 1.

We introduce the new $\mathcal{O}$-sesquilinear pairings $\widehat{W}$ and
$\widehat{T}$ in the cryptographic context.

  2. 2.

We show that these pairings give rise to many non-degenerate
$\mathcal{O}$-cyclic self-pairings, without a requirement that $m$ divide the
discriminant (Theorem 4.3).

  3. 3.

We characterize elliptic curves for which $E[m]$ is a cyclic
$\mathcal{O}$-module (Theorem 3.3): $E[m]$ is $\mathcal{O}$-cyclic if and only
if the $\mathcal{O}$-orientation is $m$-primitive.

  4. 4.

We show an equivalence between computation of an $\mathcal{O}$-orientation and
the computation of $\mathcal{O}$-sesquilinear pairings for $m$ smooth (Theorem
4.4).

  5. 5.

Corollary 1 and Theorem 6.1 (described in more detail below) provide evidence
for a trade-off between the amount of known level structure of a secret
isogeny $\phi:E\to E^{\prime}$ of degree $d$ and how much of the endomorphism
rings of $E$ and $E^{\prime}$ we need to represent to find $\phi$. As shown in
[27], the fixed-degree isogeny problem with full level structure is equivalent
to finding a representation of the full endomorphism ring of $E$ and
$E^{\prime}$, while [2, 20, 23] show that the fixed-degree isogeny problem
with minimal level structure requires no knowledge of even a partial
representation of the endomorphism rings of $E$ and $E^{\prime}$. As described
in _Cryptographic contributions_ items 2 and 3 below, knowledge of an
intermediate level structure can be combined with a representation of only
“half” of the endomorphism rings of $E$ and $E^{\prime}$, to provide attacks
on hidden isogenies of known degree. See also the work in [13], which explores
varying amounts of level structure.

Cryptographic contributions.

  1. 1.

We extend the applicability of the (sometimes polynomial) attacks from [4] on
the class group action problem (Section 8). These attacks run for smooth $m$
dividing the discriminant. We recover these attacks using the new pairings in
a slightly different way, with the advantage that our pairing computations do
not require going to a large field extension. This partially addresses one of
the open questions of [4, Section 7]. Example 3 gives an explicit situation in
which the reach of attacks is extended.

  2. 2.

We demonstrate a pairing-based reduction from SIDH1 to SIDH in the oriented
situation for $E[m]$, where $m$ is smooth and coprime to the discriminant
(Theorem 6.1), resulting in an attack when $m^{2}>\deg\phi$. This partially
addresses the first and second open problems in [4, Section 7]. Existing
attacks on SIDH1 (which apply without orientation information) require
$m>\deg\phi$.

  3. 3.

We reduce the hard problem underlying FESTA [1] to finding an orientation of
the secret isogeny $\phi:E\rightarrow E^{\prime}$ (i.e. an orientation of both
curves and the isogeny between them) (Corollary 1). This follows from an
attack on the Diagonal SIDH Problem (Theorem 7.1).

  4. 4.

We show how these pairings, using orientation information, easily reveal
_partial_ information on the image of a torsion point $P$ of order $m$ for $m$
smooth (Theorem 5.1). This results in an algorithm to break CSIDH or other
class-group-based schemes in square root of exponential time by running the
SIDH attack on $\sqrt{m}$ candidate $m$-torsion points as images under $\phi$
(Remark 4).

  5. 5.

Our results should be considered a cautionary tale for the design of
decisional problems based on torsion point images, such as in [21], since the
possible images of torsion points is restricted. We discuss this in Remark 5.

  6. 6.

In the supersingular case, we demonstrate a method of finding the secret
isogeny in the presence of two independent known orientations (which amounts
to an explicit subring of the endomorphism ring of rank $4$), provided the
secret isogeny is oriented for both orientations. This is not a surprise, as
this problem could be solved by the KLPT algorithm if the endomorphisms are
obtained by walking the graph (see [12], and also [18, 27]), but it provides a
new method via a simple reduction to the SIDH problem. (Section 9.)

##  2 Background

###  2.1 Notations.

We study elliptic curves, typically denoted $E$, $E^{\prime}$ etc., defined
over finite fields, denoted by $\mathbb{F}$ in general. Denote an algebraic
closure of $\mathbb{F}$ by $\bar{\mathbb{F}}$. The identity on $E$ is denoted
$\mathcal{O}_{E}$, and $\operatorname{End}(E)$ is the endomorphism ring over
$\overline{\mathbb{F}}$. We study imaginary quadratic fields, denoted $K$ in
general, and orders in such fields, denoted by $\mathcal{O}$,
$\mathcal{O}^{\prime}$ etc. Greek letters typically denote elements of the
orders. When considering the action of an element $\alpha\in\mathcal{O}$ on a
point $P$, we write $[\alpha]P$. The Greek letter $\phi$ always refers to an
isogeny. For ease of notation, we write $\phi P$ instead of $\phi(P)$.
Throughout the paper, we write $\mu_{m}$ for the copy of $\mu_{m}$ in a finite
field.

###  2.2 Orientations.

We study $\mathcal{O}$-_oriented_ elliptic curves over finite fields, which
are curves together with the information of an embedding
$\iota:\mathcal{O}\rightarrow\operatorname{End}(E)$. This extends to an
embedding of the same name,
$\iota:K\rightarrow\mathbb{Q}\otimes_{\mathbb{Z}}\operatorname{End}(E)$, and
the $\mathcal{O}$-orientation is called _primitive_ if
$\iota(K)\cap\operatorname{End}(E)=\mathcal{O}$. If the index
$[\iota(K)\cap\operatorname{End}(E):\iota(\mathcal{O})]$ is coprime to $n$, we
say the orientation is $n$-_primitive_. Given an $\mathcal{O}$-orientation,
there is a unique $\mathcal{O}^{\prime}\supseteq\mathcal{O}$ for which $\iota$
becomes a $\mathcal{O}^{\prime}$-primitive orientation, namely
$\mathcal{O}^{\prime}=\iota(K)\cap\operatorname{End}(E)$. Given an elliptic
curve $E$ with an $\mathcal{O}$-orientation, we define the _relative
conductor_ of $\mathcal{O}$ to be the index
$[\mathcal{O}^{\prime}:\mathcal{O}]$, for which the orientation is
$\mathcal{O}^{\prime}$-primitive.

If $\phi:E\rightarrow E^{\prime}$ is an isogeny between two
$\mathcal{O}$-oriented elliptic curves $(E,\iota)$ and
$(E^{\prime},\iota^{\prime})$ is such that
$\phi\circ\iota(\alpha)=\iota^{\prime}(\alpha)\circ\phi$ for all
$\alpha\in\mathcal{O}$, then we say that $\phi$ is an oriented isogeny.
Throughout the paper, we will generally fix a single $\mathcal{O}$-orientation
for any curve, so we will often drop the $\iota$, writing simply $[\alpha]$
for $\iota(\alpha)$, writing $\mathcal{O}\subseteq\operatorname{End}(E)$, and
characterizing oriented isogenies as those for which
$\phi\circ[\alpha]=[\alpha]\circ\phi$. This saves on notation.

###  2.3 Computational assumptions

With regards to computations, we use the word _efficient_ to mean polynomial
time in the size of the input. Throughout the paper, when we assume that if we
are given an $\mathcal{O}$-oriented elliptic curve, we mean that we are given
an explicit orientation, and that, in particular that, given an element
$\alpha\in\mathcal{O}$, we can compute its action $[\alpha]$ on a point $P$ on
$E$ efficiently.

We assume throughout that the degree of the hidden isogeny is known.

We assume that $m$ is smooth, meaning that its factors are polynomial in size,
so that discrete logarithms in $\mu_{m}$ or $E[m]$ are computable in
polynomial time. In particular, we can write any element of $E[m]$ in terms of
a given basis.

###  2.4 The Tate-Lichtenbaum Frey-Rück Pairing.

We review the definition and basic properties of the Tate-Lichtenbaum pairing.

###### Definition 1

Let $m>1$ be an integer. Let $E$ be an elliptic curve defined over a field
$\mathbb{F}$ (assumed finite in this paper). Suppose that $P\in
E(\mathbb{F})[m]$. Choose divisors $D_{P}$ and $D_{Q}$ of disjoint support
such that $D_{P}\sim(P)-(\mathcal{O})$ and $D_{Q}\sim(Q)-(\mathcal{O})$. Then
$mD_{P}\sim 0$, hence there is a function $f_{P}$ such that
$\operatorname{div}(f_{P})=mD_{P}$. The Tate-Lichtenbaum pairing

$t_{m}:E(\mathbb{F})[m]\times
E(\mathbb{F})/mE(\mathbb{F})\rightarrow\mathbb{F}^{*}/(\mathbb{F}^{*})^{m}$

is defined by

$t_{m}(P,Q)=f_{P}(D_{Q}).$

The standard properties of the Tate pairing are as follows. Proofs can be
found in many places, for example [22] and [4, Sec 3.2].

###### Proposition 1

Definition 1 is well-defined, and has the following properties:

  1. 1.

Bilinearity: for $P,P^{\prime}\in E(\mathbb{F})[m]$ and $Q,Q^{\prime}\in
E(\mathbb{F})$

$\displaystyle t_{m}(P+P^{\prime},Q)=$ $\displaystyle
t_{m}(P,Q)t_{m}(P^{\prime},Q),$ $\displaystyle t_{m}(P,Q+Q^{\prime})=$
$\displaystyle t_{m}(P,Q)t_{m}(P,Q^{\prime}).$

  2. 2.

Non-degeneracy: Let $\mathbb{F}$ be a finite field containing the $m$-th roots
of unity $\mu_{m}$. For nonzero $P\in E(\mathbb{F})[m]$, there exists $Q\in
E(\mathbb{F})$ such that

$t_{m}(P,Q)\neq 1.$

Furthermore, for $Q\in E(\mathbb{F})\backslash mE(\mathbb{F})$, there exists a
$P\in E(\mathbb{F})[m]$ such that

$t_{m}(P,Q)\neq 1.$

In particular, for $P$ of order $m$, there exists $Q$ such that $t_{m}(P,Q)$
has order $m$, and similarly for the other entry.

  3. 3.

Compatibility: For a point $P\in E(\mathbb{F})[m]$, an isogeny
$\phi:E\rightarrow E^{\prime}$, and a point $Q\in E^{\prime}(\mathbb{F})$,

$t_{m}(\widehat{\phi}P,Q)=t_{m}(P,\phi Q).$

##  3 Structure of $E[\alpha]$

Suppose $E$ has an $\mathcal{O}$-orientation. Let $\alpha\in\mathcal{O}$. We
wish to know when $E[\alpha]$ is cyclic as an $\mathcal{O}$-module. The
following two theorems of Lenstra are relevant.

######  Theorem 3.1 ([19, Proposition 2.1])

Let $E$ be an elliptic curve over an algebraically closed field $k$, and
$\mathcal{O}$ a subring of $\operatorname{End}_{k}(E)$ such that as
$\mathbb{Z}$-modules, $\mathcal{O}$ is free of rank 2 and
$\operatorname{End}_{k}(E)/\mathcal{O}$ is torsion-free. Then for every
separable element $\alpha\in\mathcal{O}$,
$E[\alpha]\cong\mathcal{O}/\alpha\mathcal{O}$ as $\mathcal{O}$-modules.

When $\alpha$ is inseparable, Lenstra has a similar result. With $\mathcal{O}$
as above, $\text{char }k=p>0$, and
$K=\mathcal{O}\otimes_{\mathbb{Z}}\mathbb{Q}$, he observes that there is a
$p$-adic valuation $\nu$ on $K$ with $\nu(\alpha)=\log(\deg_{i}\alpha)/\log p$
for $\alpha\in\mathcal{O}$. Following his notation, we define $V=\\{x\in
K:\nu(x)\geq 0\\}$.

######  Theorem 3.2 ([19, Proposition 2.4])

Let the notation and hypotheses be as above. Then for every non-zero element
$\alpha\in\mathcal{O}$ there is an isomorphism of $\mathcal{O}$-modules
$E[\alpha]\oplus(V/\alpha V)\cong\mathcal{O}/\alpha\mathcal{O}$.

###### Theorem 3.3

Let $E$ be an elliptic curve over $\mathbb{F}$, $K$ an imaginary quadratic
field, and $\mathcal{O}$ an order in $K$ such that $E$ has an
$\mathcal{O}$-orientation, which is primitive when extended to
$\mathcal{O^{\prime}}$. Let $f=[\mathcal{O}^{\prime}:\mathcal{O}]$ be the
relative conductor of $\mathcal{O}$. For $\alpha\in\mathcal{O}$ with
$N(\alpha)$ coprime to $f$ (i.e., such that the $\mathcal{O}$-orientation is
$N(\alpha)$-primitive), then $E[\alpha]$ is cyclic as an $\mathcal{O}$-module.
Specifically:

  1. 1.

If $\alpha$ is separable, then $E[\alpha]\cong\mathcal{O}/\alpha\mathcal{O}$.

  2. 2.

If $\alpha$ is inseparable, then $E[\alpha]$ is isomorphic to a proper cyclic
$\mathcal{O}$-submodule of $\mathcal{O}/\alpha\mathcal{O}$.

As a partial converse, as soon as $\alpha$ factors through multiplication by
$n$ for some $n>1$ that divides $f$, $E[\alpha]$ is not cyclic as an
$\mathcal{O}$-module. In particular, if $\alpha=m\in\mathbb{Z}$, then $E[m]$
is a cyclic $\mathcal{O}$-module if and only if $m$ and $f$ are coprime.

###### Proof

Suppose first that $\alpha$ is separable. Let $\iota$ be an
$\mathcal{O}$-orientation for $E$ and $\mathcal{O^{\prime}}$ be the order of
$K$ for which $\iota$ is a primitive orientation. Then as an abelian group the
quotient $\operatorname{End}(E)/\mathcal{O^{\prime}}$ is torsion-free and
Theorem 3.1 tells us that
$E[\alpha]\cong\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}}$ as
$\mathcal{O}^{\prime}$-modules. We have
$N(\alpha)=N(\alpha\mathcal{O^{\prime}})=\left|\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}}\right|$,
so since $N(\alpha)$ is coprime to $f$, it follows from [11, Proposition 7.18,
7.20] that the natural injection
$\mathcal{O}/\alpha\mathcal{O}\rightarrow\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}}$
is an isomorphism of $\mathcal{O}$-modules.

Suppose then that $\alpha$ is inseparable. Let $\mathcal{O^{\prime}}$ be as
above. From Theorem 3.2 we have $E[\alpha]\oplus V/\alpha
V\cong\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}}$, so $E[\alpha]$ is
isomorphic as an $\mathcal{O^{\prime}}$-module to
$(\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}})/(V/\alpha V)$ and hence is
a cyclic $\mathcal{O^{\prime}}$-module. Since
$\mathcal{O^{\prime}}/\alpha\mathcal{O^{\prime}}\cong\mathcal{O}/\alpha\mathcal{O}$
as $\mathcal{O}$-modules, again by our assumption that $N(\alpha)$ is coprime
to $f$, it follows that $E[\alpha]$ is cyclic as an $\mathcal{O}$-module.

Finally, suppose $\alpha$ factors through $[n]$ for some $n>1$ with $n\mid f$.
Then as a $\mathbb{Z}$-module,
$E[\alpha]\cong\mathbb{Z}/b\mathbb{Z}\times\mathbb{Z}/c\mathbb{Z}$ with $n\mid
b\mid c$. Let $\\{P,Q\\}$ be a generating set for $E[\alpha]$ with
$\operatorname{ord}(P)=b,\operatorname{ord}(Q)=c$ and let
$\mathcal{O^{\prime}}=\mathbb{Z}[\sigma]$ for some $\sigma$. Then
$\mathcal{O}=\mathbb{Z}[f\sigma]$. Since any element of $\mathcal{O}$ is a
$\mathbb{Z}$-linear combination of $[1]$ and $[f\sigma]$, whether or not
$E[\alpha]$ is cyclic as an $\mathcal{O^{\prime}}$-module is determined by the
action of $f\sigma$. We have $[f\sigma]Q=[n\sigma]Q^{\prime}$, where
$Q^{\prime}=[f/n]Q$.

If $[\sigma]Q^{\prime}=[s]P+[t]Q$, then $[f\sigma]Q=[ns]P+[nt]Q$, and we
cannot obtain $P$ from the action of any $\mathbb{Z}$-linear combination of
$[1]$ and $[f\sigma]$ on $Q$. Thus, $Q$ cannot be a generator for $E[\alpha]$
as an $\mathcal{O}$-module. Since $Q$ was an arbitrary order $c$ point, and
since no point of order strictly less than $c$ can generate $E[\alpha]$ as an
$\mathcal{O}$-module (endomorphisms send points of $E$ of order $m$ to points
of $E$ of order dividing $m$), $E[\alpha]$ cannot be a cyclic
$\mathcal{O}$-module.

###### Example 1

Consider the ordinary curve $y^{2}=x^{3}+30x+2$ over $\mathbb{F}_{101}$.
Denoting the Frobenius endomorphism by $\pi$, $\mathbb{Z}[\pi]$ has conductor
2 in the maximal order and $[\mathbb{Z}[\pi]:\mathbb{Z}[\pi^{2}]]=18$. Thus,
Theorem 3.3 implies $E[3]$ is not cyclic as a $\mathbb{Z}[\pi^{2}]$-module.
Indeed, making a base change to $\mathbb{F}_{101^{2}}$, the 3-torsion of $E$
is rational. On the other hand, $E[3]$ is cyclic as a
$\mathbb{Z}[\pi]$-module. With $\mathbb{F}_{101^{2}}=\mathbb{F}_{101}(a)$ and
$x^{2}-4x+2$ the minimal polynomial of $a$, we have $P=(41a+16,39a+19)\in
E[3]$ and $\pi(P)=(60a+79,62a+74)\not\in\langle P\rangle$, hence
$\mathbb{Z}[\pi]P=E[3]$.

##  4 Sesquilinear pairings

We follow [26] in this section. Suppose $\mathcal{O}=\mathbb{Z}[\tau]$ is an
imaginary quadratic order. Let $E$ have CM by $\mathcal{O}$. Let
$\rho:\mathcal{O}\rightarrow\operatorname{GL}_{2}(\mathbb{Z})$ be the left-
regular representation of $\mathcal{O}$ acting on the basis $1$ and $\tau$.
Then we endow the Cartesian square $(\mathbb{F}^{*})^{\times 2}$ with an
$\mathcal{O}$-module action via

$(x,y)^{\alpha}=\rho(\alpha)\cdot(x,y)=(x^{a}y^{b},x^{c}y^{d}),\quad\text{where}\quad\rho(\alpha)=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}.$

In the case of an $\mathcal{O}$-module, by _order_ of an element we mean the
$\mathbb{Z}$-order; we can also discuss the annihilator as an
$\mathcal{O}$-module, which may be distinct from this.

For each $\alpha\in\mathcal{O}$, we define a bilinear pairing

$\widehat{T}^{\tau}_{\alpha}:E[\overline{\alpha}](\mathbb{F})\times
E(\mathbb{F})/[\alpha]E(\mathbb{F})\rightarrow(\mathbb{F}^{*})^{\times
2}/((\mathbb{F}^{*})^{\times 2})^{\alpha}$

as follows. Write

$\rho({\alpha})=\begin{pmatrix}a&b\\\
c&d\end{pmatrix},\quad\rho(\overline{\alpha})=\begin{pmatrix}d&-b\\\
-c&a\end{pmatrix}.$

Observe that this corresponds to the ring facts

$a+c\tau=\alpha,\quad b+d\tau=\alpha\tau,\quad
d-c\tau=\overline{\alpha},\quad-b+a\tau=\overline{\alpha}\tau.$

We take $P\in E[\overline{\alpha}]$, Define $f_{P}=(f_{P,1},f_{P,2})$, where

$\displaystyle\operatorname{div}(f_{P,1})$
$\displaystyle=a([-\tau]P)+b(P)-(a+b)(\mathcal{O}),$
$\displaystyle\operatorname{div}(f_{P,2})$
$\displaystyle=c([-\tau]P)+d(P)-(c+d)(\mathcal{O}).$

Choose an auxiliary point $R$ and define

$D_{Q,1}=([-\tau]Q+[-\tau]R)-([-\tau]R),\quad D_{Q,2}=(Q+R)-(R).$

Then, choosing $R$ so that the necessary supports are disjoint (i.e. the
support of $\operatorname{div}(f_{P,i})$ and $D_{Q,j}$ are disjoint for each
pair $i$, $j$), the pairing is defined as

$\widehat{T}^{\tau}_{\alpha}(P,Q):=\left(f_{P,1}(D_{Q,1}),f_{P,2}(D_{Q,1})\right)\left(f_{P,1}(D_{Q,2}),f_{P,2}(D_{Q,2})\right)^{\overline{\tau}}$

which can also be expressed as

$\left(f_{P,1}(D_{Q,1})f_{P,1}(D_{Q,2})^{Tr(\tau)}f_{P,2}(D_{Q,2})^{N(\tau)},f_{P,2}(D_{Q,1})f_{P,1}(D_{Q,2})^{-1}\right).$

###### Remark 1

In [26], it is shown how it is possible to think of these definitions as
divisors in $\mathcal{O}\otimes_{\mathbb{Z}}\operatorname{Pic}^{0}(E)$:

$D_{Q}=D_{Q,1}+\tau\cdot D_{Q,2},\quad
D_{P}=([-\tau]P)-(\mathcal{O})+\tau\cdot((P)-(\mathcal{O})),$

and analogously define $f_{P}$ satisfying
$\operatorname{div}(f_{P})={\alpha}\cdot D_{P}$, so that the definition above
has the form $f_{P}(D_{Q})$ as for the classical Tate pairing. For simplicity
here, we stick to the direct definition above. In that same paper, analogous
constructions are also given for quaternion orders and Weil-like pairings.

######  Theorem 4.1 ([26, Theorems 5.4, 5.5, 5.6])

The pairing above is well-defined and satisfies

  1. 1.

Sesquilinearity: For $P\in E[\overline{\alpha}](\mathbb{F})$ and $Q\in
E(\mathbb{F})$,

$\widehat{T}^{\tau}_{\alpha}([\gamma]P,[\delta]Q)=\widehat{T}^{\tau}_{\alpha}(P,Q)^{{\overline{\gamma}}{\delta}}.$

  2. 2.

Compatibility: Let $\phi:E\rightarrow E^{\prime}$ be an isogeny between curves
with CM by $\mathcal{O}$ and satisfying $[\alpha]\circ\phi=\phi\circ[\alpha]$.
Then for $P\in E[\overline{\alpha}](\mathbb{F})$ and $Q\in E(\mathbb{F})$,

$\widehat{T}^{\tau}_{\alpha}(\phi P,\phi
Q)=\widehat{T}^{\tau}_{\alpha}(P,Q)^{\deg\phi}.$

  3. 3.

Coherence: Suppose $P\in E[\overline{\alpha\beta}](\mathbb{F})$, and $Q\in
E(\mathbb{F})/[\alpha\beta]E(\mathbb{F})$. Then

$\widehat{T}^{\tau}_{\alpha\beta}(P,Q)\bmod{((\mathbb{F}^{*})^{\times
2})^{\beta}}=\widehat{T}^{\tau}_{\beta}([\overline{\alpha}]P,Q\bmod[{\beta}]E).$

Suppose $P\in E[\overline{\alpha}](\mathbb{F})$, and $Q\in
E(\mathbb{F})/[\alpha\beta]E(\mathbb{F})$. Then

$\widehat{T}^{\tau}_{\alpha\beta}(P,Q)\bmod{((\mathbb{F}^{*})^{\times
2})^{\alpha}}=\widehat{T}^{\tau}_{\alpha}(P,[{\beta}]Q\bmod[{\alpha}]E).$

  4. 4.

Non-degeneracy: Let $\mathbb{F}$ be a finite field, and let $E$ be an elliptic
curve defined over $\mathbb{F}$. Let $\alpha\in\mathcal{O}$ be coprime to
$char(\mathbb{F})$ and the discriminant of $\mathcal{O}$. Let $N=N(\alpha)$.
Suppose $\mathbb{F}$ contains the $N$-th roots of unity. Suppose there exists
$P\in E[N](\mathbb{F})$ such that $\mathcal{O}P=E[N]=E[N](\mathbb{F})$. Then

$\widehat{T}^{\tau}_{\alpha}:E[\overline{\alpha}](\mathbb{F})\times
E(\mathbb{F})/[\alpha]E(\mathbb{F})\rightarrow(\mathbb{F}^{*})^{\times
2}/((\mathbb{F}^{*})^{\times 2})^{\alpha},$

is non-degenerate. Furthermore, if $P$ has annihilator
$\overline{\alpha}\mathcal{O}$, then $T_{\alpha}(P,\cdot)$ is surjective; and
if $Q$ has annihilator $\alpha\mathcal{O}$, then $T_{\alpha}(\cdot,Q)$ is
surjective.

  5. 5.

Let $t_{n}$ be the $n$-Tate-Lichtenbaum pairing as described in Section 2.
Then

$\widehat{T}^{\tau}_{n}(P,Q)=\left(t_{n}(P,Q)^{2N(\tau)}t_{n}([-\tau]P,Q)^{Tr(\tau)},\;t_{n}([\tau-\overline{\tau}]P,Q)\right).$

  6. 6.

Provided both of the following quantities are defined,

$\widehat{T}^{\tau}_{N(\alpha)}(P,Q)=\widehat{T}^{\tau}_{\alpha}(P,Q)^{\overline{\alpha}}\pmod{((\mathbb{F}^{*})^{\times
r})^{\alpha}}$

###### Theorem 4.2

The pairing $\widehat{T}_{\alpha}^{\tau}(P,Q)$ is efficiently computable. That
is, it takes polynomially many operations in the field of definition of $P$
and $Q$.

###### Proof

This follows from the definition given above, which is amenable to a Miller-
style pairing algorithm; details are in [26, Algorithm 5.7].

To use the pairings $\widehat{T}^{\tau}_{\alpha}$, the most expedient
computation method is the formulas given in Theorem 4.1 items (5) and (6). In
particular, in our applications of $\widehat{T}^{\tau}_{\alpha}$ to form a
discrete logarithm problem, in most use cases it suffices to compute
$\widehat{T}^{\tau}_{\alpha}(P,Q)^{\overline{\alpha}}$ instead. But if one
wishes, one can compute $\overline{\alpha}^{-1}\pmod{\alpha}$ (provided
$\alpha$ and $\overline{\alpha}$ are coprime), and use

$\widehat{T}^{\tau}_{\alpha}(P,Q)=\widehat{T}^{\tau}_{N(\alpha)}(P,Q)^{\overline{\alpha}^{-1}}\pmod{((\mathbb{F}^{*})^{\times
2})^{\alpha}}.$

This may not apply when $\alpha$ divides the discriminant.

###### Definition 2

Also for cryptographic applications, it is convenient to apply a final
exponentiation to obtain a _reduced pairing_ , as is common with the classical
Tate pairing. This will move the pairing into the roots of unity:

$(\overline{\mathbb{F}}^{*})/(\overline{\mathbb{F}}^{*})^{\alpha}\rightarrow\mu_{N(\alpha)}^{\times
2}\subseteq(\overline{\mathbb{F}}^{*})^{\times 2},\quad x\mapsto
x^{(q-1)\alpha^{-1}}.$

###### Lemma 1

Consider the image $N(\mathcal{O})$ of $\mathcal{O}$ under the norm map. Then
$N(\mathcal{O})$ modulo $m$ is a subset of
$\\{x^{2}:x\in\mathbb{Z}/m\mathbb{Z}\\}$ only if $m$ and
$\Delta_{\mathcal{O}}$ share a non-trivial factor.

###### Proof

We may assume, by Sunzi’s Theorem (Chinese Remainder Theorem), that $m$ is a
prime power $p^{k}$. If $p$ is split, the statement follows from the fact that
the norm map from $\mathbb{Q}_{p}\otimes_{\mathbb{Z}}\mathcal{O}$ to
$\mathbb{Q}_{p}$ is surjective. If $p$ is inert, the norm map from
$\mathbb{Q}_{p}\otimes_{\mathbb{Z}}\mathcal{O}$ to $\mathbb{Q}_{p}$ is not
surjective, but is surjective on the residue field, so $N(\mathcal{O})$ modulo
$p^{k}$ does include non-squares.

###### Theorem 4.3

Let $E$ be an elliptic curve oriented by $\mathcal{O}=\mathbb{Z}[\tau]$. Let
$m$ be coprime to the discriminant $\Delta_{\mathcal{O}}$. Let $\mathbb{F}$ be
a finite field containing the $m$-th roots of unity. Suppose
$E[m]=E[m](\mathbb{F})$. Let $P$ have order $m$. Let $s$ be the maximal
divisor of $m$ such that $E[s]\subseteq\mathcal{O}P$. Then the multiplicative
order $m^{\prime}$ of $\widehat{T}_{m}^{\tau}(P,P)$ satisfies $s\mid
m^{\prime}\mid s^{2}$. In particular, if $\mathcal{O}P=E[m]$, then the self-
pairing has order $m$; and if $\mathcal{O}P=\mathbb{Z}P$, then the self-
pairing is trivial.

###### Proof

Let $m^{\prime}\mid m$ be the order of $\widehat{T}_{m}^{\tau}(P,P)$. Suppose
$s$ is the maximal divisor of $m$ so that $E[s]\subseteq\mathcal{O}P$. Then,
in particular, $[s\tau]P\in\mathbb{Z}P$. Thus
$\mathcal{O}[s]P=\mathbb{Z}[s]P$. We will show that $m^{\prime}\mid s^{2}$ and
$s\mid m^{\prime}$.

Let $\lambda\in\mathcal{O}$. Then $[\lambda s]P=[ks]P$ for some
$k=k(\lambda)\in\mathbb{Z}$, and then

$\widehat{T}_{m}^{\tau}([s]P,[s]P)^{k^{2}}=\widehat{T}_{m}^{\tau}([ks]P,[ks]P)=\widehat{T}_{m}^{\tau}([\lambda
s]P,[\lambda s]P)=\widehat{T}_{m}^{\tau}([s]P,[s]P)^{N(\lambda)}.$

Ranging over all $\lambda\in\mathcal{O}$, we conclude that $N(\lambda)$ are
squares modulo $m^{\prime\prime}=m^{\prime}/\gcd(m^{\prime},s^{2})$, the
multiplicative order of $\widehat{T}_{m}^{\tau}([s]P,[s]P)$, contradicting
that $m$ is coprime to the discriminant unless $m^{\prime\prime}=1$ by Lemma
1. Therefore $m^{\prime}\mid s^{2}$.

On the other hand, by Theorem 4.1 item (4), there exists some $Q$ so that
$\widehat{T}_{m}^{\tau}(P,Q)$ has order $m$. Let $t=m/s$. Then there is a
basis for $E[m]$ of the form $P,P^{\prime}$ where $[t]P^{\prime}=[\lambda]P$
for some $\lambda\in\mathcal{O}$. Writing $Q=[a]P+[b]P^{\prime}$,

$\widehat{T}_{m}^{\tau}(P,Q)^{t}=\widehat{T}_{m}^{\tau}(P,[t]([a]P+[b]P^{\prime}))=\widehat{T}_{m}^{\tau}(P,[ta+b\lambda]P)=\widehat{T}_{m}^{\tau}(P,P)^{ta+b\lambda}.$

This has order $s$ on the left. Therefore $\widehat{T}_{m}^{\tau}(P,P)$ must
have order a multiple of $s$. Hence $s\mid m^{\prime}$.

###### Remark 2

In [4], the authors study cyclic self-pairings on oriented elliptic curves,
namely homogeneous functions $f:\langle
P\rangle\rightarrow\overline{\mathbb{F}}^{*}$ of degree $2$ which are
compatible with endomorphisms from the orientation, in the sense that $\langle
P\rangle$ is stabilized by such endomorphisms and $f(\phi P)=f(P)^{\deg\phi}$
for such endomorphisms. They show that non-trivial such pairings can only
exist for $P$ of order $m$ dividing $\Delta_{\mathcal{O}}$. The reason our
pairings are not ruled out by this result is that our pairings need not be
defined on a cyclic subgroup stabilized by the orientation. In fact, their
result can be recovered from Theorem 4.3, which implies that the pairings
$\widehat{T}_{\alpha}^{\tau}$ are trivial on cyclic subgroups stabilized by
$\mathcal{O}$.

###### Theorem 4.4

Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}$, and let
$m\in\mathbb{Z}$. Let a basis for $E[m]$ be given. Suppose arithmetic in
$\mathbb{F}$, discrete logarithms in $\mathbb{F}^{*}$ modulo $m$, and group
law computations on $E[m]$ can all be accomplished in polynomial time. Suppose
$E$ is known to be oriented by $\mathcal{O}=\mathbb{Z}[\tau]$ (but the
orientation $\iota$ is not given), and suppose $m$ is coprime to the
discriminant $\Delta_{\mathcal{O}}$. Then the computation of arbitrary
pairings $\widehat{T}^{\tau}_{m}(P,Q)$ on $E[m]$ is equivalent in polynomial
time to the computation of the action of $[\tau]$ on $E[m]$.

###### Proof

Note that since $\tau$ is known abstractly, computation of $[\tau]$ allows for
computation of $[\overline{\tau}]=[Tr(\tau)]-[\tau]$.

If $[\tau]$ is computable, then by Theorem 4.1 (5) one can compute
$\widehat{T}^{\tau}_{m}(P,Q)$ by computing $3$ multiplications by $[\tau]$ or
$[\overline{\tau}]$, one addition, and $3$ classical Tate pairings.

Conversely, suppose one can compute $\widehat{T}^{\tau}_{m}(P,Q)$ for any
$P,Q\in E[m]$. We will show how to compute the action of $[\tau]$ on $E[m]$.
The pairing is non-degenerate as a consequence of the given hypotheses. Choose
$P\in E[m]$ uniformly randomly as a linear combination of the given basis.
Compute $\widehat{T}^{\tau}_{m}(P,P)$. If it is not of order $m$, choose
another $P$.

For now, we assume that $\mathcal{O}P=E[m]$. Choose $Q\in E[m]$ so that $P,Q$
form a basis for $E[m]$. Then $Q=[\lambda]P$ for some
$\lambda\notin\mathbb{Z}$; then

$\widehat{T}^{\tau}_{m}(P,Q)=\widehat{T}^{\tau}_{m}(P,P)^{\lambda}.$

Since $\widehat{T}^{\tau}_{m}(P,P)$ is of order $m$ by Theorem 4.3, we can
compute $\lambda$ modulo $m$ by two pairing computations and a discrete
logarithm in $(\mathbb{F}^{*})^{\times 2}/((\mathbb{F}^{*})^{\times
2})^{m}\cong\mu_{m}$.

By construction, we can write $\tau=a+b\lambda$ modulo $m$, so we can compute
$[\tau]P=[a]P+[b]Q$.

To compute $[\tau]R$ for arbitrary $R$, we first determine $\mu\in\mathcal{O}$
modulo $m$ such that $R=[\mu]P$ (we may use the same discrete log method as
above), and then we have $[\tau]R=[\mu][\tau]P$.

If $\mathcal{O}P\neq E[m]$, then the algorithm is not guaranteed to be
correct. Therefore, we run the algorithm several times using different random
$P$ of order $m$. More than half of the $P\in E[m]$ of order $m$ should
generate $E[m]$ as an $\mathcal{O}$-module, since
$E[m]\cong\mathcal{O}/m\mathcal{O}$ by Theorem 3.3, and $\mathcal{O}$ can fix
at most two order $m$ subgroups. Any such $P$ has self-pairing of order $m$
(by non-degeneracy), so repeating sufficiently often and taking the majority
rule answer, this will succeed with overwhelming probability in polynomial
time.

###### Remark 3

Given any basis for $E[m]$, the pairing $\widehat{T}_{m}^{\tau}$ allows us to
compute the ‘eigenspaces’, i.e. a basis $P,Q$ such that $[\tau]P\in\langle
P\rangle$ and $[\tau]Q\in\langle Q\rangle$. That is, knowing the pairing
values on the original basis, we can solve for points with trivial self-
pairing.

###### Example 2

Consider the elliptic curve $y^{2}=x^{3}+x$ over $\mathbb{F}_{p}$, $p=541$. A
basis for $E[5]$ is $P=(109,208)$, $Q=(53,195)$. If we compute the self-
pairings $\widehat{T}_{5}^{[i]}([a]P+[b]Q,[a]P+[b]Q)$, for $a,b=0,\ldots,4$,
we obtain the following: the left matrix shows the real parts and the right
matrix the imaginary parts, taken log base a generator of $\mathbb{F}_{p}$,
namely, $48$. So, for example, the second entry on the fourth row indicates
that $\widehat{T}_{5}^{[i]}([4]P+[2]Q,[4]P+[2]Q)=(g^{3},g^{4})$.

$\left(\begin{array}[]{rrrrr}0&4&1&1&4\\\ 0&2&2&0&1\\\ 0&0&3&4&3\\\
0&3&4&3&0\\\
0&1&0&2&2\end{array}\right),\quad\left(\begin{array}[]{rrrrr}0&2&3&3&2\\\
0&1&1&0&3\\\ 0&0&4&2&4\\\ 0&4&2&4&0\\\ 0&3&0&1&1\end{array}\right).$

From this we observe that
$\widehat{T}_{5}^{[i]}(P,P)=\widehat{T}_{5}^{[i]}([2]P+Q,[2]P+Q)=1$. This is
as dictated by Theorem 4.3, because $[i]P=[3]P$ and $[i]([2]P+Q)=[2]([2]P+Q)$.

##  5 Recovering partial torsion image information

Our first observation is that when $E[m]$ is a cyclic $\mathcal{O}$-module,
the pairings recover _partial_ information about the action of a hidden
oriented isogeny $\phi$ on $E[m]$.

###### Theorem 5.1

Let $E$ and $E^{\prime}$ be $\mathcal{O}$-oriented supersingular curves over
$\overline{\mathbb{F}}_{p}$ upon which we can efficiently compute the action
of a generator $\tau$ for $\mathcal{O}$. Assume that the discrete logarithm in
$\mu_{m}$ and group operations on $E[m]$ are efficient. Assume also that
$E[m]$ is a cyclic $\mathcal{O}$-module, and that the hidden oriented isogeny
$\phi:E\rightarrow E^{\prime}$ has known degree coprime to $m$. Suppose we are
given $P$ and $P^{\prime}$ such that $\mathcal{O}P=E[m]$ and
$\mathcal{O}P^{\prime}=E^{\prime}[m]$. Then we can efficiently recover
$N(\lambda)$ modulo $m$ for $\lambda\in\mathcal{O}$ such that $\phi
P=[\lambda]P^{\prime}$.

###### Proof

We have

$\widehat{T}^{\tau}_{m}(P,P)^{\deg\phi}=\widehat{T}^{\tau}_{m}(\phi P,\phi
P)=\widehat{T}^{\tau}_{m}(\lambda P^{\prime},\lambda
P^{\prime})=\widehat{T}^{\tau}_{m}(P^{\prime},P^{\prime})^{N(\lambda)}.$

Note that by Theorem 4.3, $\widehat{T}^{\tau}_{m}(P,P)$ has order $m$. Since
$m$ is smooth, using the reduced pairing, we can solve a discrete log problem
in $\mu_{m}$ to obtain $N(\lambda)$ modulo $m$.

###### Remark 4

This result would provide a square-root improvement on an exhaustive search
over image points of $P$. More precisely, one could attack the class group
action problem by trying all possible image points $\phi P$ for $P$, infer
$\phi[\tau]P=[\tau]\phi P$, and therefore use the image of the $m$-torsion as
input to the SIDH attacks, checking for success at each attempt. This is
similar to [14, Section 4.1], for example. Here, the knowledge of $N(\lambda)$
restricts $\phi P$ to only $O(m)$ possible images, not $m^{2}$. This may
provide another $O(\sqrt{p})$ runtime classical attack on CSIDH, for example.
Attacks with this runtime already exist using random walks [15, 16]. To run
such an exhaustive search SIDH attack, we need the degree of $\phi$ to be
known and $m^{2}>\deg\phi$, $m$ to be coprime to $\deg\phi$, and $m$ to be
smooth. Since we have great freedom in choosing $m$, we can expect to choose
an $m$ around $\sqrt{\deg\phi}$. Then we have to try approximately $m$
different images $\lambda P^{\prime}$ of $P$ which give $N(\lambda)$ as
computed, running the SIDH attack on each. This attack applies very generally
in the setup of the theorem above, whereas the attacks of [16] require a
variety of hypotheses.

###### Remark 5

This and other similar results in this paper and in [13] are a caution against
decision Diffie-Hellman problems in which one must decide if a given point is
the image point of a specified torsion point under a hidden isogeny. A result
like the previous one reduces the possibilities for the torsion image (without
pinning it down entirely). For an example, the IND-CPA hardness of SiGamal
[21] depends upon such a problem, called the P-CSSDDH assumption. This is
discussed in [4, Section 6.1], where the authors lament the triviality of the
available self-pairings. There are non-trivial pairings of the type
$\widehat{T}$ and $\widehat{W}$ which would apply to the SiGamal situation,
but only if we had access to a different orientation on the curves and
isogeny. The Frobenius orientation used in the P-CSSDDH assumption results in
a trivial pairing once again, because the torsion is contained in the base
field.

###### Remark 6

There is a sense in which we cannot hope to obtain more information than
$N(\lambda)$ modulo $m$ using these methods. If we post-compose our isogeny
with an endomorphism from $\mathcal{O}$ of norm $1$ modulo $m$, then we do not
change the degree modulo $m$, but we do change $\lambda$, replacing it with
another $\lambda^{\prime}$ having the same norm modulo $m$. To detect the
difference, we must feed in more information than just the degree modulo $m$.
In fact, it is possible to recover the same result by a different method. Take
a basis for $E$ and $E^{\prime}$ and change basis so that the Weil pairing
takes a canonical diagonal form. Then the set of possible endomorphisms in
$\mathcal{O}$ that preserve this diagonal form turns out to be the same
‘degree of freedom’ of $\lambda$ observed above. The pairings from [4] can be
seen as getting around this by assuming $\lambda\in\mathbb{Z}$, in which case
$N(\lambda)$ pins down $\lambda$ more effectively.

###### Remark 7

In principle, the result above doesn’t require using $\widehat{T}$; it could
be phrased in terms of one of the coordinates in Theorem 4.1 (5). This
wouldn’t violate the classification of cyclic self-pairings in [4] because the
domain is not $\mathbb{Z}$-cyclic.

##  6 Reduction from SIDH1 to SIDH

In [13], the authors consider a variety of variants on the SIDH problem which
can be parameterized by the information available about the action of $\phi$
on the $m$-torsion (_level structure_ information). In particular, they define
the following problem.

######  Problem 1 (SIDH1)

Fix $d,m\in\mathbb{Z}$. Let $E,E^{\prime}$ be elliptic curves defined over
$\mathbb{F}_{q}$, where $m$ is coprime to $q$. Let $P\in E[m]$ have order $m$.
Suppose there exists an isogeny $\phi:E\rightarrow E^{\prime}$ of known degree
$d$ and $\phi P$ is given. Find $\phi$.

This can be compared to the classical SIDH problem, in which we are given full
torsion image information.

######  Problem 2 (SIDH)

Fix $d,m\in\mathbb{Z}$. Let $E,E^{\prime}$ be elliptic curves defined over
$\mathbb{F}_{q}$, where $m$ is coprime to $q$. Let $P,Q$ form a basis for
$E[m]$. Suppose there exists an isogeny $\phi:E\rightarrow E^{\prime}$ of
known degree $d$ and $\phi P$ and $\phi Q$ are given. Find $\phi$.

In either case we refer to $m$ as the _level_ of the SIDH or SIDH1 problem.
The authors of [13] show that if $m$ has a large smooth square factor, then
SIDH1 of level $m$ (a single torsion point image of order $m$) reduces to SIDH
of level $O(\sqrt{m})$ (two torsion point images of order $O(\sqrt{m})$). More
recently, a manuscript in preparation (presented at Caipi Symposium 2024 [3])
generalizes the SIDH attacks of [2, 20, 23], directly attacking SIDH1 without
the requirement that $m$ have a large square factor. Both approaches require
that $m>\deg\phi$.

Here we show that, _if we have an oriented isogeny_ , knowing a single image
of order $m$ is enough to reduce to SIDH of level $m$ (on the same curve),
assuming only that $m$ is smooth, with no assumption on $m$ being square, and
no loss in level. Thus using the SIDH attacks requires only $m^{2}>\deg\phi$.

###### Theorem 6.1

Let $E$ and $E^{\prime}$ be $\mathcal{O}$-oriented supersingular curves over
$\overline{\mathbb{F}}_{p}$, upon which we can efficiently compute the action
of endomorphisms from $\mathcal{O}$. Assume that $m$ is smooth and coprime to
the discriminant. Assume also that $E[m]$ is a cyclic $\mathcal{O}$-module,
and that the hidden isogeny $\phi:E\rightarrow E^{\prime}$ has known degree
coprime to $m$. Then the problem SIDH1 of level $m$ to find $\phi$ reduces, in
a polynomial number of operations in the field of definition of $E[m]$, to
SIDH of level $m$ on the same curve $E$ and same $\phi$.

###### Proof

We are given $\phi R$ for some point $R\in E[m]$ of order $m$. We wish to
recover a second torsion point image, resulting in an SIDH problem. First, by
Sunzi’s Theorem, we can reduce the problem to prime powers $m=p^{k}$. By
assumption, $p$ is not ramified. Hence we may assume $p$ is a split or inert.

Case that $p$ is inert. We know $\mathcal{O}R$ is an $\mathcal{O}$-submodule
of $E[m]\cong\mathcal{O}/m\mathcal{O}$. If $p$ is inert, it must be isomorphic
to $\mathcal{O}/p^{s}\mathcal{O}$. However, $\mathcal{O}/p^{s}\mathcal{O}$
doesn’t have elements of additive order $p^{k}$ unless $s=k$. Thus
$\mathcal{O}R=E[m]$. Given any other point $Q$, we may compute $\eta$ such
that $Q=[\eta]R$ (using basis $R$ and $[\tau]R$). Then $\phi
Q=\phi[\eta]R=[\eta]\phi R$.

Case that $p$ is split. Write $m=p^{k}=\mathfrak{b}\overline{\mathfrak{b}}$,
where $N(\mathfrak{b})=m$. Then we have, without loss of generality, $S,T$ a
basis for $E[m]$ so that $\mathfrak{b}T=\\{\mathcal{O}\\}$, and
$\overline{\mathfrak{b}}S=\\{\mathcal{O}\\}$. Similarly, let $S^{\prime}$ and
$T^{\prime}$ be a basis for $E[m]$ so that
$\mathfrak{b}T^{\prime}=\\{\mathcal{O}\\}$ and
$\overline{\mathfrak{b}}S^{\prime}=\\{\mathcal{O}\\}$. To find such a basis,
one could use Remark 3 or more standard methods.

Now the mapping $\phi$, as a matrix from basis $S,T$ to basis
$S^{\prime},T^{\prime}$, is diagonal, with some integers $k_{1}$ and $k_{2}$
on the diagonal. By writing $R$ and $\phi R$ in the relevant bases, namely
$R=[a]S+[b]T$, $\phi R=[c]S^{\prime}+[d]T^{\prime}$, we learn that
$ak_{1}\equiv c,bk_{2}\equiv d\pmod{m}$. We also know that $\deg\phi\equiv
k_{1}k_{2}\pmod{m}$. Without loss of generality, at least one of $a$ or $b$ is
coprime to $m$, so we know at least one of $k_{1}$ or $k_{2}$, and the degree
equation then gives us the other.

##  7 Diagonal SIDH

The following problem arises in [13, Lemma 6 and Section 5.6].

######  Problem 3 (Diagonal SIDH)

Fix $d,m\in\mathbb{Z}$. Let $E,E^{\prime}$ be elliptic curves defined over
$\mathbb{F}_{q}$, where $m$ is coprime to $q$. Let $P,Q\in E[m]$ form a basis.
Suppose there exists an isogeny $\phi:E\rightarrow E^{\prime}$ of known degree
$d$. Suppose that generators $P^{\prime}$ of $\langle\phi P\rangle$ and
$Q^{\prime}$ of $\langle\phi Q\rangle$ are known.

Interestingly, when the curves are oriented, the Diagonal SIDH problem is
amenable to a pairing-based attack, at least for certain conditions on $E[m]$.

###### Theorem 7.1

Suppose $E$ and $E^{\prime}$ are $\mathcal{O}$-oriented (and one can compute
the action of the endomorphisms efficiently, as usual). Let $m$ be a smooth
integer such that modulo $m$, $1$ has polynomially many square roots. Then
Diagonal SIDH with known degree for an oriented isogeny $\phi:E\rightarrow
E^{\prime}$ is solvable in polynomial time, provided $\mathcal{O}P=E[m]$ or
$\mathcal{O}Q=E[m]$.

###### Proof

Let the Diagonal SIDH problem be given in terms of basis $P,Q$ for $E[m]$ and
generators $P^{\prime}$ and $Q^{\prime}$ for $\langle\phi P\rangle$ and
$\langle\phi Q\rangle$ respectively. Assume without loss of generality that
$\mathcal{O}P=E[m]$. Then by Theorem 5.1, we can efficiently recover
$N(\lambda)$ such that $\phi P=\lambda P^{\prime}$. However, the Diagonal SIDH
setup guarantees that $\lambda\in\mathbb{Z}$, hence we have recovered
$\lambda^{2}$ modulo $m$. By assumption, this gives only polynomially many
possible values for $\lambda$, each of which can be tested by running the SIDH
attacks, until one recovers $\phi$.

An instance of the Diagonal SIDH problem is the problem underlying the FESTA
cryptosystem [1, Problem 7]. In this case $m$ is chosen to be a power of $2$,
so the attack above would apply if FESTA were instantiated in a situation
where the isogeny was oriented (for known orientations). Assuming an
$\mathcal{O}$-orientation, the condition $\mathcal{O}P=E[m]$ or
$\mathcal{O}Q=E[m]$ is reasonably likely to occur by chance if not explicitly
avoided.

###### Corollary 1

The hard problem underlying FESTA reduces to finding explicit
$\mathcal{O}$-orientations of the curves $E$ and $E^{\prime}$ and the isogeny
$\phi$ between them.

###### Remark 8

In [13, Section 5.6], it is shown how to reformulate the problem of finding an
isogeny of fixed degree $d$ between oriented curves (the class group action
problem) as a Diagonal SIDH problem, where $m$ is a product of primes split in
$\mathcal{O}$. The method of reduction, in brief, uses the eigenspaces
associated to a split prime in the orientation, which must map to each other.
However, the conditions under which Theorem 7.1 applies – that $m$ have few
square roots, and $P$ or $Q$ be generators of $E[m]$ as an
$\mathcal{O}$-module – both fail in the Diagonal SIDH problems that result
from the reduction of [13]. This means we cannot chain these attacks together
to attack class group action problems!

##  8 When $N$ divides the discriminant

Suppose $N\mid\Delta_{\mathcal{O}}$, where $N=N(\tau)$ for
$\tau\in\mathcal{O}$. In this case the pairing $\widehat{T}^{\tau}_{N}$
becomes trivial. However, a modification is more interesting. Let
$n\in\mathbb{Z}$, and define

$T^{\prime}_{n}(P,Q)=\left(t_{n}([\tau]P,Q),t_{n}(P,Q)\right)\in((\mathbb{F}^{*})/(\mathbb{F}^{*})^{n}))^{\times
2}.$

This modification does not preserve all of the properties of Theorem 4.1 but
importantly, it inherits compatibility from $t_{n}$, so that for
$\phi:E\rightarrow E^{\prime}$ compatible with $\mathcal{O}$, we have

$T^{\prime}_{n}(\phi Q,\phi Q)=T^{\prime}_{n}(Q,Q)^{\deg\phi}.$

In [4], the authors use generalized pairings to determine the image of a
single torsion point in $E[N]$, and then reduce to SIDH with $E[\sqrt{N}]$
when $N$ is a smooth square. In fact, recent further development of the SIDH
attacks (in preparation [3]) generalize to image information on subgroups of a
large enough size, not just full torsion subgroups, which effectively removes
the restriction that $N$ be square.

Inspired by this result, we develop a similar reduction using the pairing
above. The main advantage of our situation over that in [4] is the computation
of the pairing, which requires only operations in the field of definition of
$E[N]$. Because the pairings used in [4] may require a move to the field of
definition of $E[N^{2}]$, our pairings result in a speedup in cases where that
field of definition is large.

###### Lemma 2

Let $E$ have an orientation by $\mathcal{O}=\mathbb{Z}[\tau]$, and let $P\in
E[m]$ be such that $\langle[\tau]P\rangle\cap\langle P\rangle=\\{0\\}$. Let
$t$ be the minimal positive integer such that $[t]E[m]\subseteq\mathcal{O}P$.
Let $f$ be the relative conductor of $\mathcal{O}$, so that
$\tau=f\tau^{\prime}$ for another endomorphism $\tau^{\prime}$. Let
$g=\gcd(m,f)$ and let $n=\gcd(N(\tau^{\prime}),m)$. Then, $g\leq t\leq gn$.

###### Proof

As a direct consequence of the hypotheses, $[\tau]P=[f][\tau^{\prime}]P\in
E[m/g]$. On the other hand, $[\tau]P$ has order at least $m/gn$. Therefore
$[\tau]P$ has order $s$ satisfying $m/gn\leq s\leq m/g$. By assumption,
$\langle[\tau]P\rangle\cap\langle P\rangle=\\{0\\}$. Therefore, $s$ is the
maximal integer dividing $m$ such that $E[s]\subseteq\mathcal{O}P$. But
$E[s]=[m/s]E[m]$.

###### Proposition 2

Let $E$ be an elliptic curve oriented by $\mathcal{O}=\mathbb{Z}[\tau]$. Let
$\mathbb{F}$ be a finite field containing the $m$-th roots of unity. Suppose
$E[m]=E[m](\mathbb{F})$ is a cyclic $\mathcal{O}$-module. Let $P\in E[m]$.
Then the multiplicative order $T^{\prime}_{m}(P,P)$ is $m/t$ where $t$ is the
minimal positive integer such that $[t]E[m]\subseteq\mathcal{O}P$.

###### Proof

The classical Tate-Lichtenbaum pairing

$t_{m}:E[m](\mathbb{F})\times
E(\mathbb{F})/[m]E(\mathbb{F})\rightarrow\mathbb{F}^{*}/(\mathbb{F}^{*})^{m}$

is non-degenerate and, for $P$ of order $m$, there exists a $Q$ so
$t_{m}(P,Q)$ has order $m$ (Proposition 1). Let $t$ be the minimal positive
integer for which $[t]E[m]\subseteq\mathcal{O}P$. Then $[t]Q=[a+\tau b]P$ for
some $a,b$ having $\gcd(a,b,m)=1$.

$\displaystyle T^{\prime}_{m}(P,Q)^{t}$
$\displaystyle=T^{\prime}_{m}(P,[a+\tau b]P)$
$\displaystyle=T^{\prime}_{m}(P,P)^{a}T^{\prime}_{m}(P,[\tau]P)^{b}$
$\displaystyle=(t_{m}([\tau]P,P)^{a}t_{n}(P,P)^{N(\tau)b},t_{m}(P,P)^{a}t_{m}([\tau]P,P)^{b}).$

The left side has order $m/t$. Thus the right side has order $m/t$; applying a
linear transformation, $T^{\prime}_{m}(P,P)$ must have order $m/t$.

In the following, we assume $E[m]$ is a cyclic $\mathcal{O}$-module. By
Theorem 3.3, it suffices that the $\mathcal{O}$-orientation be $m$-primitive.

###### Theorem 8.1

Let $E$ and $E^{\prime}$ be $\mathcal{O}$-oriented elliptic curves. Suppose
there exists an oriented $\phi:E\rightarrow E^{\prime}$ of known degree $d$.
Let $m$ be smooth, coprime to $d$, and chosen so that there are only
polynomially many square roots of $1$ modulo $m$. Suppose there exists
$\tau\in\mathcal{O}$ with norm $N(\tau)\equiv\Delta_{\mathcal{O}}\equiv
0\pmod{m}$. Suppose that $E[m]$ is a cyclic $\mathcal{O}$-module. Suppose
$P\in E[m]$ such that $\mathcal{O}P=E[m]$. Then a subset $S\subset E[m]$ of
polynomial size containing $\phi(P)$ can be computed in polynomially many
operations in the field of definition of $E[m]$.

###### Proof

As explained in [4, Section 5.2], we can find $\tau\in\mathcal{O}$ such that
$N(\tau)\equiv Tr(\tau)\equiv 0\pmod{m}$. Hence the minimal polynomial of
$\tau$ is $x^{2}$ modulo $m$, and $\tau^{2}$ acts as $0$ on
$\mathcal{O}/m\mathcal{O}$. Choose a point $P\in E[m]$ such that
$\mathcal{O}P=E[m]$. Choose a point $P^{\prime}\in E^{\prime}[m]$ such that
$\mathcal{O}P^{\prime}=E^{\prime}[m]$. Then $T^{\prime}_{m}(P,P)$ and
$T^{\prime}_{m}(P^{\prime},P^{\prime})$ have order $m$ by Proposition 2. Then

${T}^{\prime}_{m}(P,P)^{\deg\phi}=T^{\prime}_{m}(\phi P,\phi
P)=T^{\prime}_{m}(\lambda P^{\prime},\lambda
P^{\prime})=T^{\prime}_{m}(P^{\prime},P^{\prime})^{N(\lambda)}.$

Using a discrete logarithm, we can compute $N(\lambda)\pmod{m}$. Write
$\lambda=a+b\tau$. Then $N(\lambda)\equiv a^{2}\pmod{m}$. Since the
factorization of $m$ is known, by assumption, we have an efficiently
computable set of polynomial size of possible values of $a$. Compute
$[a][\tau]P^{\prime}$. For the correct $a$, this is the image of $[\tau]P$
under $\phi$, since

$\phi[\tau]P=\lambda[\tau]P^{\prime}=[a][\tau]P^{\prime}.$

Trying all possible values of $a$, we obtain the set
$\\{[a][\tau]P^{\prime}:a^{2}\equiv N(\lambda)\pmod{m}\\}$ required by the
statement.

The results of [4, 13] can now be applied if $m$ is a smooth square, $d$ is
powersmooth and $m>d$, to reduce to a solvable instance of SIDH.
Alternatively, loosening the restriction that $m$ is a square will be possible
with the new generalizations of SIDH mentioned above [3].

###### Example 3

The following example is based on an example communicated to the authors by
Wouter Castryck. Let $E:y^{2}=x^{3}+x$. Let $p$ be a prime of the form $4\cdot
3^{r}-1$ with $r>0$. This curve is supersingular with $j=1728$ and
endomorphisms $[i]:(x,y)\mapsto(-x,iy)$ and
$\pi_{p}:(x,y)\mapsto(x^{p},y^{p})$. Let

$\tau:=\frac{i+\pi_{p}}{2}\in\operatorname{End}(E).$

Then $\tau^{2}=-\frac{p+1}{4}=-3^{r}$, so $N(\tau)=3^{r}$. Since
$\pi_{p}^{2}=[-p]$,
$E(\mathbb{F}_{p^{2}})\cong(\mathbb{Z}/(p+1)\mathbb{Z})^{2}\cong(\mathbb{Z}/4\cdot
3^{r}\mathbb{Z})^{2}$ [25, Ex. 5.16.d]. Therefore $E[3^{r}]\subseteq
E(\mathbb{F}_{p^{2}})$.

We can choose $m=3^{r}$, which is a square when $r$ is even. Let $Q$ be an
$\mathcal{O}$-generator of $E[3^{r}]$. Then by Proposition 2,
$T^{\prime}_{m}(Q,Q)$ has order $3^{r}$, and the polynomially many operations
to run the attack of Theorem 8.1 take place in $\mathbb{F}_{p^{2}}$. The SIDH
portion of the attack requires that $d<m=3^{r}$.

By contrast, using the methods of [4, Section 6.1], one would need a
generalized pairing value of $T^{\tau}_{m}$ for which only methods of
computation taking place in the field of definition of $E[3^{2r}]$ are known.

##  9 Supersingular class group action in the presence of another orientation

###### Theorem 9.1

Let $E$ and $E^{\prime}$ be elliptic curves for both of which we know
orientations by two orders $\mathcal{O}$ and $\mathcal{O}^{\prime}$ which
generate a rank $4$ sub-order of the endomorphism ring. Let $\phi:E\rightarrow
E^{\prime}$ be an isogeny of known degree $d$. Let $m$ be smooth, coprime to
the discriminants of $\mathcal{O}$ and $\mathcal{O}^{\prime}$, and suppose $1$
has only polynomially many square roots modulo $m$. Suppose $\phi$ respects
both the $\mathcal{O}$ and $\mathcal{O}^{\prime}$ orientations. Let $P\in
E[m]$. Then a subset of $E^{\prime}[m]$ of polynomial size containing $\phi P$
can be computed in polynomially many operations in the field of definition of
$E[m]$.

###### Proof

By assumption, $m$ is coprime to the discriminants. Thus we can choose $P\in
E[m]$ so that $\mathcal{O}P=E[m]$. Similarly, let $P^{\prime}\in
E^{\prime}[m]$ be chosen so that $\mathcal{O}P^{\prime}=E^{\prime}[m]$.
Suppose $\phi P=[\lambda]P^{\prime}$ for some $\lambda\in\mathcal{O}$. As in
Theorem 6.1, we can compute $N(\lambda)$ modulo $m$.

Let $\sigma\in\mathcal{O}^{\prime}$ be chosen to have norm coprime to $m$ and
be of the form $\sigma=a\sigma_{1}+b\sigma_{2}$ with $a$ and $b$ coprime to
$m$, where $\sigma_{1}\in\mathcal{O}$ and $\sigma_{2}$ is perpendicular to
$\mathcal{O}$ in the geometry afforded by the norm map on the quaternion
algebra, so that $\sigma_{2}\lambda=\overline{\lambda}\sigma_{2}$. Write
$\lambda^{\sigma}$ for an element which participates in the equivalence
$\lambda^{\sigma}\sigma\equiv\sigma\lambda\pmod{m}$. This can be computed by
taking $\lambda^{\sigma}=\sigma\lambda\overline{\sigma}N$ where $N$ is an
integer equivalent to $N(\sigma)^{-1}\pmod{m}$. Then
$\overline{\lambda^{\sigma}}\equiv a\overline{\lambda}+b{\lambda}\pmod{m}$.
Then

$\displaystyle\widehat{T}_{m}^{\tau}([\sigma]P,P)^{\deg\phi}$
$\displaystyle=\widehat{T}_{m}^{\tau}(\phi[\sigma]P,\phi P)$
$\displaystyle=\widehat{T}_{m}^{\tau}([\sigma]\phi P,\phi P)$
$\displaystyle=\widehat{T}_{m}^{\tau}(\sigma[\lambda]P^{\prime},[\lambda]P^{\prime})$
$\displaystyle=\widehat{T}_{m}^{\tau}([\lambda^{\sigma}][\sigma]P^{\prime},[\lambda]P^{\prime})$
$\displaystyle=\widehat{T}_{m}^{\tau}([\sigma]P^{\prime},P^{\prime})^{\overline{\lambda^{\sigma}}\lambda}.$

Since the norm of $\sigma$ is coprime to $m$,
$\widehat{T}_{m}^{\tau}([\sigma]P,P)$ has the same order as
$\widehat{T}_{m}^{\tau}(P,P)$, which is $m$ by Theorem 4.3. Thus, we can
compute $\overline{\lambda^{\sigma}}\lambda$ modulo $m$ by performing a
discrete logarithm in $\mu_{m}$.

Using knowledge of $\overline{\lambda^{\sigma}}\lambda\equiv
aN(\lambda)+b\lambda^{2}$ and $N(\lambda)$, both modulo $m$, and recalling $b$
is coprime to $m$, we obtain $\lambda^{2}$ modulo $m$.

Using $N(\lambda)$ and $\lambda^{2}$, we can solve for polynomially many
possibilities for $\lambda$ modulo $m$. Then we have obtained $\phi P$. From
this we can compute any other $\phi R$ by solving for $R=[\mu]P$ and observing
that $\phi R=\phi[\mu]P=[\mu]\phi P$.

### Acknowledgements

The authors are grateful to Damien Robert and Wouter Castryck for helpful
discussions. Both authors are supported by NSF CAREER CNS-1652238 and NSF
DMS-2401580 (PI K. E. Stange).

###

The authors have no competing interests to declare that are relevant to the
content of this article.

## References

  * [1] Basso, A., Maino, L., Pope, G.: FESTA: fast encryption from supersingular torsion attacks. In: Advances in cryptology—ASIACRYPT 2023. Part VII, Lecture Notes in Comput. Sci., vol. 14444, pp. 98–126. Springer, Singapore ([2023] ©2023). https://doi.org/10.1007/978-981-99-8739-9_4, https://doi-org.colorado.idm.oclc.org/10.1007/978-981-99-8739-9_4
  * [2] Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Advances in cryptology—EUROCRYPT 2023. Part V, Lecture Notes in Comput. Sci., vol. 14008, pp. 423–447. Springer, Cham ([2023] ©2023). https://doi.org/10.1007/978-3-031-30589-4_15, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-031-30589-4_15
  * [3] Castryck, W., Decru, T., Maino, L., Martindale, C., Panny, L., Pope, G., Robert, D., Wesolowski, B.: Isogeny interpolation (2024), manuscript in preparation, presented at Caipi Symposium, Rennes, April 30, 2024, https://caipi_symposium.pages.math.cnrs.fr/page-web/editions/avr24.html
  * [4] Castryck, W., Houben, M., Merz, S.P., Mula, M., Buuren, S.v., Vercauteren, F.: Weak instances of class group action based cryptography via self-pairings. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023\. pp. 762–792. Springer Nature Switzerland, Cham (2023)
  * [5] Castryck, W., Houben, M., Vercauteren, F., Wesolowski, B.: On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves. Res. Number Theory 8(4), Paper No. 99, 18 (2022). https://doi.org/10.1007/s40993-022-00399-6, https://doi-org.colorado.idm.oclc.org/10.1007/s40993-022-00399-6
  * [6] Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Advances in cryptology—ASIACRYPT 2018. Part III, Lecture Notes in Comput. Sci., vol. 11274, pp. 395–427. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03332-3_15, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-030-03332-3_15
  * [7] Castryck, W., Sotáková, J., Vercauteren, F.: Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: extended version. J. Cryptology 35(4), Paper No. 24, 30 (2022). https://doi.org/10.1007/s00145-022-09435-1, https://doi-org.colorado.idm.oclc.org/10.1007/s00145-022-09435-1
  * [8] Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptology 22(1), 93–113 (2009). https://doi.org/10.1007/s00145-007-9002-x, https://doi-org.colorado.idm.oclc.org/10.1007/s00145-007-9002-x
  * [9] Colò, L., Kohel, D.: Orienting supersingular isogeny graphs. J. Math. Cryptol. 14(1), 414–437 (2020). https://doi.org/10.1515/jmc-2019-0034, https://doi-org.colorado.idm.oclc.org/10.1515/jmc-2019-0034
  * [10] Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291 (2006), https://eprint.iacr.org/2006/291, https://eprint.iacr.org/2006/291
  * [11] Cox, D.A.: Primes of the Form $x^{2}+ny^{2}$: Fermat, Class Field Theory, and Complex Multiplication. Third Edition with Solutions. AMS Chelsea Publishing (2022)
  * [12] Eisenträger, K., Hallgren, S., Leonardi, C., Morrison, T., Park, J.: Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs. In: ANTS XIV—Proceedings of the Fourteenth Algorithmic Number Theory Symposium. Open Book Ser., vol. 4, pp. 215–232. Math. Sci. Publ., Berkeley, CA (2020). https://doi.org/10.2140/obs.2020.4.215, https://doi-org.colorado.idm.oclc.org/10.2140/obs.2020.4.215
  * [13] De Feo, L., Fouotsa, T.B., Panny, L.: Isogeny problems with level structure. Springer-Verlag (2024)
  * [14] Fouotsa, T.B., Moriya, T., Petit, C.: M-SIDH and MD-SIDH: countering SIDH attacks by masking information. In: Advances in cryptology—EUROCRYPT 2023. Part V, Lecture Notes in Comput. Sci., vol. 14008, pp. 282–309. Springer, Cham ([2023] ©2023). https://doi.org/10.1007/978-3-031-30589-4_10, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-031-30589-4_10
  * [15] Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118–138 (1999). https://doi.org/10.1112/S1461157000000097, https://doi-org.colorado.idm.oclc.org/10.1112/S1461157000000097
  * [16] Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil descent attack. In: Advances in cryptology—EUROCRYPT 2002 (Amsterdam), Lecture Notes in Comput. Sci., vol. 2332, pp. 29–44. Springer, Berlin (2002). https://doi.org/10.1007/3-540-46035-7_3, https://doi-org.colorado.idm.oclc.org/10.1007/3-540-46035-7_3
  * [17] Ionica, S., Joux, A.: Pairing the volcano. Math. Comp. 82(281), 581–603 (2013). https://doi.org/10.1090/S0025-5718-2012-02622-6, https://doi-org.colorado.idm.oclc.org/10.1090/S0025-5718-2012-02622-6
  * [18] Kohel, D., Lauter, K., Petit, C., Tignol, J.P.: On the quaternion $\ell$-isogeny path problem. LMS J.Comput. Math. (2014)
  * [19] Lenstra, Jr., H.W.: Complex multiplication structure of elliptic curves. J. Number Theory 56(2), 227–241 (1996). https://doi.org/10.1006/jnth.1996.0015, https://doi-org.colorado.idm.oclc.org/10.1006/jnth.1996.0015
  * [20] Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Advances in cryptology—EUROCRYPT 2023. Part V, Lecture Notes in Comput. Sci., vol. 14008, pp. 448–471. Springer, Cham ([2023] ©2023). https://doi.org/10.1007/978-3-031-30589-4_16, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-031-30589-4_16
  * [21] Moriya, T., Onuki, H., Takagi, T.: SiGamal: a supersingular isogeny-based PKE and its application to a PRF. In: Advances in cryptology—ASIACRYPT 2020. Part II, Lecture Notes in Comput. Sci., vol. 12492, pp. 551–580. Springer, Cham ([2020] ©2020). https://doi.org/10.1007/978-3-030-64834-3_19, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-030-64834-3_19
  * [22] Robert, D.: The geometric interpretation of the Tate pairing and its applications. Cryptology ePrint Archive, Paper 2023/177 (2023), https://eprint.iacr.org/2023/177, https://eprint.iacr.org/2023/177
  * [23] Robert, D.: Breaking SIDH in polynomial time. In: Advances in cryptology—EUROCRYPT 2023. Part V, Lecture Notes in Comput. Sci., vol. 14008, pp. 472–503. Springer, Cham ([2023] ©2023). https://doi.org/10.1007/978-3-031-30589-4_17, https://doi-org.colorado.idm.oclc.org/10.1007/978-3-031-30589-4_17
  * [24] Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Paper 2006/145 (2006), https://eprint.iacr.org/2006/145, https://eprint.iacr.org/2006/145
  * [25] Silverman, J.H.: The Arithmetic of Elliptic Curves, Second Edition. Springer (2009)
  * [26] Stange, K.E.: Sesquilinear pairings on elliptic curves (2024), https://arxiv.org/abs/2405.14167
  * [27] Wesolowski, B.: The supersingular isogeny path and endomorphism ring problems are equivalent. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, pp. 1100–1111. IEEE Computer Soc., Los Alamitos, CA ([2022] ©2022). https://doi.org/10.1109/FOCS52979.2021.00109, https://doi-org.ezproxy.lib.ucalgary.ca/10.1109/FOCS52979.2021.00109


# Linear-in-temperature conductance in electron hydrodynamics

Serhii Kryhin, Qiantan Hong and Leonid Levitov  Department of Physics,
Massachusetts Institute of Technology, Cambridge, MA 02139

###### Abstract

A $T$-linear temperature dependence of transport coefficients in metals is
habitually associated with non-Fermi-liquid physics. Contrary to this common
lore, here we establish this behavior for 2D electron fluids with simple Fermi
surfaces, where it supersedes the Fermi-liquid $T^{2}$ scaling. The $T$-linear
scaling originates from nonclassical hydrodynamics governed by long-lived
excitations and multiple viscous modes unique to 2D Fermi systems, which
result in Kolmogorov-like fractional power law $-5/3$ scaling of conductivity
with the wavenumber. The anomalous $T$ dependence, which extends down to
lowest temperatures, provides a smoking gun for nonclassical hydrodynamics and
is expected to be generic for strongly-correlated systems that host soft
quantum-critical modes. These findings explain the linear $T$ dependence of
conductance recently measured in 2D electron fluids.

Unusual temperature dependence of transport properties in metals often hints
at exotic physics resulting from electron interactions. A celebrated example
of this is the linear temperature ($T$) dependence of resistivity observed in
different strongly correlated systems, particularly in the vicinity of
quantum-critical points[1, 2, 3, 4, 5, 6, 7, 8]. Linear $T$ dependence of
resistivity that extends to lowest temperatures has become a powerful tool for
discerning non-Fermi-liquid phenomena that arise from strong interactions,
such as scattering by emergent gauge fields and quantum-critical soft modes of
different kinds[9, 10, 11]. This stands in contrast with quadratic ($T^{2}$)
scaling of transport coefficients predicted by conventional Fermi-liquid
physics (see [13, 12] and references therein).

Here our aim is to extend these ideas to the domain of electron
hydrodynamics[14, 20, 29, 15, 17, 18, 21, 26, 27, 28, 16, 17, 19, 30, 31, 32,
33, 37, 38, 39, 40, 42, 41, 34, 35, 36, 22, 24, 23, 25]. Recently it was
emphasized that currents in electron fluids are governed by a nonlocal
conductivity, featuring a power-law dependence on the wavenumber. Different
exponent values have been identified for various regimes [37, 38, 39, 40],
with the singularity at small wavenumbers indicating the significant role of
long-wavelength modes. It is instructive to draw parallels to theories of non-
Fermi-liquids, which predict fractional power-law scaling in frequency-
dependent optical conductivity, such as $\sigma(\omega)\sim\omega^{-2/3}$ for
$\omega\ll E_{F}$, and establish a connection between this fractional scaling
and a linear temperature-dependent resistivity [9, 10, 11].

In a similar vein, this paper will demonstrate a linear temperature scaling of
nonlocal conductivity for two-dimensional electron fluids with simple Fermi
surfaces:

$\sigma(k)\sim\frac{T}{k^{5/3}}n,$ (1)

where $n$ is carrier density. The Kolmogorov-like fractional power-law
dependence in Eq.(1) arises as a cumulative effect of many long-lived modes.
For a flow in a realistic geometry such as that shown in Fig.1, scaling in $k$
translates into the dependence on the aperture.

This surprising result, derived in the absence of momentum relaxation by
disorder or phonons, is valid in a wide range of $k$ extending to values much
greater than the nominal viscous/ballistic crossover $k\ell_{\rm ee}\sim 1$
(see Fig.3). Underpinning it is nonclassical hydrodynamics[38] driven by long-
lived odd-parity excitations with super-Fermi-liquid decay rates $\gamma_{\rm
odd}\sim T^{4}$ which occur alongside the excitations with normal Fermi-liquid
decay rates $\gamma_{\rm even}\sim T^{2}$ [41, 40]. These excitations alter
the hydrodynamics, creating multiple viscous modes with long lifetimes.

Figure 1:  Conventional Fermi-liquid (FL) and unconventional (super-FL)
hydrodynamics in an electron gas illustrated for transport through an
aperture. Hydrodynamic FL flow occurs when particle collision mean free path
$l_{\rm ee}$ is smaller than the aperture. Super-FL hydrodynamic flow has a
completely different structure, manifested in a fractional-power divergence in
$k$, Eq.(1). At small $T$, typical trajectory experiences many backreflections
at small angles $\theta_{T}\sim T/T_{F}$, allowing particles to propagate out
and then return as holes [38, 41]. Super-FL hydrodynamics occurs when $l_{\rm
ee}\theta_{T}$ is smaller than the aperture. Conductance behaves as $T^{2}$
for FL hydrodynamics and as $T$ for super-FL hydrodynamics, as visualized in
Fig.3.

Scaling linear in $T$ arising from microscopic rates behaving as $T^{2}$ and
$T^{4}$ is a manifestly non-perturbative result, derived by accounting for the
response of a large family of coupled long-lived modes. Transport measurements
in graphene and GaAs systems in the geometry pictured in Fig.1 report on
conductance that grows as $T$, exceeding ballistic values seen at $T=0$[48,
49]. Observation of superballistic conductance provides a clear signature of
hydrodynamic flow in which ee collisions facilitate conduction. Strikingly, a
linear $T$ dependence of conductance is observed which extends to lowest
temperatures. The $T$-linear conductance provides a testable signature of the
nonclassical super-FL hydrodynamics predicted here.

Figure 2: Decay rates for even and odd excitations, $\gamma_{m}$, vs. harmonic
order $m$ at different temperatures[38, 41]. Even-$m$ and odd-$m$ rates are
shown by orange and blue dots, respectively, for three different temperatures
$T=0.1T_{F}$ $T^{\prime}=0.01T_{F}$, $T^{\prime\prime}=0.003T_{F}$ with the
lighter colors corresponding to higher temperatures. Odd-$m$ rates scale as
$T^{4}m^{4}$ for small $T$ and not-too-large $m$. For large $m$ all rates
scale as $T^{2}$ independent of the $m$ parity. For interpolation, we used the
dependence $\gamma_{m\,{\rm odd}}=T^{4}m^{4}/(1+m^{4}T^{2})$, with $T$
representing $T/T_{F}$. Highlighted in pink are modes with $\gamma_{m\,{\rm
odd}}\lesssim\nu k^{2}$, which propagate as weakly damped viscous modes. The
number of these modes grows rapidly as $T$ decreases, resulting in a quasi-
continuum of soft modes and anomalous $T$ dependence of conductance.

The $T$-linear scaling starkly contrasts with the $T^{2}$ scaling expected for
Fermi-liquid hydrodynamics governed by a single viscous mode[14]. In this
case, nonlocal conductivity, readily obtained from Stokes equation, is

$\sigma(k)\sim\frac{n}{\nu k^{2}},$ (2)

where $\nu=v_{F}^{2}/4\gamma_{2}$ is electrons’ kinematic viscosity. For a
Fermi liquid, $\nu$ scales as $1/T^{2}$, predicting a $T^{2}$ temperature
dependence for $\sigma(k)$ and for the conductance of an aperture shown in
Fig.1 [34].

The quantities that are central to our analysis, yielding a general closed-
form solution for hydrodynamic conduction, are the eigenvalues $\gamma_{m}$ of
the linearized collision operator of 2D electrons. The values $\gamma_{m}$
give relaxation rates for different angular harmonics of the perturbed Fermi
surface,[44, 38, 41, 40]

$\delta f(\theta)\sim a_{m}\cos m\theta+b_{m}\sin m\theta,$ (3)

where $\theta$ is the angle on the Fermi surface. Odd-$m$ rates $\gamma_{m}$
are much smaller than even-$m$ rates and scale as $m^{4}$[44, 38], forming a
wide hierarchy of time scales

$\gamma_{m\,{\rm even}}=\gamma,\quad\gamma_{m\,{\rm
odd}}=\gamma^{\prime}m^{4},\quad m\ll m_{\star}.$ (4)

In the regime of interest $T\ll\epsilon_{F}$, the rates depend on $T$ as
$\gamma\sim T^{2}/\epsilon_{F}$, $\gamma^{\prime}\sim T^{4}/\epsilon_{F}^{3}$,
such that $\gamma^{\prime}\ll\gamma$ [41, 40]. Odd-$m$ rates $\gamma_{m}$
initially grow as $m^{4}$, saturating at the value $\gamma$ at a large
$m\gtrsim m_{\star}=(\gamma/\gamma^{\prime})^{1/4}$. This hierarchy of
even-$m$ and odd-$m$ rates, pictured in Fig.2, demonstrates that the family of
long-lived modes, marked by pink in Fig.2, quickly grows as temperature
decreases. Because of their very low super-FL decays rates, these modes
strongly contribute to hydrodynamics.

We now proceed to analyze the nonlocal current-field response due to carrier
movement governed by hydrodynamic modes, described by nonlocal conductivity as

$j_{\alpha}({\boldsymbol{x}})=\int
d^{2}x^{\prime}\sigma_{\alpha\beta}({\boldsymbol{x}}-{\boldsymbol{x}}^{\prime})E_{\beta}({\boldsymbol{x}}^{\prime}).$
(5)

The quantity of interest is the $k$-dependent conductivity
$\sigma_{\alpha\beta}(k)=\int
d^{2}xe^{-i{\boldsymbol{k}}({\boldsymbol{x}}-{\boldsymbol{x}}^{\prime})}\sigma_{\alpha\beta}({\boldsymbol{x}}-{\boldsymbol{x}}^{\prime})$.
This quantity plays the same role in the theory of hydrodynamic response as
Pippard’s nonlocal $j$ vs. $A$ relation in the theory of superconductivity
[46] or the nonlocal current-field relation in the theory of the anomalous
skin effect [47]. However, unlike these two effects, which describe the
distribution of supercurrents and normal currents in a narrow surface layer,
here the relation in Eq.(5) will be employed to describe current profile in
the system bulk.

Figure 3: Hydrodynamic conductance $k$ and $T$ dependence. Main panel: the
quantity $\Gamma(k)$, Eq.(6), proportional to scale-dependent conductance
$\sigma(k)$ times $k^{2}$, taken at three distinct temperatures $T_{0}$,
$2T_{0}$, $4T_{0}$ (green, purple and red curves). The $\Gamma(k)$ vs. $k$
dependence features two distinct regimes: Fermi-liquid (FL) hydrodynamics and
super FL hydrodynamics, in which $\Gamma(k)$ is $k$-independent and scales as
$k^{1/3}$, respectively. For comparison, $\Gamma(k)$ for conventional Gurzhi
FL hydrodynamics is shown by dashed lines for matching parameter values (see
discussion in text). Inset: $T$ dependence in these regimes obtained for three
$k$ values marked on the $x$ axis and taken in the FL, super FL and an
intermediate regime (cyan, blue and light blue curves). Temperature scaling,
$T$ for super FL and $T^{2}$ for FL regimes, is validated by best fits to a
linear and quadratic $T$ dependence (dashed lines, inset).

The kernel in Eq.(5) can be obtained microscopically in a closed form[36, 45].
Fermion kinetics that accounts for perturbed Fermi surface dynamics links
transverse conductivity
$\sigma_{\alpha\beta}(k)=\sigma(k)(\delta_{\alpha\beta}-\hat{{\boldsymbol{k}}}_{\alpha}\hat{{\boldsymbol{k}}}_{\beta})$
to a quantity $\Gamma(k)$ defined as a continued fraction comprised of
$\gamma_{m}$ rates,

$\sigma(k)=\frac{D}{\gamma_{p}+\frac{z}{\Gamma(k)}},\quad\Gamma(k)=\gamma_{2}+\frac{z}{\gamma_{3}+\frac{z}{\gamma_{4}+\frac{z}{\gamma_{5}+...}}}.$
(6)

Here $D=ne^{2}/m$ is the Drude weight and $z=v_{F}^{2}k^{2}/4$ (we expressed
carrier density through Fermi momentum, $n=gp_{F}^{2}/4\pi\hbar^{2}$, where
$g$ is the spin/valley degeneracy). The quantity $\Gamma(k)$, which will take
a center stage in our discussion, will be referred to as “hydrodynamic
conductance.” Indeed, in the ideal fluid phase, i.e. in the absence of
momentum relaxing scattering, $\gamma_{p}=0$, the conductivity $\sigma(k)$
equals $(D/z)\Gamma(k)$.

To gain insight into the properties of $\Gamma(k)$, which are very sensitive
to even/odd parity asymmetry and $m$ dependence in $\gamma_{m}$, we present
numerical results for $\Gamma(k)$ obtained from the rates given in Eq.(4).
Fig.2 shows $\Gamma(k)$ vs. $k$ dependence that exhibits two distinct regimes.
In the regime labeled “Fermi-liquid (FL) hydrodynamics,” $\Gamma(k)$ is
$k$-independent. This gives conductivity $\sigma(k)\sim 1/k^{2}$ that agrees
with Stokes hydrodynamics. In the regime labeled “super-FL hydrodynamics,”
$\Gamma(k)$ obeys power-law scaling $k^{1/3}$. Temperature dependence of this
quantity, shown in the inset, is $T^{2}$ in the first regime, as expected for
conventional FL hydrodynamics, and is linear in $T$ in the super-FL regime.
This matches the $T$ and $k$ dependence in Eqs.(1),(2).

The range of $k$’s in which super-FL regime occurs can be quantified as
follows. At large lengthscales it is limited by the distances by which the
longest-lived odd-$m$ excitation, which is the $m=3$ harmonic, travels over
its lifetime. This gives a condition $\gamma_{3}=\nu k_{<}^{2}$. At short
lengthscales it is limited by distances estimated above as $\xi_{*}=l_{\rm
ee}\theta_{T}$ (see Fig,1 and accompanying discussion). This gives the domain
of existence of the super FL regime

$\kappa_{<}<k<\kappa_{>},\quad\kappa_{<}=\sqrt{\gamma_{3}\gamma_{2}}/v,\quad\kappa_{>}=\gamma_{2}T_{F}/vT.$
(7)

Outside this range the conventional FL hydrodynamics and ballistic regimes
occur (at small and large $k$, respectively). Since $\gamma_{2}$ and
$\gamma_{3}$ scale with temperature as $T^{2}$ and $T^{4}$, at low
temperatures $\kappa_{<}$ scales as $T^{3}$, whereas $\kappa_{>}$ scales as
$T$. This predicts widening of the super FL regime at low $T$ which is a
behavior evident in Fig.3.

As a comparison, $\Gamma(k)$ for conventional Gurzhi FL hydrodynamics is shown
in Fig.2 main panel for matching parameter values by dashed lines. The $T$
dependence is absent in the ballistic regime and is $T^{2}$ in the FL regime.
The $k$-linear behavior at large $k$, indicative of a ballistic transport, is
pushed to high $k$ in the super FL regime. Simultaneously, a $T$-linear
dependence emerges characteristic of the super FL regime.

Next, we describe an analytic approach that allows to evaluate $\Gamma(k)$ and
derive the super FL scaling given in Eq.(1). It is instructive to first
discuss an artificial case when all $\gamma_{m}$ take identical values
$\gamma_{m}=\gamma$ ($m>1$) with no even/odd asymmetry. In this case
evaluating the continued fraction yields $\sigma(k)$ of the form in Eq.(6)
with $\Gamma(k)=(\gamma+\sqrt{\gamma^{2}+4z^{2}})/2$. In the long-wavelength
limit $kv_{F}\ll\gamma$, the term $4z^{2}$ under the square root can be
ignored, giving a result identical to that found from Stokes hydrodynamics,
$\sigma(k)=D/\left(\gamma_{p}+z/\gamma\right)$. This quantity features $T^{2}$
scaling at $\gamma_{p}=0$, Eq.(2).

A very different behavior arises for a more realistic case of the rates with
an even/odd asymmetry. As we will see, this problem is considerably more
challenging, in particular because odd-$m$ rates in Eq.(4) depend on $m$, with
large differences between successive even and odd $m$. To capture this
behavior in a simplified model, we set $\gamma_{m}=\gamma_{\rm e}$ for all
even $m$ and $\gamma_{\rm o}$ for all odd $m$, ignoring the $m$ dependence of
$\gamma_{\rm e}$ and $\gamma_{\rm o}$. In this case, $\Gamma(k)$ can be
evaluated exactly: $\Gamma(k)=\frac{1}{2}\sqrt{\frac{\gamma_{\rm
e}}{\gamma_{\rm o}}}(\sqrt{\gamma_{\rm o}\gamma_{\rm e}}+\sqrt{\gamma_{\rm
o}\gamma_{\rm e}+k^{2}v_{F}^{2}})$. This motivates introducing “level-$m$”
partial continued fractions, defined as

$\Gamma_{m}(k)=\gamma_{m}+\frac{z}{\gamma_{m+1}+\frac{z}{\gamma_{m+2}+\cdots}}.$
(8)

These quantities, evaluated similarly, are
$\Gamma_{m}(k)=b_{m}(\sqrt{\gamma_{\rm o}\gamma_{\rm e}}+\sqrt{\gamma_{\rm
o}\gamma_{\rm e}+k^{2}v_{F}^{2}})/2$, with $b_{m}$ values $\sqrt{\gamma_{\rm
e}/\gamma_{\rm o}}$ for even $m$ and $\sqrt{\gamma_{\rm o}/\gamma_{\rm e}}$
for odd $m$. When the even/odd parity separation of $\gamma_{m}$ is
significant, $\gamma_{\rm e}\gg\gamma_{\rm o}$, the quantities $\Gamma_{m}$
are much larger for even $m$ than for odd $m$.

Below, to obtain the behavior at low $T$, we apply this picture to the quasi-
continuum of weakly decaying modes highlighted in pink in Fig.2. We assume
that, despite the even/odd beating effect, $\Gamma_{m}$ is slowly varying with
$m$ for each individual parity of $m$. It is then natural to analyze the
dependence $\Gamma_{m}$ vs. $m$ for a fixed parity. The result for $\Gamma(k)$
will then be found by taking $m=2$.

This analysis, described in detail below, predicts a fractional-power scaling
relation for $\Gamma(k)$:

$\Gamma(k)=A\frac{\gamma}{(\gamma\gamma^{\prime})^{\frac{1}{6}}}\left(\frac{kv_{F}}{2}\right)^{\frac{1}{3}}$
(9)

where $A$ is a numerical prefactor given in Eq.(21). Here $\gamma$ and
$\gamma^{\prime}$ are the even-$m$ and odd-$m$ rates defined in Eq.(4). From
the scaling of these rates with temperature, $\gamma\sim T^{2}$,
$\gamma^{\prime}\sim T^{4}$, the resulting $T$ dependence of $\Gamma(k)$ is
linear,

$\Gamma(k)\sim Tk^{1/3}.$ (10)

Eq.(6) then yields $\sigma(k)=D/\left(\gamma_{p}+A^{\prime}k^{5/3}/T\right)$
with $A^{\prime}$ a $T$-independent factor. The dependence on the wavenumber
$k$ translates into a dependence on system geometry. In the presence of
momentum relaxing scattering due to phonons, in which case $\gamma_{p}\sim T$,
the expected $T$ dependence becomes nonmonotonic, growing at low $T$, where ee
scattering dominates, and decreasing at elevated $T$.

To derive the scaling relation given in Eq.(9), we perform the recursion
analysis of partial continued fractions, Eq.(8), focusing on the even-$m$
quantities $\Gamma_{m}$. Taking a difference of $\Gamma_{m}$ and
$\Gamma_{m+2}$, and using Eq.(8) yields

$\Gamma_{m}-\Gamma_{m+2}=\gamma_{m}-\frac{\gamma_{m+1}\Gamma_{m+2}^{2}}{\gamma_{m+1}\Gamma_{m+2}+z}$
(11)

It turns out, perhaps surprisingly, that this nonlinear relation is greatly
simplified and is transformed to a linear relation after the substitution

$\displaystyle\Gamma_{m}=\frac{z}{\gamma_{m-1}}\left(\frac{u_{m}}{u_{m+2}}-1\right).$
(12)

After this substitution Eq.(11) yields a linear relation resembling a
discretized second-order ODE:

$\displaystyle\frac{1}{2}\left(\frac{z}{\gamma_{m-1}}+\frac{z}{\gamma_{m+1}}\right)(u_{m+4}-2u_{m+2}+u_{m})$
(13)
$\displaystyle-\frac{1}{2}\left(\frac{z}{\gamma_{m-1}}-\frac{z}{\gamma_{m+1}}\right)(u_{m+4}-u_{m})=\gamma_{m}u_{m+2}.$

We emphasize that these relations are totally general. Indeed, our starting
point is a tridiagonal system of equations for the amplitudes of different
harmonics[45]. In this case there is a natural bipartite structure (the off-
diagonal couplings are between harmonics of different parity). Eliminating
variables of one parity yields a tridiagonal problem describing the other
parity. Hereafter we take $m$ values to be even.

Since $\Gamma_{m}$ and $\gamma_{m}$, when restricted to a fixed parity, are
slowly varying with $m$, we take Eq.(13) to continuous domain by replacing the
differences with derivatives

$\displaystyle 4\frac{z}{\gamma_{\rm
o}}\frac{d^{2}u}{dm^{2}}-4z\frac{d\gamma_{\rm
o}^{-1}}{dm}\frac{du}{dm}=\gamma_{\rm e}u.$

where $\gamma_{\rm e}(m)=\gamma_{m}$ and $\gamma_{\rm o}(m)=\gamma_{m+1}$.
This simplifies to

$\displaystyle u^{\prime\prime}-\frac{\gamma_{\rm o}^{\prime}}{\gamma_{\rm
o}}u^{\prime}-\frac{\gamma_{\rm o}\gamma_{\rm e}}{4z}u=0.$ (14)

In the continuous domain, Eq.(12) now reads

$\displaystyle\Gamma(m)=-\frac{2z}{\gamma_{\rm o}u}\frac{du}{dm}.$ (15)

We assume that $\gamma_{\rm o}$ and $\gamma_{\rm e}$ both converge to a
constant value $\gamma$ for high harmonics, $m\gtrsim m_{\star}$, then the
values $\Gamma_{m}$ for $m\gtrsim m_{\star}$ are given by the solution of the
one-rate model $(\gamma+\sqrt{\gamma^{2}+k^{2}v_{F}^{2}})/2$. Therefore, we
can write the boundary condition for Eq.(14) as

$\left.-\frac{2z}{\gamma
u}\frac{du}{dm}\right|_{m=m_{\star}}=\Gamma(m_{\star})=\frac{\gamma+\sqrt{\gamma^{2}+k^{2}v_{F}^{2}}}{2},$
(16)

and proceed to solve Eq.(14) on the interval $0<m<m_{\star}$ to obtain the
value of $\Gamma_{m=2}$.

From now on we focus on the $m^{4}$ model, Eq.(4), wherein $\gamma_{\rm
o}=\gamma^{\prime}m^{4}$, $\gamma_{\rm e}=\gamma$. Then Eq.(14) becomes

$\displaystyle
u^{\prime\prime}-\frac{4}{m}u^{\prime}-\frac{\sqrt{\gamma\gamma^{\prime}}}{4z}m^{4}u=0$
(17)

After introducing a new variable
$g=\frac{\sqrt{\gamma\gamma^{\prime}}}{6\sqrt{z}}m^{3}$ and replacing $u$ with
$w=u/g^{5/6}$, Eq.(17) is transformed to the Bessel equation for $w(g)$, with
a general solution

$u=g^{5/6}[C_{1}I_{5/6}(g)+C_{2}I_{-5/6}(g)],$ (18)

where $I_{\alpha}(g)$ is the $\alpha$th-order modified Bessel function of the
first kind.

From Eq.(15), we know that constant prefactor of $u$ does not affect
$\Gamma(m)$ values. Thus the only quantity that remains to be determined is
the ratio $C_{2}/C_{1}$. When $m$ varies from $0$ to
$m_{\star}=(\gamma/\gamma^{\prime})^{1/4}$, $g$ varies from $0$ to
$g_{\star}=\gamma^{5/4}/(6\gamma^{\prime 1/4}\sqrt{z})$, and the boundary
condition for $u(g)$ at the right end of the interval is given by Eq.(16),
that is

$-\frac{m_{\star}\gamma}{6g_{\star}u}\left.\frac{du}{dg}\right|_{g=g_{\star}}=\Gamma(m_{\star})>0$
(19)

When $k\ll\frac{\gamma^{5/4}}{3v_{F}\gamma^{\prime 1/4}}\equiv\kappa_{>}$,
Eq.(19) requires $\Gamma>0$ for $g_{\star}\gg 1$. However, the large-argument
asymptotic expansions for $I_{\alpha}(g)$ are exponentially growing in exactly
the same way for $\alpha$ and $-\alpha$. This results in a monotonically
increasing $u$, producing unphysical values $\Gamma(m_{\star})<0$. The only
way to resolve this conflict is to pick $C_{2}\simeq-C_{1}$, then all terms in
the asymptotic expansion cancel out.

We therefore arrive at Eq.(18) with $C_{1}=-C_{2}$. The quantity of interest,
$\Gamma(k)$, corresponds to
$g|_{m=2}=\frac{4}{3}\frac{\sqrt{\gamma\gamma^{\prime}}}{\sqrt{z}}$. Since for
$k\gg\xi_{\rm h}^{-1}\sim\frac{\sqrt{\gamma\gamma^{\prime}}}{v_{F}}$, the
latter quantity is small, $g|_{m=2}\ll 1$, and we can expand $u$ in $g\ll
1$[50]:

$u=-\frac{2^{\frac{5}{6}}}{\Gamma(\frac{1}{6})}+\frac{2^{\frac{5}{6}}}{\Gamma(\frac{11}{6})}\left(\frac{g}{2}\right)^{5/3}-\frac{1}{2^{\frac{1}{6}}\Gamma(\frac{7}{6})}\left(\frac{g}{2}\right)^{2}+\cdots.$
(20)

Plugging it in Eq.(15) gives the dependence

$\Gamma(k)=\frac{\Gamma(\frac{1}{6})}{3^{\frac{2}{3}}2^{\frac{4}{3}}\Gamma(\frac{5}{6})}\frac{\gamma}{(\gamma\gamma^{\prime})^{\frac{1}{6}}}z^{\frac{1}{6}},$
(21)

valid up to a $T$-independent correction describing ballistic conductivity at
$T=0$. This result is valid in the domain of $k$ identified in Eq.(7) above.
The $T$ dependence of the even and odd rates, $\gamma\sim T^{2}$ and
$\gamma^{\prime}\sim T^{4}$, yields a $T$-linear dependence, supporting the
numerical results presented above.

In summary, conductivity growing with temperature is a hallmark of the
hydrodynamic regime in which ee collisions facilitate conduction and suppress
dissipation. In contrast to the conventional FL hydrodynamics, which predicts
conductivity growing as $T^{2}$ at $T\ll T_{F}$, the super-FL conductance
grows more rapidly, increasing linearly with temperature. The enhanced
conductance reflects presence of multiple long-lived modes unique to 2D
fermions. Conductance exceeding the ballistic $T=0$ value and growing linearly
with $T$ has been observed for superballistic transport in graphene and GaAs
electron fluids[48, 49]. This indicates that ongoing experimental efforts to
achieve electron hydrodynamics [51, 52, 53, 54, 55] can access the exotic
hydrodynamics driven by emergent long-lived modes. Further, we expect similar
anomalous $T$-dependent hydrodynamic effects in strongly-correlated systems
that host soft quantum-critical modes or emergent gauge fields [1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11] activated at low temperatures.

We are grateful to Klaus Ensslin, Andre Geim, Lev Ginzburg and Boris Spivak
for useful discussions. This work was supported by the Science and Technology
Center for Integrated Quantum Materials, National Science Foundation grant No.
DMR1231319 and was performed in part at Aspen Center for Physics, which is
supported by NSF grant PHY-2210452. SK is currently affiliated with Harvard
University, Physics Department.

## References

  * [1] S. Sachdev, B. Keimer, Quantum Criticality, Physics Today 64, 2, 29 (2011)
  * [2] P. W. Phillips, N. E. Hussey, P. Abbamonte, Stranger than metals, Science 377, 169 (2022)
  * [3] C. M. Varma, Colloquium: Linear in temperature resistivity and associated mysteries including high temperature superconductivity. Rev. Mod. Phys. 92, 031001 (2020).
  * [4] C. M. Varma, P. B. Littlewood, S. Schmitt-Rink, E. Abrahams, A. E. Ruckenstein, Phenomenology of the normal state of Cu-O high-temperature superconductors. Phys. Rev. Lett. 63, 1996 (1989).
  * [5] C. Proust, L. Taillefer, The remarkable underlying ground states of cuprate superconductors. Annu. Rev. Condens. Matter Phys. 10, 409-429 (2019).
  * [6] S. A. Hartnoll, A. P. Mackenzie, Colloquium: Planckian dissipation in metals. Rev. Mod. Phys. 94, 041002 (2022).
  * [7] J. Zaanen, Planckian dissipation, minimal viscosity and the transport in cuprate strange metals. SciPost Phys. 6, 061 (2019).
  * [8] S. A. Hartnoll, Theory of universal incoherent metallic transport. Nat. Phys. 11, 54-61 (2015).
  * [9] H. Guo, A. A. Patel, I. Esterlis, and S. Sachdev, Large-N theory of critical Fermi surfaces. II. Conductivity, Phys. Rev. B 106, 115151 (2022).
  * [10] P. A. Lee, Gauge Field, Aharonov-Bohm Flux, and High-Tc Superconductivity, Phys. Rev. Lett. 63, 680 (1989).
  * [11] Y. B. Kim, A. Furusaki, X.-G. Wen, and P. A. Lee, Gauge-invariant response functions of fermions coupled to a gauge field, Phys. Rev. B 50, 17917 (1994).
  * [12] X. Lin, B. Fauque and K. Behnia, Science 349, 945-948 (2015).
  * [13] H. K. Pal, V. I. Yudson and D. L. Maslov, Resistivity of non-Galilean-invariant Fermi- and non-Fermi liquids, Lith. J. Phys. 52, 142-164 (2012).
  * [14] R. N. Gurzhi, Sov. Phys. Usp. 11, 255 (1968). DOI 10.1070/PU1968v011n02ABEH003815
  * [15] M. Müller, J. Schmalian, L. Fritz, Graphene: a nearly perfect fluid. Phys. Rev. Lett. 103, 2–5 (2009).
  * [16] A. Tomadin, G. Vignale, M. Polini, A Corbino disk viscometer for 2D quantum electron liquids Phys. Rev. Lett. 113, 235901 (2014).
  * [17] A. Principi, G. Vignale, M. Carrega, M. Polini, Bulk and shear viscosities of the two-dimensional electron liquid in a doped graphene sheet Phys. Rev. B 93, 125410 (2016)
  * [18] T. Scaffidi, N. Nandi, B. Schmidt, A. P. Mackenzie, J. E. Moore, Hydrodynamic electron flow and Hall viscosity. Phys. Rev. Lett. 118, 226601 (2017).
  * [19] A. Lucas, K. C. Fong, Hydrodynamics of electrons in graphene, J. Phys.: Condens. Matter 30 053001 (2018).
  * [20] K. A. Guerrero-Becerra, F. M. D. Pellegrino, M. Polini, Magnetic hallmarks of viscous electron flow in graphene. Phys. Rev. B 99, 041407 (2019).
  * [21] B. N. Narozhny, M. Schütt, Magnetohydrodynamics in graphene: Shear and Hall viscosities. Phys. Rev. B 100, 035125 (2019).
  * [22] G. Wagner, D. X. Nguyen and S. H. Simon, Transport in Bilayer Graphene near Charge Neutrality: Which Scattering Mechanisms Are Important? Phys. Rev. Lett. 124, 026601 (2020).
  * [23] S. Li, A. Levchenko and A. V. Andreev, Hydrodynamic electron transport near charge neutrality, Phys. Rev. B 102, 075305 (2020)
  * [24] A. Levchenko and J. Schmalian, Transport properties of strongly coupled electron–phonon liquids, Annals of Physics 419, 168218 (2020).
  * [25] A. G. Abanov, T. Can, S. Ganeshan, G. M. Monteiro, Hydrodynamics of two-dimensional compressible fluid with broken parity: variational principle and free surface dynamics in the absence of dissipation, Phys. Rev. Fluids 5, 104802 (2020)
  * [26] P. S. Alekseev, A. P. Dmitriev, Viscosity of two-dimensional electrons. Phys. Rev. B 102, 241409 (2020).
  * [27] R. Toshio, K. Takasan, N. Kawakami, Anomalous hydrodynamic transport in interacting noncentrosymmetric metals. Phys. Rev. Res. 2, 032021 (2020).
  * [28] B. N. Narozhny, I. V. Gornyi, M. Titov, Hydrodynamic collective modes in graphene. Phys. Rev. B 103, 115402 (2021).
  * [29] E. H. Hasdeo, J. Ekstrom, E. G. Idrisov, T. L. Schmidt, Electron hydrodynamics of two-dimensional anomalous Hall materials. Phys. Rev. B 103, 125106 (2021).
  * [30] M. Qi, A. Lucas, Distinguishing viscous, ballistic, and diffusive current flows in anisotropic metals, Phys. Rev. B 104 (19), 195106 (2021)
  * [31] C. Q. Cook, A. Lucas, Viscometry of electron fluids from symmetry, Phys. Rev. Lett. 127 (17), 176603 (2021)
  * [32] D. Valentinis, J. Zaanen, D. van der Marel Propagation of shear stress in strongly interacting metallic Fermi liquids enhances transmission of terahertz radiation Sci. Rep. 11, 7105 (2021)
  * [33] D. Valentinis, Optical signatures of shear collective modes in strongly interacting Fermi liquids Phys. Rev. Research 3, 023076 (2021)
  * [34] H. Guo, E. Ilseven, G. Falkovich, and L. Levitov, Higher-than-ballistic conduction of viscous electron flows, Proc. Natl. Acad. Sci. U.S.A. 114, 3068 (2017).
  * [35] A. V. Shytov, J. F. Kong, G. Falkovich, and L. S. Levitov, Particle Collisions and Negative Nonlocal Response of Ballistic Electrons, Phys. Rev. Lett. 121, 176805 (2018).
  * [36] K. G. Nazaryan, L. S. Levitov, Nonlocal conductivity, continued fractions and current vortices in electron fluids, arXiv:2111.09878.
  * [37] E. I. Kiselev, J. Schmalian, Lévy flights and hydrodynamic superdiffusion on the Dirac cone of Graphene, Phys. Rev. Lett. 123, 195302 (2019).
  * [38] P. Ledwith, H. Guo, A. Shytov, L. Levitov Tomographic Dynamics and Scale-Dependent Viscosity in 2D Electron Systems, Phys. Rev. Lett. 123, 116601 (2019).
  * [39] X. Huang and A. Lucas, Fingerprints of quantum criticality in locally resolved transport, SciPost Phys. 13 004 (2022).
  * [40] J. Hofmann and S. Das Sarma, Collective modes in interacting two-dimensional tomographic Fermi liquids, Phys. Rev. B 106, 205412 (2022).
  * [41] S. Kryhin, L. Levitov, Collinear scattering and long-lived excitations in two-dimensional electron fluids, Phys. Rev. B 107, L201404 (2023); arXiv preprint arXiv:2112.05076 (2021).
  * [42] J. Hofmann, U. Gran, Anomalously long lifetimes in two-dimensional Fermi liquids, arXiv preprint arXiv:2210.16300 (2022)
  * [43] P. J. Ledwith, H. Guo, L. Levitov, Angular Superdiffusion and Directional Memory in Two-Dimensional Electron Fluids, arXiv:1708.01915
  * [44] P. J. Ledwith, H. Guo, L. Levitov, The Hierarchy of Excitation Lifetimes in Two-Dimensional Fermi Gases, Ann. Phys. 411, 167913 (2019).
  * [45] S. Kryhin, L. Levitov, Non-Newtonian hydrodynamic modes in two-dimensional electron fluids, preprint arXiv:2305.02883
  * [46] M. Tinkham, Introduction to Superconductivity (Dover Books on Physics, 1996).
  * [47] L. P. Pitaevskii; E. M. Lifshitz, Physical Kinetics, (Butterworth-Heinemann, 1981)
  * [48] R. Krishna Kumar, D. A. Bandurin, F. M. D. Pellegrino, Y. Cao, A. Principi, H. Guo, G. H. Auton, M. BenShalom, L. A. Ponomarenko, G. Falkovich, K. Watanabe, T. Taniguchi, I. V. Grigorieva, L. S. Levitov, M. Polini, and A. K. Geim, Superballistic flow of viscous electron fluid through graphene constrictions, Nature Physics 13, 1182 (2017).
  * [49] L. V. Ginzburg, Y. Wu, M. P. Roosli, P. R. Gomez, R. Garreis, C. Tong, V. Stará, C. Gold, K. Nazaryan, S. Kryhin, H. Overweg, C. Reichl, M. Berl, T. Taniguchi, K. Watanabe, W. Wegscheider, T. Ihn, K. Ensslin, Long distance electron-electron scattering detected with point contacts, arXiv:2308.06056
  * [50] The Gamma functions in Eqs.(20) and (21) are not to be confused with the notation $\Gamma_{m}(k)$ for continued fractions.
  * [51] J. A. Sulpizio, L. Ella, A. Rozen, J. Birkbeck, D. J. Perello, D. Dutta, M. Ben-Shalom, T. Taniguchi, K. Watanabe, T. Holder, R. Queiroz, A. Principi, A. Stern, T. Scaffidi, A. K. Geim, S. Ilani, Visualizing Poiseuille flow of hydrodynamic electrons, Nature 576, 75-79 (2019).
  * [52] M. J. H. Ku, T. X. Zhou, Q. Li, Y. J. Shin, J. K. Shi, C. Burch, L. E. Anderson, A. T. Pierce, Y. Xie, A. Hamo, U. Vool, H. Zhang, F. Casola, T. Taniguchi, K. Watanabe, M. M. Fogler, P. Kim, A. Yacoby, R. L. Walsworth, Imaging viscous flow of the Dirac fluid in graphene, Nature 583, 537-541 (2020).
  * [53] B. A. Braem, F. M. D. Pellegrino, A. Principi, M. Roosli, C. Gold, S. Hennel, J. V. Koski, M. Berl, W. Dietsche, W. Wegscheider, M. Polini, T. Ihn, and K. Ensslin, Scanning gate microscopy in a viscous electron fluid, Phys. Rev. B 98, 241304(R) (2018).
  * [54] U. Vool, A. Hamo, G. Varnavides, Y. Wang, T. X. Zhou, N. Kumar, Y. Dovzhenko, Z. Qiu, C. A. C. Garcia, A. T. Pierce, J. Gooth, P. Anikeeva, C. Felser, P. Narang, A. Yacoby, Imaging phonon-mediated hydrodynamic flow in WTe2, Nature Physics 17, 1216-1220 (2021).
  * [55] A. Aharon-Steinberg, T. Volkl, A. Kaplan, A. K. Pariari, I. Roy, T. Holder, Y. Wolf, A. Y. Meltzer, Y. Myasoedov, M. E. Huber, B. Yan, G. Falkovich, L. S. Levitov, M. Hucker, E. Zeldov, Direct observation of vortices in an electron fluid, Nature 607, 74-80 (2022).