The supersingular endomorphism ring problem given one endomorphism

• URL: http://arxiv.org/abs/2309.11912v2
• Date: Fri, 6 Oct 2023 06:32:26 GMT
• Title: The supersingular endomorphism ring problem given one endomorphism
• Authors: Arthur Herlédan Le Merdy, Benjamin Wesolowski,
• Abstract summary: 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.
• Score: 5.01069065110753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a supersingular elliptic curve E and a non-scalar endomorphism $\alpha$ of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[$\alpha$])^1/4 , and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions. Along the way, we prove that the Primitivisation problem can be solved in polynomial time (a problem previously believed to be hard), and we prove that the action of smooth ideals on oriented elliptic curves can be computed in polynomial time (previous results of this form required the ideal to be powersmooth, i.e., not divisible by any large prime power). Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results.

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)
• Emptiness Instanton in Quantum Polytropic Gas [49.1574468325115]
  The problem involves determining the probability of the spontaneous formation of an empty interval in the ground state of the gas. By solving the hydrodynamic equations in imaginary time, we derive the analytic form of the emptiness instanton. This solution is expressed as an integral representation analogous to those used for correlation functions in Conformal Field Theory.
  arXiv  Detail & Related papers  (2024-12-16T11:58:51Z)
• 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)
• Real-time dynamics of false vacuum decay [49.1574468325115]
  We investigate false vacuum decay of a relativistic scalar field in the metastable minimum of an asymmetric double-well potential. We employ the non-perturbative framework of the two-particle irreducible (2PI) quantum effective action at next-to-leading order in a large-N expansion.
  arXiv  Detail & Related papers  (2023-10-06T12:44:48Z)
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent [5.01069065110753]
  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.
  arXiv  Detail & Related papers  (2023-09-19T08:47:12Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Dynamical chaos in nonlinear Schr\"odinger models with subquadratic power nonlinearity [137.6408511310322]
  We deal with a class of nonlinear Schr"odinger lattices with random potential and subquadratic power nonlinearity. We show that the spreading process is subdiffusive and has complex microscopic organization. The limit of quadratic power nonlinearity is also discussed and shown to result in a delocalization border.
  arXiv  Detail & Related papers  (2023-01-20T16:45:36Z)
• A New Look at the $C^{0}$-formulation of the Strong Cosmic Censorship Conjecture [68.8204255655161]
  We argue that for generic black hole parameters as initial conditions for Einstein equations, the metric is $C0$-extendable to a larger Lorentzian manifold. We prove it violates the "complexity=volume" conjecture for a low-temperature hyperbolic AdS$_d+1$ black hole dual to a CFT living on a ($d-1$)-dimensional hyperboloid $H_d-1$.
  arXiv  Detail & Related papers  (2022-06-17T12:14:33Z)
• 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)
• Measuring dissimilarity with diffeomorphism invariance [94.02751799024684]
  We introduce DID, a pairwise dissimilarity measure applicable to a wide range of data spaces. We prove that DID enjoys properties which make it relevant for theoretical study and practical use.
  arXiv  Detail & Related papers  (2022-02-11T13:51:30Z)
• Complete ionization for a non-autonomous point interaction model in d = 2 [0.0]
  We consider the two dimensional Schr"odinger equation with time dependent delta potential. We prove global well-posedness of the associated Cauchy problem. We investigate the behavior of the survival probability of a bound state of the time-independent problem.
  arXiv  Detail & Related papers  (2021-08-14T15:30:13Z)
• Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
  A central problem in the theory of machine learning is whether it is possible to efficiently find a consistent hypothesis i.e. which has zero error. We show that the general idea of our algorithm can even be extended to the case of weakly convex hypotheses.
  arXiv  Detail & Related papers  (2021-05-10T23:00:02Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.