# A Cryptographic Hash Function from Markoff Triples

Elena Fuchs  Department of Mathematics, University of California, Davis
Kristin Lauter  Facebook AI Research, Seattle, WA Matthew Litman  Department
of Mathematics, University of California, Davis Austin Tran  Department of
Mathematics, University of California, Davis

###### Abstract

Cryptographic hash functions from expander graphs were proposed by Charles,
Goren, and Lauter in [CGL] based on the hardness of finding paths in the
graph. In this paper, we propose a new candidate for a hash function based on
the hardness of finding paths in the graph of Markoff triples modulo $p$.
These graphs have been studied extensively in number theory and various other
fields, and yet finding paths in the graphs remains difficult. We discuss the
hardness of finding paths between points, based on the structure of the
Markoff graphs. We investigate several possible avenues for attack and
estimate their running time to be greater than $O(p)$. In particular, we
analyze a recent groundbreaking proof in [BGS1] that such graphs are connected
and discuss how this proof gives an algorithm for finding paths.

Keywords: Markoff triples, Cryptographic hash functions
MSC: 11T71, 94A60, 05C48

###### Contents

  1. 1 Introduction
    1. 1.1 Markoff tree and graph
    2. 1.2 Cryptographic hash function
    3. 1.3 Avenues for attack
    4. 1.4 Some background on Markoff triples
  2. 2 Markoff triple hash function and data
    1. 2.1 Cryptographic Heuristics
    2. 2.2 Sampling
  3. 3 Attack by Pathfinding via the Method of Bourgain-Gamburd-Sarnak
    1. 3.1 Rotations
    2. 3.2 The End Game
    3. 3.3 The Middle Game and The Opening
  4. 4 Attack by Lifting
  5. 5 Other Possible Attacks and Future Avenues for Research

##  1 Introduction

In this work, we introduce a proposal for a hash function based on the
hardness of finding paths in the graph of Markoff triples, which we will
define. The idea of using the hardness of path-finding in graphs to define
cryptosystems was introduced at the NIST Hash function workshop in 2005 [CGL].
The paper [CGL] proposed two different candidate families of Ramanujan graphs:
1) LPS Cayley graphs, and 2) Supersingular Isogeny Graphs. The LPS-based hash
function was attacked in two subsequent papers, which presented efficient
algorithms to find collisions [TZ], and preimages [PLQ]. Path-finding in
Supersingular Isogeny Graphs remains a hard problem in cryptography so far,
and is the basis for the SIDH Key Exchange Protocol [JFP, CFLMP] in the third
round of the NIST PQC competition.

In this paper, we propose to use graphs based on solutions to Markoff’s
equation to construct a new cryptographic hash function, and discuss why it
appears that these graphs may be good candidates. Our main focus will be to
evaluate the path-finding algorithm that can be extracted from the proof of
Bourgain-Gamburd-Sarnak in [BGS1] that these graphs are connected in most
cases, as this is currently the only certain way to find paths in these graphs
in general. We will hence go into the details of the proof in [BGS1] and how
it yields an algorithm to find paths, as well as explore some other potential
attacks in Section 4 and 5.

###  1.1 Markoff tree and graph

Consider solutions in $(\mathbb{Z}_{\geq 0})^{3}\backslash\\{(0,0,0)\\}$ to

$x_{1}^{2}+x_{2}^{2}+x_{3}^{2}-3x_{1}x_{2}x_{3}=0.$ (1)

Equation (1) is known as the _Markoff equation_ , and its solutions are called
_Markoff triples_ , with the integers that occur as members of some triples
known as Markoff numbers. As we discuss below, a lot is known about Markoff
numbers, and one particularly useful observation, both to us and more
generally in the arithmetic study of Markoff numbers, is that one can generate
all such triples by considering the orbit of the group generated by the
involutions

$R_{1}(x_{1},x_{2},x_{3})=(3x_{2}x_{3}-x_{1},x_{2},x_{3})$
$R_{2}(x_{1},x_{2},x_{3})=(x_{1},3x_{1}x_{3}-x_{2},x_{3})$
$R_{3}(x_{1},x_{2},x_{3})=(x_{1},x_{2},3x_{1}x_{2}-x_{3})$

acting on the triple $(1,1,1)$ [M1],[M2]. In this way, one can view the set of
Markoff triples as a tree as depicted in Figure 1. Note that the tree depicted
in Figure 1 shows one of several very similar branches of the tree, the others
are generated by acting on $(1,1,1)$ via $R_{1}$ and $R_{2}$, as well as
letting one other involution act on the triple immediately adjacent to
$(1,1,1)$ (in the figure, that other involution would be $R_{1}$ acting on
$(1,1,2)$). Those branches will simply contain permutations of the triples
shown in Figure 1.

Figure 1: A branch of the Markoff tree generated by applying the involutions
$R_{1},R_{2},R_{3}$ to the fundamental solution (1,1,1).

Markoff triples first appeared in the literature in Markoff’s master’s thesis
[M1], [M2] in the context of studying rational approximations via continued
fractions. Markoff found that the sequence of Markoff numbers plays a big role
in results that produce infinitely many irrationals $\alpha$ which admit a
continued fraction convergent $p/q$ such that

$\left|\alpha-\frac{p}{q}\right|<\frac{m}{\sqrt{d}q^{2}}$

for appropriate values of $m$ and $d$ which are connected to the Markoff
sequence. Moreover, he was able to determine exactly for which $\alpha$ the
above bound is sharp. Markoff’s work on the subject inspired a whole series of
generalizations of his result which introduced novel techniques into the
theory which are still used today, e.g. [RS]. Indeed, today the Markoff
equation in (1) is of interest not only to those studying continued fractions
but has become an important object in other branches of mathematics such as
algebraic geometry and theoretical physics [Ch],[LT].

For cryptographic applications, we will consider what is, roughly speaking,
the mod-$p$ reduction of this tree, as well as a related graph where edges are
defined slightly differently.

Specifically, let $p$ be a (large) prime, and consider the set of nonzero
solutions modulo $p$ to equation (1). We call a solution $(x_{1},x_{2},x_{3})$
in $(\mathbb{F}_{p})^{3}$ a _triple_ , and each entry in the triple $x_{1}$,
$x_{2}$, or $x_{3}$, a _coordinate_ ; so a coordinate is simply an element of
$\mathbb{F}_{p}$.

We consider two graphs: $G_{p}$ and $\hat{G}_{p}$. In both of these graphs,
the vertices are comprised of nontrivial (we exclude $(0,0,0)$) solutions
modulo $p$. In $G_{p}$, the edges are defined by the involutions
$R_{1},R_{2},R_{3}$: two triples are connected by an edge if one of the three
involutions takes one triple to the other. We will also refer to this graph as
the involution graph. In $\hat{G}_{p}$, the edges are defined by _rotations_
(see Section 3.1). Explicitly, they are given by

$\operatorname{rot}_{i}=\tau_{i+1,i+2}\circ R_{i+1}$ (2)

Here $\tau$ is a transposition of coordinates, and all index additions are
done modulo 3. Two triples are connected by an edge in $\hat{G}_{p}$ if one of
the 3 rotations takes one triple to the other. We refer to this as the
rotation graph.

Our reason for considering $G_{p}$ is that it is particularly convenient for
setting up our hash function. It is the rotation graph $\hat{G}_{p}$, however,
for which Bourgain-Gamburd-Sarnak prove connectivity and in fact give a path-
finding algorithm. Notably, finding paths in the graph $\hat{G}_{p}$ is easily
correlated to finding paths in $G_{p}$, and vice versa.

Specifically, one can check that, given three different indices $1\leq
i,j,k\leq 3$, and a triple $(a,b,c)$, one has
$R_{i}(a,b,c)=\tau_{j,i}R_{j}\tau_{k,j}R_{k}\tau_{i,k}R_{i}(a,b,c)$, so a path
of length $\ell$ between two triples in $G_{p}$ corresponds to a path of
length $3\ell$ in $\hat{G}_{p}$, whereas a path of length $\ell$ between two
triples in $\hat{G}_{p}$ corresponds to a path of at length at least $\ell/3$,
and possibly much longer, in $G_{p}$. In other words, an algorithm to find
paths in $\hat{G}_{p}$ will find paths in the other graph in time not
significantly shorter, and possibly much longer, time.

Figure 2: The Markoff mod-$p$ graphs $\hat{G}_{p}$ for $p=3$, $5$, and $7$.

###  1.2 Cryptographic hash function

First we give a brief summary of the hash function we propose, with more
details given in Section 2. We choose a large prime $p$: typical cryptographic
size primes have at least $256$ bits. There are some restrictions on the
choice of $p$, see the discussion in the following section. We then label in
$G_{p}$ the edges corresponding to the involutions $R_{1}$, $R_{2}$, and
$R_{3}$, respectively. The input to the hash function is a bit string
$b_{0}b_{1}b_{2}\ldots$. To compute the output of the hash function, start at
a fixed vertex, such as the vertex $(1,1,1)$, and take a walk in the graph
according to the directions in the bit string, reading the string bit by bit,
one bit for each step of the walk. The output is the vertex at which this
process ends.

The security of this hash function depends on the hardness of finding paths
between two vertices in the graph $G_{p}$. This paper is concerned primarily
with exploring potential avenues for attack and estimating their running
times.

