An official website of the United States government
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.
more »
« less
Failing to Hash Into Supersingular Isogeny Graphs
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.
more »
« less
- PAR ID:
- 10509672
- Publisher / Repository:
- Oxford University Press
- Date Published:
- Journal Name:
- The Computer Journal
- Volume:
- 67
- Issue:
- 8
- ISSN:
- 0010-4620
- Format(s):
- Medium: X Size: p. 2702-2719
- Size(s):
- p. 2702-2719
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Problems relating to the computation of isogenies between elliptic curves defined over finite fields have been studied for a long time. Isogenies on supersingular elliptic curves are a candidate for quantum-safe key exchange protocols because the best known classical and quantum algorithms for solving well-formed instances of the isogeny problem are exponential. We propose an implementation of supersingular isogeny Diffie-Hellman (SIDH) key exchange for complete Edwards curves. Our work is motivated by the use of Edwards curves to speed up many cryptographic protocols and improve security. Our work does not actually provide a faster implementation of SIDH, but the use of complete Edwards curves and their complete addition formulae provides security benefits against side-channel attacks. We provide run time complexity analysis and operation counts for the proposed key exchange based on Edwards curves along with comparisons to the Montgomery form.more » « less
-
Abstract The Hilbert class polynomial has as roots the j -invariants of elliptic curves whose endomorphism ring is a given imaginary quadratic order. It can be used to compute elliptic curves over finite fields with a prescribed number of points. Since its coefficients are typically rather large, there has been continued interest in finding alternative modular functions whose corresponding class polynomials are smaller. Best known are Weber’s functions, which reduce the size by a factor of 72 for a positive density subset of imaginary quadratic discriminants. On the other hand, Bröker and Stevenhagen showed that no modular function will ever do better than a factor of 100.83. We introduce a generalization of class polynomials, with reduction factors that are not limited by the Bröker–Stevenhagen bound. We provide examples matching Weber’s reduction factor. For an infinite family of discriminants, their reduction factors surpass those of all previously known modular functions by a factor at least 2.more » « less
-
Abstract Biopolymers, like chromatin, are often confined in small volumes. Confinement has a great effect on polymer conformations, including polymer entanglement. Polymer chains and other filamentous structures can be represented by polygonal curves in three-space. In this manuscript, we examine the topological complexity of polygonal chains in three-space and in confinement as a function of their length. We model polygonal chains by equilateral random walks in three-space and by uniform random walks (URWs) in confinement. For the topological characterization, we use the second Vassiliev measure. This is an integer topological invariant for polygons and a continuous functions over the real numbers, as a function of the chain coordinates for open polygonal chains. For URWs in confined space, we prove that the average value of the Vassiliev measure in the space of configurations increases as O ( n 2 ) with the length of the walks or polygons. We verify this result numerically and our numerical results also show that the mean value of the second Vassiliev measure of equilateral random walks in three-space increases as O ( n ). These results reveal the rate at which knotting of open curves and not simply entanglement are affected by confinement.more » « less
-
We introduce a special class of supersingular curves over Fp2 , characterized by the existence of non-integer endomorphisms of small degree. A number of properties of this set is proved. Most notably, we show that when this set partitions into subsets in such a way that curves within each subset have small-degree isogenies between them, but curves in distinct subsets have no small-degree isogenies between them. Despite this, we show that isogenies between these curves can be computed efficiently, giving a technique for computing isogenies between certain prescribed curves that cannot be reasonably connected by searching on ell-isogeny graphs.more » « less
