Search for: All records

Abstract An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of ‘hard supersingular curves’ that is equations for supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. A related open problem is to produce a hash function to the vertices of the supersingular $$\ell $$-isogeny graph, which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hope that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd’s of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces, and applying Kummer surfaces and (v) using quantum random walks. 

Abstract In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small degree endomorphism enables polynomial-time path-finding and endomorphism ring computation (in: Love and Boneh, ANTS XIV-Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of Open Book Ser. Math. Sci. Publ., Berkeley, 2020). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (in: Wesolowski, Advances in cryptology-EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science. Springer, Cham, 2022), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don’t assume the knowledge of the primitive order associated with the endomorphism. 

In a primitive integral Apollonian circle packing, the curvatures that appear must fall into one of six or eight residue classes modulo 24. The local-global conjecture states that every sufficiently large integer in one of these residue classes appears as a curvature in the packing. We prove that this conjecture is false for many packings, by proving that certain quadratic and quartic families are missed. The new obstructions are a property of the thin Apollonian group (and not its Zariski closure), and are a result of quadratic and quartic reciprocity, reminiscent of a Brauer-Manin obstruction. Based on computational evidence, we formulate a new conjecture. 

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $$n$$, where $$n$$ is the integer whose factorization is sought. The algorithm has subexponential runtime $$\exp(O(\sqrt{\log n \log \log n}))$$ (or $$\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus. 

Abstract A circle of curvature $$n\in \mathbb{Z}^+$$ is a part of finitely many primitive integral Apollonian circle packings. Each such packing has a circle of minimal curvature $$-c\leq 0$$, and we study the distribution of $c/n$ across all primitive integral packings containing a circle of curvature $$n$$. As $$n\rightarrow \infty $$, the distribution is shown to tend towards a picture we name the Apollonian staircase. A consequence of the staircase is that if we choose a random circle packing containing a circle $$C$$ of curvature $$n$$, then the probability that $$C$$ is tangent to the outermost circle tends towards $$3/\pi $$. These results are found by using positive semidefinite quadratic forms to make $$\mathbb{P}^1(\mathbb{C})$$ a parameter space for (not necessarily integral) circle packings. Finally, we examine an aspect of the integral theory known as spikes. When $$n$$ is prime, the distribution of $c/n$ is extremely smooth, whereas when $$n$$ is composite, there are certain spikes that correspond to prime divisors of $$n$$ that are at most $$\sqrt{n}$$. 

A practical algorithm to compute the fundamental domain of an arithmetic Fuchsian group was given by Voight, and implemented in Magma. It was later expanded by Page to the case of arithmetic Kleinian groups. We combine and improve on parts of both algorithms to produce a more efficient algorithm for arithmetic Fuchsian groups. This algorithm is implemented in PARI/GP, and we demonstrate the improvements by comparing running times versus the live Magma implementation.