###  1.3 Avenues for attack

In Sections 3 and 4, we describe two potential attacks on our hash function.
Both give ways of finding paths between two triples in the graph $G_{p}$.

The work of Bourgain, Gamburd, and Sarnak in [BGS1] gives a potential attack
on the cryptosystem we have proposed, but we will show that its running time
is heuristically $O(p)$. Specifically, in order to show that the graphs
$\hat{G}_{p}$ are connected, their algorithm gives a way to construct a path
between any two vertices in the Markoff graph mod $p$ for most primes $p$. The
very rough idea is to associate to every vertex a certain “order” that we
describe in Section 3.1. Those vertices of maximal possible order are grouped
into what Bourgain-Gamburd-Sarnak call _the cage_ , which they prove is
connected. They then show a way to connect any other vertex to the cage by
walking along the graph while increasing the so-called order of the vertex
until the cage is reached. We call this the BGS algorithm for finding paths in
$\hat{G}_{p}$.

Not surprisingly, this is easiest to do when the order of the vertex in
question is already quite large, and they call the process of passing from
such a vertex to the cage the “End Game.” Those points whose order is larger
than a small power of $p$ but not as large as the vertices involved in the End
Game are treated separately in what Bourgain, Gamburd, and Sarnak call the
“Middle Game.” Finally, to move from vertices of very small order into the
Middle Game and beyond, they employ rather technical methods in what they call
the “Opening.” Because it is central to understanding the potential attack
that it gives on our cryptosystem, and because some of the details that are
important to us are left to the reader in [BGS1], we carefully describe these
three parts of Bourgain, Gamburd, and Sarnak’s proof of Theorem 5 and then
give a heuristic for the running time in Section 2.1. We show the following.

######  Proposition 1.

The length of the path given by the BGS algorithm is bounded from above by

$O\left(p\log\log{p}\right).$

See section 2.1 for the derivation. From this, we deduce the time complexity
of the algorithm.

######  Proposition 2.

The time complexity of the BGS algorithm is at most

$O\left(p\log\log{p}\right).$

We also provide data in Section 2.1 showing that these upper bounds are in
fact of the right order, which supports the heuristics. We observe that the
path is longest modulo primes $p$ for which $p^{2}-1$ is _very smooth_ (see
discussion in Section 6). Note that, if a faster way of finding paths between
vertices in $G_{p}$ or $\hat{G}_{p}$ exists, this would be both of interest to
the study of our hash function, and to the study of the arithmetic of Markoff
numbers: it could provide a second proof of Theorem 5 that works even for
those primes that Bourgain, Gamburd, and Sarnak could not handle.

Related to this first attack, we also present a seemingly simple attack which
would use the fact that, as one walks without back-tracking along the Markoff
tree depicted in Figure 1, the coordinates of the triple increase. This makes
it trivial to find paths between vertices in this tree: simply walk from the
two vertices in question along edges that decrease coordinates until one gets
to $(1,1,1)$. If it were easily possible, given a vertex $(x_{1},x_{2},x_{3})$
in $G_{p}$ to lift it to a vertex in the infinite Markoff tree which reduces
to $(x_{1},x_{2},x_{3})$ modulo $p$, then one could simply connect the two
vertices in question by connecting their lifts in the infinite tree, and then
transferring this path back to $G_{p}$. However, in Section 4, where we
describe this attack more carefully, we explain the obstacles to this
approach. In particular, an efficient algorithm to lift would yield another
proof of Theorem 5: an algorithm to lift any triple in $G_{p}$ to one in the
infinite tree (which is known to be connected) in fact shows that $G_{p}$
itself, and, by the previous discussion of how the two graphs are related,
$\hat{G}_{p}$ is connected. We conjecture the following.

######  Conjecture 3.

The length of a path found by lifting a triple in $G_{p}$ to a triple in the
Markoff tree over $\mathbb{Z}$ is at least $\textrm{O}(\log p)$ for most
triples in $G_{p}$.

Note that this does not take into account the difficulty of actually finding
the lift (or this path of length $\log p$). Hence the running time of this
attack is likely comparable to the one based on the BGS algorithm.

###  1.4 Some background on Markoff triples

We now note a few important facts about the graphs $G_{p}$. First of all, it
is known that $|G_{p}|=|\hat{G}_{p}|=p^{2}+\left(\frac{-1}{p}\right)\cdot 3p$
if $p>3$, which is mentioned in [dCM] without proof. Here
$\left(\frac{\ast}{\ast}\right)$ denotes the Legendre symbol. One way to prove
this is to think of the left side of the Markoff equation as a quadratic form
in one of the variables $x_{1},x_{2},x_{3}$, and then consider how many
representations of $0$ there are mod $p$, which is a well known problem.
Furthermore, Meiri and Puder have proven the following.

######  Theorem 4 (Meiri, Puder [MP]).

Let $G_{p}$ be as above and let $\Gamma_{p}$ be the finite permutation group
induced by the action of $\Gamma=\langle R_{1},R_{2},R_{3}\rangle$ on $G_{p}$.
Then, outside a zero-density subset of all primes, the group $\Gamma_{p}$ is
either the full symmetric group or the alternating group on the vertices of
$G_{p}$.

They conjecture that this is in fact true for all primes $p\geq 5$. So we can
compare walking along the graph $G_{p}$ to generating elements of $S_{n}$ and
$A_{n}$ (where $n=|G_{p}|$) with a given random generating set, which has been
studied, for example in [BH].

The graphs $G_{p}$ and $\hat{G}_{p}$ are now known to be connected for the
majority of primes $p$. This was proven by Bourgain, Gamburd, and Sarnak in
[BGS1] as a first step in studying the arithmetic of Markoff triples (for
example, the distribution of primes or numbers with a bounded number of prime
factors among Markoff numbers). The structure of these graphs plays an
important roll in sieving over Markoff triples, which is key in [BGS2].
Specifically, they show the following.

######  Theorem 5 (Bourgain, Gamburd, Sarnak [BGS1]).

For all primes $p\not\in E$, where $E$ is an exceptional set of primes, the
graph $\hat{G}_{p}$ is connected. The set $E$ is small: for any $\epsilon>0$,
the number of primes $p\leq T$ with $p\in E$ is at most $T^{\epsilon}$ for $T$
large.

Furthermore, they conjecture not only that $G_{p}$ is connected for all primes
$p$, but that in fact the family of graphs $G_{p}$ where $p$ is prime is an
expander family. This is explored in [dCM], as we discuss in the following
section. Theorem 5 is enough to show, as Bourgain, Gamburd, and Sarnak show in
[BGS2], that the set of Markoff numbers contains infinitely many composite
numbers, and in fact that almost all Markoff numbers are composite.

##  2 Markoff triple hash function and data

Recall that for a sufficiently large prime $p$, we can construct a hash
function as follows. A fixed public initial vertex is specified, say
$(1,1,1)$. Also choose an involution $k$; the choice of $k$ is fixed but
arbitrary. The edges of $G_{p}$ are canonically labeled with 1, 2, or 3,
corresponding to the three involutions $R_{1},R_{2},R_{3}$ respectively. Given
a bit string of finite length as input, say $b_{0}b_{1}b_{2}\ldots$, designate
$c_{0}=k$. Then, for $i>0$, suppose $c_{i-1}$ was the label of the previous
edge, $c_{i}\in\\{1,2,3\\}$. Then we move along the edge

$c_{i}=(c_{i-1}+b_{i})\ (\mathrm{mod}\ 3)+1$

Note that doing this avoids substrings of the form $R_{i}R_{i}$, and so we
avoid backtracking. The output of the hash function is the final vertex where
the walk ends, after processing all the bits $b_{i}$ in the string. Note that
the initial bit string is not necessarily raw text or data, and will most
likely be augmented with some compression function, such as the Merkle-Damgard
construction.

For example, suppose we want to encode the binary message `10011` in $G_{13}$.
We choose $k=0$ then apply the series of rotations

$10011\mapsto R_{2}\circ R_{3}\circ R_{2}\circ R_{1}\circ
R_{2}(1,1,1)=(0,5,1)$

We know that $|G_{p}|=O(p^{2})$, so for the output space of this hash function
to be comparable to say SHA-256, we would want to take $p\approx 2^{128}$. The
security of this hash function depends upon the difficulty of path or cycle
finding in $G_{p}$. That is, given $x$, $y\in G_{p}$, what is the time
complexity of finding a path between $x$ and $y$?

Note that if the starting vertex is $(1,1,1)$, the input string needs to be
longer than $\log{p}$ so that the coordinates of the output start to wrap
around modulo $p$. Otherwise a trivial lifting attack is possible. A better
starting vertex $v_{0}$ can be obtained by taking a walk of length $\log(p)$
from $(1,1,1)$. In general we will assume that the length of the walk from
$v_{0}$ is at least length $\log(p)$. In fact, [BGS2] has conjectured that the
family $G_{p}$ is an expander family; walks of length $O(\log{p})$ are
sufficient for mixing in expander graphs.

###  2.1 Cryptographic Heuristics

