The supersingular Endomorphism Ring and One Endomorphism problems are equivalent

• URL: http://arxiv.org/abs/2309.10432v2
• Date: Mon, 16 Oct 2023 11:06:20 GMT
• Title: The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Authors: Aurel Page, Benjamin Wesolowski,
• Abstract summary: The endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves. We introduce a flexible framework for the study of isogeny graphs with additional information.
• Score: 5.01069065110753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The supersingular Endomorphism Ring problem is the following: given a supersingular elliptic curve, compute all of its endomorphisms. The presumed hardness of this problem is foundational for isogeny-based cryptography. The One Endomorphism problem only asks to find a single non-scalar endomorphism. We prove that these two problems are equivalent, under probabilistic polynomial time reductions. We prove a number of consequences. First, assuming the hardness of the endomorphism ring problem, the Charles--Goren--Lauter hash function is collision resistant, and the SQIsign identification protocol is sound. Second, the endomorphism ring problem is equivalent to the problem of computing arbitrary isogenies between supersingular elliptic curves, a result previously known only for isogenies of smooth degree. Third, there exists an unconditional probabilistic algorithm to solve the endomorphism ring problem in time O~(sqrt(p)), a result that previously required to assume the generalized Riemann hypothesis. To prove our main result, we introduce a flexible framework for the study of isogeny graphs with additional information. We prove a general and easy-to-use rapid mixing theorem. The proof of this result goes via an augmented Deuring correspondence and the Jacquet-Langlands correspondence.

Related papers

• Computing Isomorphisms between Products of Supersingular Elliptic Curves [0.9467360130705919]
  Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. We present methods for explicitly computing these isomorphisms in time, given the rings of the curves involved.
  arXiv  Detail & Related papers  (2025-03-27T14:26:31Z)
• Unconditional foundations for supersingular isogeny-based cryptography [5.01069065110753]
  We prove that the supersingular isogeny problem (Isogeny) is equivalent to the worst ring problem (EndRing) and maximal order problem (MaxOrder) For cryptographic applications, one requires computational problems to be hard on average for random instances. We extend this result to prove that if any of the above-mentionned classical problems is hard in the case, then all of them are hard on average.
  arXiv  Detail & Related papers  (2025-02-24T09:46:03Z)
• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings [0.0]
  We give a deterministic time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring.
  arXiv  Detail & Related papers  (2024-02-07T18:10:54Z)
• Causal Layering via Conditional Entropy [85.01590667411956]
  Causal discovery aims to recover information about an unobserved causal graph from the observable data it generates. We provide ways to recover layerings of a graph by accessing the data via a conditional entropy oracle.
  arXiv  Detail & Related papers  (2024-01-19T05:18:28Z)
• The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
  We prove that the endomorphism ring of E can be computed in classical time. We also prove that the action of smooth ideals on elliptic curves can be computed in time.
  arXiv  Detail & Related papers  (2023-09-21T09:22:43Z)
• On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups [5.10647201123061]
  We study the complexity of isomorphism problems for d-way arrays, or tensors, under natural actions by classical groups. For unitary groups, the preceding result implies that LOCC classification of tripartite quantum states is at least as difficult as LOCC classification of d-partite quantum states for any d.
  arXiv  Detail & Related papers  (2023-06-05T18:00:04Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Failing to hash into supersingular isogeny graphs [4.57147786707036]
  An important cryptographic open problem is to produce, without a trusted authority, concrete examples of "hard supersingular curves" We document a number of 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.
  arXiv  Detail & Related papers  (2022-04-30T02:56:47Z)
• Feature Cross Search via Submodular Optimization [58.15569071608769]
  We study feature cross search as a fundamental primitive in feature engineering. We show that there exists a simple greedy $(1-1/e)$-approximation algorithm for this problem.
  arXiv  Detail & Related papers  (2021-07-05T16:58:31Z)
• Relative stability toward diffeomorphisms in deep nets indicates performance [66.51503682738931]
  We show that stability toward diffeomorphisms does not strongly correlate to performance on benchmark data sets of images. We find that the stability toward diffeomorphisms relative to that of generic transformations $R_f$ correlates remarkably with the test error $epsilon_t$. For CIFAR10 and 15 known architectures, we find $epsilon_tapprox 0.2sqrtR_f$, suggesting that obtaining a small $R_f$ is important to achieve good performance.
  arXiv  Detail & Related papers  (2021-05-06T07:03:30Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  We show an average-case and noisy version of the well-known NP-hard graph isomorphism problem. For the correlated Erd"os-R'enyi model, we prove an impossibility result for partial recovery in the sparse regime. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise.
  arXiv  Detail & Related papers  (2021-02-04T15:26:48Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.