The theorems of Bourgain, Gamburd, and Sarnak, which we present in detail in
Section 3 prove the correctness of the following path finding algorithm in
$\hat{G}_{p}$ (under certain easy assumptions on $p$). This path finding
algorithm uses a notion of “order” of a triple, coming from a certain rotation
assigned to it (see Section 3.1 for the definition). The idea is then that
there is a large connected component of $\hat{G}_{p}$ consisting of triples of
“maximal” order, and to connect any two triples one need only connect each of
them to this large component, which Bourgain-Gamburd-Sarnak call the _cage_.
One does this by walking along a specially concocted path in which the orders
of the triples grow as one walks along it, until one reaches the cage. In
other words, the algorithm runs as follows.

Suppose we want to connect two triples $X$ and $Y$. We can do this in two
steps:

  1. 1.

First, if $X$ or $Y$ are not in the cage, then we want to connect them to the
cage.

Every triple $X$ is part of special cycles in $\hat{G}_{p}$ which we describe
in Section 3, called maximal orbits $M_{X}$ of $X$. Bourgain-Gamburd-Sarnak
show that the orbit $M_{X}$ contains at least one point of higher order than
$X$, call it $X^{\prime}$. Then $X^{\prime}$ is connected to $X$, so replace
$X$ with $X^{\prime}$ and repeat the same argument. The order is guaranteed to
increase each step, until eventually the order is maximal.

  2. 2.

Now we can suppose $X$ and $Y$ are both in the cage. Then by Proposition 10
(Proposition 6 in [BGS1]), there exists a point $Z$ in the cage such that
$X-Z-Y$ is a valid path.

In fact, we have an explicit way of finding $Z$. Since $X$ or $Y$ might have
more than one maximal orbit, we search over all maximal orbits of $X$ and $Y$
and look for an intersection, which is guaranteed to exist. In the case that
$X$ and $Y$ have the same singular maximal index, then we simply perform an
appropriate transposition on either $X$ or $Y$.

As noted in Proposition 1, we have an upper bound of

$O(p\log\log{p})$

on the length of the path obtained using the BGS algorithm.

To see this, suppose we start at a point that is far from the cage and walk
towards it by going around essentially a full orbit of a rotation acting on
that point, then switching to an orbit that is slightly larger, and so on. The
number of steps needed is as follows: we may have to go through all the
divisors $d$ of $p-1$ and $p+1$ as we increase the divisors (these correspond
to the orbit sizes). We only need to do this up to about $\sqrt{p}$, according
to Bourgain-Gamburd-Sarnak, since after that there will be a point in the
orbit that is in the cage. So the total number of steps needed to take in the
BGS algorithm is bounded above by

$\sum_{d|p-1}d+\sum_{d|p+1}d+3p$

where $3p$ bounds the number of steps needed to walk from one point in the
cage to another. We have that

$\sum_{d|p-1}d,\;\sum_{d|p+1}d<<p\log\log p$

and this is expected to be almost always sharp.

Note that if the two points between which wee must find a path are both in the
cage, then path-finding in the cage has complexity $O(p)$.

We can imagine optimizing this algorithm by being greedier with the first
step. Instead of looking at the entire orbit, as soon as we find _any_
$X^{\prime}$ with order higher than $X$, we replace $X$ with that
$X^{\prime}$. The algorithm is also guaranteed to work because the order is
still guaranteed to increase at each step. If we assume this $X^{\prime}$
occurs uniformly randomly within the orbit, instead of looking at $d$ points
in an orbit, we only look at $d/2$ points on average. The complexity of this
modified algorithm is largely unchanged (up to a constant).

This upper bound is supported by the data in Figure 3. Larger $p$ are needed
for more precise comparison, but this is encouraging data that tracks very
closely with $p\log\log p$. Note that the relative scale for time taken is
arbitrary; nevertheless we mention the specifications for reference.
Calculations were done in SageMath 9.1, running on a quad-core i7-8550U CPU.

Figure 3: Plot of $\log{p}$ vs. $\log$ average time taken by the BGS
algorithm. Here we take primes $p\leq 739$. Time taken is in milliseconds,
averaged over 100 trials for each $p$.

Now the complexity depends merely on the chance of a worst-case scenario,
where the triple is not in the cage. This depends on a couple of factors: the
proportional size of the cage, and the number of steps it could potentially
take to connect any triple to the cage.

It turns out that both of these factors depend in turn on $\eta_{p}$, the
number of divisors of $p^{2}-1$. There is a correlation between $\eta_{p}$ and
the number of steps needed to connect a triple (not in the cage), as can be
seen in Figure 4. Additionally, Figure 5 is supporting evidence that the size
of cage also depends on $\eta_{p}$. The asymptotic behavior of this graph, as
$\eta_{p}\to\infty$, is a relevant open question.

Figure 4: Plot of $\log\eta_{p}$ vs. average time taken by the BGS algorithm,
in seconds. Here we take prime $p<10000$ and $\eta_{p}<6000$. Time taken is in
seconds, averaged over 10 trials for each $p$. Figure 5: Plot of
$\log\eta_{p}$ vs. proportion of all vertices in the graph $\hat{G}_{p}$ which
are in the cage for primes $p<100000$ with $\eta_{p}<24000$.

We would also like to see if the time taken to connect a point to the cage
depends on $\eta_{p}$. A plot of this relationship can be seen in Figure 6,
showing a strong correlation between $\eta_{p}$ and the time taken to connect
a point to the cage.

Figure 6: Plot of $\log\eta_{p}$ vs. time taken by the BGS algorithm to
connect a point to the cage, in seconds. Here our primes $p$ are taken such
that $p<2000$ and $\eta_{p}<2000$. Time taken is in seconds, averaged over 10
trials for each $p$.

Concretely, [BGS1] only establishes that $\hat{G}_{p}$ is connected as long as
$p$ satisfies the following condition: for any $y$,

$\sum_{d\mid p^{2}-1,d\in[(\log p)^{1/3},y]}d^{2/3}<y$

Therefore $p$ is selected so that $p^{2}-1$ is not smooth. Not only does this
guarantee connectedness, it also assists with the problem of short cycles. The
length of any orbit must divide $p^{2}-1$, so avoiding small factors will also
avoid small orbits. Fortunately, such primes are difficult to find, and thus
easy to avoid. Different search methods have been proposed for finding smooth
primes (for example, in the appendices of [C] and [FKLPW], the authors produce
two separate approaches), all of which support the claim that finding such
primes is a difficult task.

This is additional evidence that increasing $\eta_{p}$ also increases the
difficulty of path-finding. Thus we recommend that the security parameter be
dependent on both the size of $p$ as well as $\eta_{p}$.

###  2.2 Sampling

Without prior knowledge of the entirety of $\hat{G}_{p}$, how does one
randomly sample a point from $\hat{G}_{p}$? One way would be the following.
Start at a fixed point, say $(1,1,1)$ which is in $\hat{G}_{p}$ for all $p$.
Then perform a random non-backtracking walk starting from $(1,1,1)$, of a
large length $l$, the end of which is our sample. Below we see empirically
that $l$ does not affect the random distribution for sufficiently large $l$:

Figure 7: Graph of $\log$ length of a sample path vs. a sampled estimate of
the size of the cage. Here $p$ is fixed at 5851, and we performed 300 random
walks of length $l$ for each $l$. The data show how many of these 300 samples
are in the cage.

Of course, this method would be truly uniformly random if the family of graphs
$\hat{G}_{p}$ were an expander family. We do have empirical evidence of this,
as well as more compelling evidence from a paper of de Courcy-Ireland and
Magee [dCM]. In particular, they state that $G_{p}$ “resembles” a random
graph, which is a start to examining the spectral gap for the adjacency
matrices of the graphs $G_{p}$.

Specifically, de Courcy-Ireland and Magee show that the distribution of the
eigenvalues of the adjacency matrix of a Markoff graph $G_{p}$ asymptotically
follows the Kesten-McKay law for the distribution of eigenvalues of large
randomly chosen $3$-regular graphs. In general, the Kesten-McKay law says
that, for a large random $d$-regular graph, the expected eigenvalue
probability distribution is

$\rho_{d}(\lambda)=\frac{d}{2\pi}\frac{\sqrt{4(d-1)-\lambda^{2}}}{d^{2}-\lambda^{2}}$

for $|\lambda|\leq 2\sqrt{d-1}$ and is $0$ otherwise.

Let $\mu_{p}$ be the distribution of eigenvalues on $G_{p}$, which range from
$[-3,3]$:

$\mu_{p}=\frac{1}{|G_{p}|}\sum\delta_{\lambda_{j}}$

De Courcy-Ireland and Magee prove the following.

######  Theorem 6 ([dCM], Theorem 1.1).

Given $p$, there exists a constant $L\sim\log{p}$ and a constant $C$,
independent of $p$ and $L$, such that

$\int x^{L}d\mu_{p}=\int x^{L}\rho_{3}(x)dx+O(C^{L}/p)$

However, as mentioned in [dCM], this distribution is not strong enough to show
that the family of graphs $G_{p}$ is an expander family. We would like the
spectral gap to be nonzero, i.e. the number of eigenvalues in the interval
$[3-\epsilon,3]$ to be $O(1)$; the work in [dCM] only proves that this number
is $O(p^{2}/\log{p})$.

For a beautiful graphical comparison of the plot of this distribution to
analogous plots of calculated eigenvalues for the Markoff surface mod $p$ for
$p=83$ and $89$, see Figure 1.1 of [dCM]. While not conclusive, this gives
some indication that the family of Markoff graphs forms an expander family.

##  3 Attack by Pathfinding via the Method of Bourgain-Gamburd-Sarnak

In this section, we go through the key elements of the proof of Theorem 5,
which is necessary for the analysis of how fast of a path-finding algorithm
this produces in section 2.1.

###  3.1 Rotations

A key collection of tools in the proof of Theorem 5 are certain rotations that
are associated to every triple in $\hat{G}_{p}$. In this section, we go over
crucial results about these rotations.

Denote by $\tau_{ij}$ the transposition of the $i$th and $j$th coordinates.

Let $C_{j}(a)$ denote all triples for which the $j$th coordinate is equal to
$a$.

Given a triple $X$, define a _rotation_ function

$\operatorname{rot}_{x_{1}}(X)=\tau_{23}\circ
R_{2}(X)=(x_{1},x_{3},3x_{1}x_{3}-x_{2})$

Note that this function is easily extended to $x_{2}$ or $x_{3}$ by applying
the appropriate permutation to $R_{j}(X)$ for the appropriate $j$.

Further note that without loss of generality we applied $R_{2}$ instead of
$R_{3}$; we can simulate the latter by again applying the appropriate
permutation to $X$. Thus define
$\operatorname{rot}_{x_{2}},\operatorname{rot}_{x_{3}}$ similarly.

Since $\operatorname{rot}_{x_{1}}$ fixes $x_{1}$, we can think of
$\operatorname{rot}_{x_{1}}$ as a function in $(x_{2},x_{3})$ on the plane
defined by setting the first coordinate to be $x_{1}$:

$\operatorname{rot}_{x_{1}}\begin{pmatrix}x_{2}\\\
x_{3}\end{pmatrix}=\begin{pmatrix}0&1\\\
-1&3x_{1}\end{pmatrix}\begin{pmatrix}x_{2}\\\ x_{3}\end{pmatrix}$

So we define the _rotation order_ of $x$ as the order of

$\begin{pmatrix}0&1\\\ -1&\ x\end{pmatrix}\in\mathrm{SL}_{2}(\mathbb{F}_{p})$

Note here we are replacing $3x_{1}$ with $x$. For the remainder of this
section, $x$ will always denote $3x_{1}$.

The rotation order of a triple is then defined to be the maximum rotation
order of its coordinates.

Iteratively applying one rotation to a triple $X$ eventually returns one to
$X$, and we call the set of all such points the _orbit_ of that rotation.

The eigenvalues of the rotation matrix are $\frac{x\pm\sqrt{x^{2}-4}}{2}$, and
so we separate cases depending on whether $\left(\frac{x^{2}-4}{p}\right)=\pm
1$.

  * •

If $x\equiv\pm 2\ (\mathrm{mod}\ p)$, we say $x$ is _parabolic_.

  * •

If $\left(\frac{x^{2}-4}{p}\right)=1$, then $x$ is _hyperbolic_.

  * •

If $\left(\frac{x^{2}-4}{p}\right)=-1$, then $x$ is _elliptic_.

A triple is parabolic/hyperbolic/elliptic if its coordinate with maximal
rotation order is parabolic/hyperbolic/elliptic. These suggestive names will
begin to make more sense if $\hat{G}_{p}$ is pictured literally as a subset of
Euclidean space.

To reiterate an above statement, if we were to say $12\in\mathbb{F}_{17}$ is
hyperbolic, we mean that the coordinate $x_{1}=4$ is hyperbolic.

######  Lemma 7 (Lemma 3 of [BGS1]).

Let $x$ be parabolic, i.e. $x\equiv\pm 2\ (\mathrm{mod}\ p)$. If $p\equiv 3\
(\mathrm{mod}\ 4)$, then $C_{1}(x)$ is empty (i.e. $x$ does not appear in any
triple in $\hat{G}_{p}$). If $p\equiv 1\ (\mathrm{mod}\ 4)$, then

$C_{1}(2/3)=\left(\frac{2}{3},t,t\pm\frac{2i}{3}\right)$
$C_{1}(-2/3)=\left(-\frac{2}{3},t,-t\pm\frac{2i}{3}\right)$

where $i^{2}\equiv-1\ (\mathrm{mod}\ p)$ and $t$ is any number $\
(\mathrm{mod}\ p)$. So $C_{1}(x)$ is a pair of disjoint lines. Furthermore,
the action of $\operatorname{rot}_{x}$ is explicitly given by

$\operatorname{rot}_{x}\left(\left(\frac{2}{3},t,t\pm\frac{2i}{3}\right)\right)=\left(\frac{2}{3},t\pm\frac{2i}{3},t\pm\frac{4i}{3}\right)$
$\operatorname{rot}_{x}\left(\left(-\frac{2}{3},t,-t\pm\frac{2i}{3}\right)\right)=\left(-\frac{2}{3},-t\pm\frac{2i}{3},-t\mp\frac{4i}{3}\right)$

So $\operatorname{rot}_{2}$ fixes each line while $\operatorname{rot}_{-2}$
interchanges them.

###### Proof.

Without loss of generality suppose $x_{1}=\pm 2/3$. Then equation (1) reduces
to

$x_{2}^{2}+x_{3}^{2}+\frac{4}{9}\mp 2x_{2}x_{3}\equiv 0\ (\mathrm{mod}\ p)$
$(x_{2}\mp x_{3})^{2}\equiv-\frac{4}{9}\ (\mathrm{mod}\ p)$

So a solution exists if and only if $\left(\frac{-1}{p}\right)=1$, which is
equivalent to $p\equiv 1\ (\mathrm{mod}\ 4)$.

Set $p\equiv 1\ (\mathrm{mod}\ 4)$ and suppose $C_{1}(2/3)=(2/3,t,t+a)$. Then
we have

$t^{2}+(t+a)^{2}+\frac{4}{9}-2t(t+a)\equiv 0\ (\mathrm{mod}\ p)$

which reduces to $a^{2}\equiv-4/9\ (\mathrm{mod}\ p)$ independent of $t$,
which gives the desired result.

Similarly suppose $C_{1}(-2/3)=(-2/3,t,-t+a)$, which gives

$t^{2}+(-t+a)^{2}+\frac{4}{9}+2t(-t+a)\equiv 0\ (\mathrm{mod}\ p)$

which again reduces to $a^{2}\equiv-4/9\ (\mathrm{mod}\ p)$ which again gives
the desired result.

Now we can explicitly calculate

$\operatorname{rot}_{2}\left(\left(\frac{2}{3},t,t\pm\frac{2i}{3}\right)\right)=\left(\frac{2}{3},t\pm\frac{2i}{3},3\frac{2}{3}\left(t\pm\frac{2i}{3}\right)-t\right)=\left(\frac{2}{3},t\pm\frac{2i}{3},t\pm\frac{4i}{3}\right)$
$\displaystyle\operatorname{rot}_{-2}\left(\left(-\frac{2}{3},t,-t\pm\frac{2i}{3}\right)\right)$
$\displaystyle=\left(-\frac{2}{3},-t\pm\frac{2i}{3},-3\frac{2}{3}\left(-t\pm\frac{2i}{3}\right)-t\right)$
$\displaystyle=\left(-\frac{2}{3},-t\pm\frac{2i}{3},-t\mp\frac{4i}{3}\right)$

as desired. ∎

Here is an example in $G_{17}$, where $17\equiv 1\ (\mathrm{mod}\ 4)$, $2/3\
(\mathrm{mod}\ p)=12$, and $i\equiv 4\ (\mathrm{mod}\ 17)$.

Figure 8: (a) Two lines in $C_{1}(12)$ fixed by $\operatorname{rot}_{12}$. (b)
Two lines in $C_{1}(5)$ interchanged by $\operatorname{rot}_{5}$.

######  Lemma 8.

If $x$ is not parabolic, then we can write

$x=\chi+\chi^{-1}$

where $\chi\in\mathbb{F}_{p}$ if $x$ is hyperbolic, and
$\chi\in\mathbb{F}_{p^{2}}$ if $x$ is elliptic.

###### Proof.

Suppose $x$ is hyperbolic, i.e. $\left(\frac{x^{2}-4}{p}\right)=1$. Then
suppose $x^{2}-4=r^{2}$. Set $\chi=(x+r)/2$, $\chi^{-1}=(x-r)/2$, and verify

$\frac{x+r}{2}\frac{x-r}{2}=\frac{x^{2}-r^{2}}{4}=1$

Then we have

$r^{2}=(\chi-\chi^{-1})^{2}=\chi^{2}+\chi^{-2}-2=(\chi+\chi^{-1})^{2}-4$

as desired. Now similarly suppose $x$ is elliptic. Then $x^{2}-4$ is not a
residue in $\mathbb{F}_{p}$, but it is a residue in

$\mathbb{F}_{p^{2}}\simeq\frac{\mathbb{F}_{p}[y]}{y^{2}-(x^{2}-4)}$

Set $x^{2}-4=r^{2}$ where $r\in\mathbb{F}_{p^{2}}$ and repeat the above
argument. ∎

Upon diagonalizing the rotation matrix $\operatorname{rot}_{x}$, one arrives
at

$\displaystyle\operatorname{rot}_{x}$ $\displaystyle=\begin{pmatrix}1&1\\\
\chi&\chi^{-1}\end{pmatrix}\begin{pmatrix}\chi&0\\\
0&\chi^{-1}\end{pmatrix}\begin{pmatrix}1&1\\\
\chi&\chi^{-1}\end{pmatrix}^{-1}$
$\displaystyle=(\chi^{-1}-\chi)^{-1}\begin{pmatrix}1&1\\\
\chi&\chi^{-1}\end{pmatrix}\begin{pmatrix}\chi&0\\\
0&\chi^{-1}\end{pmatrix}\begin{pmatrix}\chi^{-1}&-1\\\ -\chi&1\end{pmatrix}$

Thus

$\displaystyle(\operatorname{rot}_{x})^{l}$
$\displaystyle=(\chi^{-1}-\chi)^{-1}\begin{pmatrix}1&1\\\
\chi&\chi^{-1}\end{pmatrix}\begin{pmatrix}\chi^{l}&0\\\
0&\chi^{-l}\end{pmatrix}\begin{pmatrix}\chi^{-1}&-1\\\ -\chi&1\end{pmatrix}$
$\displaystyle=(\chi^{-1}-\chi)^{-1}\begin{pmatrix}\chi^{l-1}-\chi^{1-l}&-\chi^{l}+\chi^{-l}\\\
\chi^{l}-\chi^{-l}&-\chi^{l+1}+\chi^{-l-1}\end{pmatrix}$

If we consider $\chi^{l}=t$, where $t\in\langle\chi\rangle$, then we have

$\langle\operatorname{rot}_{x}\rangle=\left\\{(\chi^{-1}-\chi)^{-1}\begin{pmatrix}\chi^{-1}t-\chi
t^{-1}&t^{-1}-t\\\ t-t^{-1}&\chi^{-1}t^{-1}-\chi
t\end{pmatrix}:t\in\langle\chi\rangle\right\\}$

Thus

$\displaystyle C_{1}(x)$
$\displaystyle=\left\\{(\chi^{-1}-\chi)^{-1}\begin{pmatrix}\chi^{-1}t-\chi
t^{-1}&t^{-1}-t\\\ t-t^{-1}&\chi^{-1}t^{-1}-\chi
t\end{pmatrix}\begin{pmatrix}x_{2}\\\
x_{3}\end{pmatrix}:t\in\langle\chi\rangle\right\\}$
$\displaystyle=(\chi-\chi^{-1})^{-1}\Big{(}t(x_{3}-\chi^{-1}x_{2})+t^{-1}(\chi
x_{2}-x_{3}),$ (3) $\displaystyle\quad t(\chi
x_{3}-x_{2})+t^{-1}(x_{2}-\chi^{-1}x_{3})\Big{)}$ (4)

again for $t\in\langle\chi\rangle$. Now we can rewrite the second coordinate
as $at+bt^{-1}$ where

$a=\frac{x_{3}-\chi^{-1}x_{2}}{\chi-\chi^{-1}},\quad b=\frac{\chi
x_{2}-x_{3}}{\chi-\chi^{-1}}$

Later we will need the fact that

$ab=\frac{x_{2}x_{3}(\chi+\chi^{-1})-x_{2}^{2}-x_{3}^{2}}{(\chi-\chi^{-1})^{2}}=\frac{x^{2}}{(\chi-\chi^{-1})^{2}}=\left(\frac{\chi+\chi^{-1}}{\chi-\chi^{-1}}\right)^{2}\neq
1$ (5)

Now we consider the cases of $x$ hyperbolic or elliptic separately.

  * •

For $x$ hyperbolic: From equation (4), note that $a,b\in\mathbb{F}_{p}^{*}$,
so substitute $t\mapsto ta^{-1}$ to see that

$C_{1}(x)=\left\\{\left(t+\frac{ab}{t},\chi t+\frac{ab}{\chi
t}\right):t\in\mathbb{F}_{p}^{*}\right\\}$

Applying the rotation gives

$\operatorname{rot}_{x}\left(t+\frac{ab}{t},\chi t+\frac{ab}{\chi
t}\right)=\left(\chi t+\frac{ab}{\chi
t},\chi^{2}t+\frac{ab}{\chi^{2}t}\right)$ (6)

Since $t\in\mathbb{F}_{p}^{*}$, we see that $|C_{1}(x)|=p-1$. On the other
hand, since $x$ is hyperbolic, by Lemma 8, we can write

$x=\rho^{j}+\rho^{-j}$

where $\rho$ is a primitive root of $\mathbb{F}_{p}$. Then if we iteratively
apply $\operatorname{rot}_{x}$, we cycle through $\frac{p-1}{j}$ elements in
$C_{1}(x)$, i.e. the rotation order of $\operatorname{rot}_{x}$ is
$\frac{p-1}{j}$ for some $j$.

An explicit example of this can be seen below in Figure 9 for the case of
$G_{17}$:

Figure 9: (a) A maximal order hyperbolic rotation $\operatorname{rot}_{3}$
shown in the plane $C_{1}(3)$. (b) A hyperbolic rotation
$\operatorname{rot}_{2}$ of order $8=\frac{p-1}{2}$ in $C_{1}(2)$. The line
$x_{2}=x_{3}$ is shown for symmetry.

  * •

For $x$ elliptic, the derivation is similar. We start by rewriting

$x=\chi+\chi^{-1}=\nu+\nu^{p}$

for $\nu\in\mathbb{F}_{p^{2}}-\mathbb{F}_{p}$. Then applying the rotation
gives

$\operatorname{rot}_{x}\left(x,t,\frac{\kappa_{x}}{t}\right)=\left(x,t+\frac{\kappa_{x}}{t},t\nu+\frac{\kappa_{x}}{t\nu}\right)$
(7)

which implies

$C_{1}(x)=\left\\{\left(t+\frac{ab}{t},\nu t+\frac{ab}{\nu
t}\right):t\in\mathbb{F}_{p^{2}}^{*},\quad t^{p+1}=ab\right\\}$

where the latter requirement implies
$t\in\mathbb{F}_{p^{2}}\backslash\mathbb{F}_{p}$, which in turn implies
$|C_{1}(x)|=p+1$. On the other hand, since $x$ is elliptic, by Lemma 8, we can
write

$x=\xi^{j}+\xi^{-j}$

where $\xi$ is some element of $\mathbb{F}_{p^{2}}$. Explicitly, if $\gamma$
is a generator of $(\mathbb{F}_{p^{2}})^{\times}$, then $\xi=\gamma^{p+1}$. So
if we iteratively apply $\operatorname{rot}_{x}$, we cycle through
$\frac{p+1}{j}$ elements in $C_{1}(x)$, i.e. the rotation order of $x_{1}$ is
$\frac{p+1}{j}$ for some $j$.

An explicit example of rotations for elliptic and hyperbolic elements in
$G_{17}$ can be seen in Figure 10.

Figure 10: (a) A maximal order elliptic rotation $\operatorname{rot}_{7}$
shown in the plane $C_{1}(7)$. (b) A hyperbolic rotation
$\operatorname{rot}_{8}$ of order $9=\frac{p+1}{2}$ in $C_{1}(9)$.

From the above discussion, we have that $x$ has a maximal rotation order of
$p-1$ if $x$ is hyperbolic, $p+1$ if it is elliptic, or $p,2p$ if it is
parabolic. If any of these cases applies to $x$, we say $x$ is maximal
hyperbolic/elliptic/parabolic respectively. A triple is maximal
(hyperbolic/elliptic/parabolic) if one if its coordinates is with respect to
its corresponding type (again remembering that $x=3x_{1}$).

Note that the rotation order of a parabolic $x$ is either $p$ or $2p$. We
consider both of these elements to be maximal parabolic. If a triple $X$
contains either element, we can connect $X$ to a triple containing any
coordinate.

###  3.2 The End Game

We are now ready to delve into the BGS algorithm. In this section we aim to
show that any element of order $p^{1/2+\delta}$ for $\delta>0$ can be
connected to a triple with a coordinate that is maximal with respect to its
type. Later on we will show that every element in $\hat{G}_{p}$ can be
connected to a triple of maximal order, and that such maximal triples
themselves can be connected, implying the connectedness of $\hat{G}_{p}$.

######  Proposition 9 (Proposition 7 of [BGS1]).

Let $X$ be a triple with rotation order at least $p^{1/2+\delta}$ for
$\delta>0$ fixed. Then $X$ is connected to a maximal triple $Y$.

As defined above, the triple $X$ can be classified as hyperbolic, elliptic, or
parabolic.

The parabolic case is trivial. As we discussed above, we can connect a
parabolic triple to an arbitrary coordinate.

Let us first suppose the element is hyperbolic. Then applying (6) to $X$ gives
elements of the form

$(x_{1},\alpha_{1}t+\alpha_{2}t^{-1},\alpha_{3}t+\alpha_{4}t^{-1})$

Here $\alpha_{i}\in\mathbb{F}_{p}^{*}$ and $t\in H$, where $H$ is some cyclic
subgroup of $\mathbb{F}_{p}^{*}$. If we want to connect $X$ to a maximal
triple by iteratively applying (6), we would like the second coordinate to
eventually take the form $\rho+\rho^{-1}$, where $\rho$ is a primitive root of
$F_{p}^{*}$. The latter is exactly the form of a maximal hyperbolic element.

So let $P(H)$ denote the number of solutions to

$\alpha_{1}t+\alpha_{2}t^{-1}=\rho+\rho^{-1}$ (8)

where $\rho$ is a primitive root of $\mathbb{F}_{p}^{*}$.

On the other hand, let $K$ be an arbitrary subgroup of $\mathbb{F}_{p}^{*}$.
Now define $P(H,K)$ to be the number of solutions to (8) where we require
$\rho\in K$ instead of $\rho$ being a primitive root.

The subgroups $H$ and $K$ are determined by their indices in
$\mathbb{F}_{p}^{*}$; set $d_{K}=(p-1)/|K|$ and $d_{H}=(p-1)/|H|$.

Now suppose $(t,y)$ is a solution to

$\alpha_{1}t^{d_{H}}+\alpha_{2}t^{-d_{H}}=y^{d_{K}}+y^{-d_{K}}$ (9)

Then the map $(t,y)\mapsto(t^{d_{H}},y^{d_{K}})$ sends solutions of (9) to
solutions of (8); this map is $d_{H}d_{K}$ to 1.

Thus if $N(\alpha_{1},\alpha_{2})$ is the number of solutions to (9), then

$P(H,K)=\frac{N(\alpha_{1},\alpha_{2})}{d_{H}d_{K}}$

As shown by Lemma 8 of [BGS1], the curve

$\alpha_{1}t^{d_{H}}+\alpha_{2}t^{-d_{H}}-y^{d_{K}}-y^{-d_{K}}$

given by (9) is absolutely irreducible with genus $O(d_{H}d_{K})$. Thus
applying the Hasse-Weil bound for irreducible curves gives

$N(\alpha_{1},\alpha_{2})=p+O(d_{H}d_{K}\sqrt{p})$

which in turn gives

$P(H,K)=\frac{p}{d_{H}d_{K}}+O(\sqrt{p})$ (10)

We now want to express $P(H)$ in terms of $P(H,K)$. We use inclusion/exclusion
on $K$ to eventually find all primitive roots. Let $p_{i}$ be the distinct
prime factors of $p-1$. Also let $K_{d}$ be the subgroup of
$\mathbb{F}_{p}^{*}$ of index $d$, e.g. $K_{1}=\mathbb{F}_{p}^{*}$ and
$K_{p-1}=\\{1\\}$. Then we have:

$\displaystyle P(H)$
$\displaystyle=P(H,K_{1})-\sum_{i}P(H,K_{p_{i}})+\sum_{i,j}P(H,K_{p_{i}p_{j}})-\cdots$
$\displaystyle=\sum_{d\mid p-1}\mu(d)P(H,K_{d})$ (11)

Plugging (10) into (11) gives

$\displaystyle P(H)$ $\displaystyle=\sum_{d\mid
p-1}\mu(d)\left(\frac{|H|}{d}+O(\sqrt{p})\right)$
$\displaystyle=\left(|H|\sum_{d\mid
p-1}\frac{\mu(d)}{d}\right)+O(p^{1/2+\epsilon})$
$\displaystyle=\left(|H|\frac{\phi(p-1)}{p-1}\right)+O(p^{1/2+\epsilon})$
$\displaystyle\geq|H|(p-1)^{-\epsilon}+O(p^{1/2+\epsilon})$

We assumed our initial triple $X$ had order $\geq p^{1/2+\delta}$, i.e.
$|H|\geq p^{1/2+\delta}$. Thus $P(H)>1$ and so there exists at least one
solution to equation (8). This implies that the orbit of this rotation
contains a maximal triple and the hyperbolic case is handled.

The elliptic case is covered in detail in Section 3 of [BGS1]. However, as the
technical details of their argument are not needed for the paper at hand, we
omit them and move on to showing the collection of maximal elements is
connected.

####  3.2.1 Connectedness of the Cage

The vertices in $\hat{G}_{p}$ corresponding to triples of maximal order form a
connected component [BGS1]. Consider $C_{j}(\alpha)\cap C_{k}(\beta)$ with
$j\neq k$, and without loss of generality let $j=1,k=2$. Also suppose
$\alpha,\beta\neq 0,\pm 2/3$. Going forward we sometimes denote
$C_{1}(\alpha)$ as $(\alpha,?,?)$ and $C_{1}(\alpha)\cap C_{2}(\beta)$ as
$(\alpha,\beta,?)$.

Then

$|C_{1}(\alpha)\cap C_{2}(\beta)|=|(\alpha,\beta,?)|=0,1,2$

In particular, the intersection consists of all $\gamma$ such that
$\alpha^{2}+\beta^{2}+\gamma^{2}-3\alpha\beta\gamma=0$, which has a solution
in $\gamma$ if

$\left(\frac{9\alpha^{2}\beta^{2}-4(\alpha^{2}+\beta^{2})}{p}\right)\geq 0$

In particular

$|(\alpha,\beta,?)|=1+\left(\frac{9\alpha^{2}\beta^{2}-4(\alpha^{2}+\beta^{2})}{p}\right)\geq
0$

So consider the _incidence graph_ $I(p)$ of $\hat{G}_{p}$. The vertices of
$I(p)$ are $C_{j}(\alpha)$ and the number of edges between $C_{j}(\alpha)$ and
$C_{k}(\alpha)$ is $|(\alpha,\beta,?)|$.

######  Proposition 10 (Proposition 6 of [BGS1]).

For $p>10$, the incidence graph is connected and in fact has diameter 2.

###### Proof.

We want to connect $C_{1}(\alpha)$ and $C_{2}(\beta)$. Thus we want to find
$\gamma$ such that both $(\alpha,?,\gamma)$ and $(?,\beta,\gamma)$ are
nonempty. So suppose there is a point $(\alpha,l,\gamma)$; solve the quadratic
in the second coordinate to see that we must have

$9\alpha^{2}\gamma^{2}-4\alpha^{2}-4\gamma^{2}=\lambda^{2}$

for some $\lambda$. Similarly we must have that

$9\beta^{2}\gamma^{2}-4\beta^{2}-4\gamma^{2}=\mu^{2}$

for some $\mu$. Rearrange the two equations into the system

$\begin{cases}(9\alpha^{2}-4)\gamma^{2}-\lambda^{2}=4\alpha^{2}\\\
(9\beta^{2}-4)\gamma^{2}-\mu^{2}=4\beta^{2}\end{cases}$ (12)

If $\alpha^{2}=\beta^{2}$, then we just take $\lambda=\mu$, and we can reduce
(12) to one equation and find an explicit value for $\gamma$. Otherwise (12)
is an irreducible curve for which we know a solution in $\gamma$ exists for
$p>10$. So the diameter of the incidence graph is at most 2. But of course
$C_{1}(\alpha)$ is not connected to $C_{1}(\beta)$ if $\alpha\neq\beta$. Thus
the diameter is precisely 2. ∎

Define the _cage_ to be the subset of maximal triples. We claim the cage is
connected, i.e. path-connected.

Suppose $X$ is a maximal triple with maximal coordinate $\alpha$, say
$X=(\alpha,?,?)$. Suppose $Y$ is a maximal triple with maximal coordinate
$\beta$, say $Y=(?,\beta,?)$. By Proposition 10, we know there exists a
$\gamma$ such that both $(\alpha,?,\gamma)$ and $(?,\beta,\gamma)$ are
nonempty. However, we need $\gamma$ to have maximal order:

${(\alpha,?,?)}$${(\alpha,?,\gamma)}$${(?,\beta,\gamma)}$${(?,\beta,?)}$$\scriptstyle{\alpha\text{
maximal}}$$\scriptstyle{\gamma\text{ maximal}}$$\scriptstyle{\beta\text{
maximal}}$

The paper of Bourgain, Gamburd, and Sarnak [BGS1] finishes the proof to
guarantee the existence of such a maximal $\gamma$. Thus the cage is
connected. We now illuminate this approach through a concrete example.

####  3.2.2 Constructive Example

Let’s now walk through a simple example to show how vertices are connected
using the BGS algorithm. Take $p=17$. We have the elements along with their
order and type in the following table.

Element | Order | Type
---|---|---
0 | 4 | parabolic
1 | 18 | elliptic
2 | 8 | hyperbolic
3 | 16 | hyperbolic
4 | 16 | hyperbolic
5 | 34 | parabolic
6 | 6 | elliptic
7 | 18 | elliptic
8 | 9 | elliptic
9 | 18 | elliptic
10 | 9 | elliptic
11 | 3 | elliptic
12 | 17 | parabolic
13 | 16 | hyperbolic
14 | 16 | hyperbolic
15 | 8 | hyperbolic
16 | 9 | elliptic

Consider the triple $X=(15,0,8)\in G_{17}$. This triple is not maximal, but it
does have order $>p^{1/2+\delta}$. By Lemma 9, we should be able to connect
$X$ to the cage through rotations of its maximal element.

Since the coordinate 8 has the highest order, we consider
$\operatorname{rot}_{8}$ applied to $X$:

$(15,0,8)\mapsto(0,2,8)\mapsto(2,14,8)\mapsto(14,11,8)\mapsto(11,12,8)\mapsto(12,5,8)\mapsto$
$(5,6,8)\mapsto(6,3,8)\mapsto(3,15,8)\mapsto(15,0,8)$

which is just a shuffle of the coordinates

$15-0-2-14-11-12-5-6-3-15$

for which 14 and 3 are maximal hyperbolic, and 12 and 5 are maximal parabolic.
Thus we can connect $X$ to the cage in a number of ways.

A visual representation of this rotation within the plane $C_{3}(8)$ is given
in Figure 11.

Figure 11: $\operatorname{rot}_{8}$ applied to $(15,0,8)$ in the plane
$C_{3}(8)$.

###  3.3 The Middle Game and The Opening

In this section we aim to show that any triple $X$ of small order can be
connected to the cage in a finite number of moves. By small order, we mean
triples $X$ whose order is $p^{\varepsilon}$ (which we refer to as The Middle
Game) or those whose order is less than $p<c$ for some constant $c$, i.e.
points whose orders are uniformly bounded independent of $p$ (which we refer
to as The Opening).

We first handle the Middle Game in detail, and then outline how the Opening
comes into play. In particular, we connect a triple of order $p^{\varepsilon}$
to the cage by showing that one can connect it to a triple whose order is
strictly greater than that of the original triple, and then iterate the
process until we have a triple of order $p^{1/2+\delta}$ and we are in the End
Game. This is done via the following procedure:

Define the _maximal orbit_ $M_{X}$ of a triple $X$ as the orbit corresponding
to the rotation of the maximal coordinate of $X$. So if $X$ is a triple with
order $l$, then $|M_{X}|=l$. Any orbit occurs with respect to either the
first, second, or third coordinate; we call this number the index of the
orbit.

  1. 1.

Let $Y\in M_{X}$ and $l_{Y}$ be the order of $Y$. Of course $l,l_{Y}\mid
p^{2}-1$.

  2. 2.

If $l_{Y}>l$, then necessarily the index of $M_{Y}$ is not equal to the index
of $M_{X}$. Then replace $X$ with $Y$, thereby strictly increasing the order
of $X$.

  3. 3.

Otherwise, $l_{Y}\leq l$. Consider the sum

$N_{l}=\sum_{l^{\prime}\leq l}\\#\\{Y\in M_{X}:l_{Y}=l^{\prime}\\}$ (13)

If $N_{l}<l$, then there must be a point $Z\in M_{X}$ whose order is strictly
greater than that of $X$. We can then replace $X$ with $Z$ and repeat this
process until we arrive at an element with order at least $p^{1/2+\delta}$,
which is a reduction to the endgame. This must happen because the order
strictly increases at each step and $p^{2}-1$ has finitely many divisors.

Now we need to effectively bound $N_{l}$. As seen in the endgame, every $Y$
(with order $l_{Y}\mid p^{2}-1$) in the maximal orbit of $X$ corresponds to a
solution of the equation:

$\begin{cases}h_{1}+\frac{\sigma}{h_{1}}=h_{2}+\frac{1}{h_{2}}\\\ h_{1}\in
H_{1},h_{2}\in H_{2}\\\ H_{1},H_{2}\text{ subgroups of
}\mathbb{F}_{p}^{*}\text{ or }\mathbb{F}_{p^{2}}^{*}\\\
\sigma\in\mathbb{F}_{p}\end{cases}$ (14)

where $|H_{1}|=l$ and $|H_{2}|=l_{Y}$. Also, from equation (5), we have that
$\sigma\neq 1$. So we see that in fact $N_{l}$ denotes precisely the number of
solutions to (14), so equivalently we want an upper bound on the number of
solutions to (14). The following bound is derived in [BGS1], based off
previous work of Bourgain (Proposition 2 in [B10]).

######  Proposition 11 (Proposition 10 of [BGS1]).

Given $\delta>0$ there is $\tau<1$ and $C_{\tau}$ depending on $\delta$ such
that if $p^{\delta}<|H_{1}|<p^{1-\delta}$ then the number of solutions to (14)
is at most $C_{\tau}|H_{1}|^{\tau}$.

From this proposition, we simply deduce

$N_{l}\leq C_{\tau}|H_{1}|^{\tau}=C_{\tau}l^{\tau}$

which provides a necessary upper bound to the number of solutions of (14), as
desired.

Thus any triple of order at least $p^{\epsilon}$ can be connected to the cage,
and so all triples of order at least $p^{\epsilon}$ are connected. This
algorithm is essential for our cryptographic constructions, and provides the
backbone to the first step in connecting two triples $X$ and $Y$ as discussed
in Section 2.1.

Next we consider the part of the BGS algorithm that is called “the Opening,”
in [BGS1]: that is, the rest of the points in $\hat{G}_{p}$ whose order is
less than $p<c$ for some constant $c$, that is points whose orders are
uniformly bounded.

In the Opening section of [BGS1], Bourgain, Gamburd, and Sarnak prove that one
can connect triples with uniformly bounded orders to the cage to conclude that
the Markoff graph mod $p$ is connected; however their methods are non-
constructive. To go about this, they look at the characteristic 0 case and
show that there are no finite $\Gamma$-orbits. As this method is not needed in
our cryptographic analysis of $\hat{G}_{p}$, we omit the technicalities and
direct the interested reader to Section 5 of [BGS1] for a comprehensive
analysis of the Opening.

The proof of Theorem 5 presented throughout Section 3 provides us with an
algorithmic approach to finding paths in $\hat{G}_{p}$, thus establishing
connectivity of $\hat{G}_{p}$. This method need not be optimal but the
cryptographic analysis in Section 2.1 elucidates the strength of the
cryptosystem against the BGS-style attack. We now look at another possible
avenue of path-finding based off lifting solutions to $\mathbb{Z}$ and
exploiting the structure of the Markoff tree.

##  4 Attack by Lifting

The main observation behind our plan of attack is the following lemma.

######  Lemma 12.

Let $(x_{1},x_{2},x_{3})$ be a Markoff triple in $\mathbb{Z}^{3}$ whose $i$-th
coordinate $x_{i}$ is maximal, and $x_{i}>1$. Then applying $R_{i}$ to the
triple decreases the size of the $i$-th entry. Formally, suppose
$|x_{i}|\geq|x_{k}|$ for all $1\leq k\leq 3$ in the Markoff triple
$(x_{1},x_{2},x_{3})$. Let $(x_{1,i},x_{2,i},x_{3,i})$ be the triple obtained
from applying the $i$-th involution $R_{i}$ to the triple:

$(x_{1,i},x_{2,i},x_{3,i}):=R_{i}(x_{1},x_{2},x_{3}).$

Then $|x_{i,i}|<|x_{i}|$.

###### Proof.

Let $x_{j},x_{k}$ be the other two coordinates of the triple
$(x_{1},x_{2},x_{3})$ besides $x_{i}$. Note that, since $|x_{i}|>1$, it is
impossible for $(x_{i},x_{j},x_{k})$ to satisfy (1) if
$|x_{i}|=|x_{j}|=|x_{k}|$. In fact, in this case we have that $|x_{i}|$ must
be strictly larger than $|x_{j}|$ and $|x_{k}|$ in order for (1) to be true.
Suppose further without loss of generality that $|x_{j}|\leq|x_{k}|$.

We have $x_{i,i}=3x_{j}x_{k}-x_{i}$. If $x_{i}>0$, then $x_{j}x_{k}>0$ in
order for (1) to be satisfied, and, again by (1) we have

$3x_{j}x_{k}=(x_{1}^{2}+x_{2}^{2}+x_{3}^{2})/x_{i}>x_{i},$

so that

$|x_{i,i}|=|3x_{j}x_{k}-x_{i}|=3x_{j}x_{k}-x_{i}.$

Our goal is hence to show that $2x_{i}-3x_{j}x_{k}>0$. We have by (1) that

$2x_{i}-3x_{j}x_{k}=2x_{i}-\frac{x_{i}^{2}+x_{j}^{2}+x_{k}^{2}}{x_{i}}=\frac{x_{i}^{2}-x_{j}^{2}-x_{k}^{2}}{x_{i}},$

which, given that $x_{i}>0$, is positive if and only if the numerator is
positive. Rewrite the numerator as

$x_{i}^{2}+x_{j}^{2}+x_{k}^{2}-(2x_{j}^{2}+2x_{k}^{2})$

and compare with the left side of (1). We claim that
$2x_{j}^{2}+2x_{k}^{2}<3x_{i}x_{j}x_{k}$, which would imply that the numerator
above is positive as desired.

It remains to prove our claim. Given that $x_{i}>|x_{j}|$ and
$|x_{k}|\geq|x_{j}|$, we have

$3x_{i}x_{j}x_{k}>x_{i}x_{j}x_{j}+2|x_{k}|x_{j}x_{k}\geq
2x_{j}^{2}+2x_{k}^{2}$

as desired where the last inequality is true since $x_{i}\geq 2$ and
$|x_{j}|\geq 1$. So, if $x_{i}>0$ we are done.

If $x_{i}<0$ the argument is nearly identical. We would have that $x_{i,i}<0$
in that case, and so our goal would be to show that
$-3x_{j}x_{k}+x_{i}<-x_{i},$ or that $2x_{i}-3x_{j}x_{k}<0$. Given that
$(-x_{i},-x_{j},x_{k})$ is a triple satisfying the properties in the first
case above where $x_{i}>0$, the argument above shows that
$-2x_{i}+3x_{j}x_{k}>0$, which is exactly what we need. ∎

This lemma gives a very straightforward way of finding a path from any triple
$(x_{1},x_{2},x_{3})$ in the tree to the triple that is the “origin,” or
$(1,1,1)$ in absolute value, which in turn gives a simple way of finding a
path between any two vertices in the tree. Thus if triples can be efficiently
lifted from the graph $G_{p}$ to the tree, this algorithm gives a path-finding
attack on the graph. The algorithm is as follows. Start with $W=I$, the
identity.

  1. 1.

If $(|x_{1}|,|x_{2}|,|x_{3}|)=(1,1,1)$ then we are done, and $W$ is the word
that describes the path from $(x_{1},x_{2},x_{3})$ to the origin. If not,
determine $i$ such that the $i$-th coordinate of $(|x_{1}|,|x_{2}|,|x_{3}|)$
is largest. Go to step 2.

  2. 2.

Replace $(x_{1},x_{2},x_{3})$ with $R_{i}((x_{1},x_{2},x_{3}))$, replace $W$
with $WR_{i}$, and go to step 1.

By the lemma, this algorithm will continuously decrease every largest
coordinate in absolute value until each coordinate is $1$ in absolute value.
For example, for the triple $(29,-169,-14701)$ it gives

$(29,-169,-14701)\xrightarrow{R_{3}}(29,-169,-2)\xrightarrow{R_{2}}(29,-5,-2)\xrightarrow{R_{1}}(1,-5,-2)$
$\xrightarrow{R_{2}}(1,-1,-2)\xrightarrow{R_{3}}(1,-1,-1).$

Coming back to our problem of finding paths between two points in the graph
$G_{p}$,, if our attacker is able to take a triple
$(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})$ which satisfies the Markoff
equation modulo $p$ and lift it to a solution $(x_{1},x_{2},x_{3})$ to the
Markoff equation in $\mathbb{Z}$, then she need only run the algorithm above
to find a path from $(x_{1},x_{2},x_{3})$ to the origin in which every
coordinate is $1$ in absolute value in order to find a path from
$(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})$ to the origin in $G_{p}$ (it
is the path corresponding to the same word as the one she will obtain from the
above algorithm).

However, so far it appears that finding a Markoff triple that reduces to
$(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})$ modulo $p$ is difficult for
most candidate $(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})$’s. The reason
for this is that, according to [Z], the number of Markoff triples in which the
largest coordinate is at most $T$ is asymptotic to $C(\log T)^{2}$ for some
constant $C$, while the number of vertices in $G_{p}\sim p^{2}$. So in order
to have a chance of covering all possible mod-$p$ Markoff triples coming from
$G_{p}$ by Markoff triples over $\mathbb{Z}$, one must consider all those
triples less than $T$ where

$C(\log T)^{2}\geq p^{2},$

or, in other words, where $T$ is of size roughly $e^{p}$. More likely, $T$
will have to be much larger than that, since it is not at all true that all
Markoff numbers less than $T$ reduce to a different triple modulo $p$. Even
with this estimate of $e^{p}$, however, one sees that the lifts will probably
be very large (since $p$ itself will be taken to be large), and certainly no
straightforward search for a lift in $\mathbb{Z}$ will be computationally
feasible.

Constructing a collision attack from lifting is almost equivalent to path
finding. If one has a method of efficiently finding lifts to $\mathbb{Z}$, two
lifts of the same triple could result in two distinct paths between triples.
Unless the two paths in $\mathbb{Z}$ overlap nontrivially, we would have a
collision starting with $(0,0,0)$.

##  5 Other Possible Attacks and Future Avenues for Research

We note that the BGS algorithm can be slightly modified to search for
collision resistance. Currently, the steps of the middle game are
deterministic in connecting a triple to the cage; the rotations are always
done on the maximal coordinate. For a collision attack, we would search for
two distinct paths between points. So instead of always choosing the maximal
coordinate, we can randomly choose coordinates instead (not necessarily
uniformly). If we eventually arrive at the cage, then we have found another
distinct path, since the cage is connected. Of course, there is no proof,
other than empiricism, that any method other than choosing the maximal
coordinate will succeed in a similar way.

Many potential attacks involve finding small cycles on $G_{p}$ or
$\hat{G}_{p}$, e.g. some adaptation of the Pollard rho algorithm. There are a
number of reasons we believe such a study is unfruitful. A Pollard-style
attempt would look for cycles by repeatedly applying a single involution. The
construction of $G_{p}$ means that such short cycles occur with vanishingly
little frequency, as discussed in the Opening. In any case, such discrete
logarithm attacks must involve at least $\Omega(\sqrt{p})$ group operations
[S], which is not a significant improvement.

Nonetheless, it will certainly be important to understand better the
distribution of cycle lengths in a graph $G_{p}$ or $\hat{G}_{p}$. While it is
known that small cycles in $\hat{G}_{p}$ exist, it is not known how common
they are, and how likely one is to run into one in practice. Even less is
known about the cycles in the graph $G_{p}$. This is a problem the authors
hope to explore in a future paper.

In addition, it would be helpful to have a better picture of the size of an
average lift of a Markoff triple mod $p$ to one over $\mathbb{Z}$, so that we
can further understand the potential for success of the lifting attack
described in Section 4. This is currently being studied by the first-named
author together with co-authors E. Bellah, S. Kim, D. Schindler, J. Sivaraman,
and L. Ye.

## References

  * [BH] Laszlo Babai, Thomas P. Hayes. The probability of generating the symmetric group when one of the generators is random. Publ. Math. Debrecen, 69 No. 3 (2006), pp. 271-280.
  * [B] Jean Bourgain. A modular Szemeredi-Trotter theorem for hyperbolas. arXiv:1208.4008.
  * [BGS1] Jean Bourgain, Alexander Gamburd, Peter Sarnak. Markoff Surfaces and Strong Approximation: 1. arXiv:1607.01530.
  * [BGS2] Jean Bourgain, Alexander Gamburd, Peter Sarnak. Markoff Surfaces and Strong Approximation. arXiv:1505.06411.
  * [CGL] Denis X. Charles, Eyal Z. Goren, and Kristin E. Lauter. Cryptographic hash functions from expander graphs. J. Cryptology, Vol. 22 (1), (2009) 93–113. eprint.iacr.org/2006/021
  * [Ch] William Chen, Nonabelian level structures, Nielsen equivalence, and Markoff triples, preprint (2021) https://static1.squarespace.com/static/59b0d0048419c2e19a207ba7/ t/608608553348ca47ee4941e3/1619396694639/congruence.pdf.
  * [CFLMP] Anamaria Costache, Brooke Feigon, Kristin Lauter, Maike Massierer and Anna Puskas. Ramanujan graphs in cryptography. In: Research Directions in Number Theory: Women in Numbers IV, Association for Women in Mathematics Series, Vol. 19, pp. 1–40 (2019) Springer.
  * [C] Craig Costello. B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion, In: International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology – ASIACRYPT 2020 (2020), pp. 440-463.
  * [dCM] Matthew de Courcy-Ireland, Michael Magee. Kesten-McKay law for the Markoff surface mod $p$. arXiv:1811.00113.
  * [FKLPW] Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: compact post-quantum signatures from quaternions and isogenies, In: International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology – ASIACRYPT 2020 (2020), pp. 64–93.
  * [JFP] David Jao, Luca De Feo, and Jérôme Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), no. 3, pp. 209–247.
  * [LT] Oleg Lisovyy and Yuriy Tykhyy, Algebraic solutions of the sixth Painlevé equation, Journal of Geometry and Physics, Volume 85 (2014), pp. 124–163,
  * [M1] Andrey Markoff. Sur les formes quadratiques binaires indéfinies, Math. Ann. 15 (1879) 381–409.
  * [M2] Andrey Markoff. Sur les formes quadratiques binaires indéfinies, Math. Ann. 17 (1880) 379–399.
  * [MP] Chen Meiri, Doron Puder with an Appendix by Dan Carmon. The Markoff Group of Transformations in Prime and Composite Moduli. Duke Math J. 167 No. 14 (2018) pp. 2679–2720.
  * [PLQ] Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater. Full cryptanalysis of LPS and Morgenstern hash functions, Security and Cryptography for Networks 2008, pp. 263–277, Springer Berlin Heidelberg.
  * [RS] Michelle Rabideau and Ralf Schiffler. Continued fractions and orderings on the Markov Numbers. arXiv:1801.07155v2.
  * [S] Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer.
  * [TZ] Jean-Pierre Tillich and Gilles Zémor. Collisions for the LPS Expander Graph Hash Function, Advances in Cryptology - EUROCRYPT 2008, Lecture Notes in Computer Science, Vol 4965, pp. 254–269, Springer.
  * [Z] Don Zagier. Markoff numbers below a given bound, Mathematics of computation 39 No. 160 (1982) 709-723.