Unconditional foundations for supersingular isogeny-based cryptography

• URL: http://arxiv.org/abs/2502.17010v1
• Date: Mon, 24 Feb 2025 09:46:03 GMT
• Title: Unconditional foundations for supersingular isogeny-based cryptography
• Authors: Arthur Herlédan Le Merdy, Benjamin Wesolowski,
• Abstract summary: We prove that the supersingular isogeny problem (Isogeny) is equivalent to the worst ring problem (EndRing) and maximal order problem (MaxOrder)<n>For cryptographic applications, one requires computational problems to be hard on average for random instances.<n>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.
• Score: 5.01069065110753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we prove that the supersingular isogeny problem (Isogeny), endomorphism ring problem (EndRing) and maximal order problem (MaxOrder) are equivalent under probabilistic polynomial time reductions, unconditionally.Isogeny-based cryptography is founded on the presumed hardness of these problems, and their interconnection is at the heart of the design and analysis of cryptosystems like the SQIsign digital signature scheme. Previously known reductions relied on unproven assumptions such as the generalized Riemann hypothesis. In this work, we present unconditional reductions, and extend this network of equivalences to the problem of computing the lattice of all isogenies between two supersingular elliptic curves (HomModule).For cryptographic applications, one requires computational problems to be hard on average for random instances. It is well-known that if Isogeny is hard (in the worst case), then it is hard for random instances. We extend this result by proving that if any of the above-mentionned classical problems is hard in the worst case, then all of them are hard on average. In particular, if there exist hard instances of Isogeny, then all of Isogeny, EndRing, MaxOrder and HomModule are hard on average.

Related papers

• PromptCoT: Synthesizing Olympiad-level Problems for Mathematical Reasoning in Large Language Models [59.920971312822736]
  We introduce PromptCoT, a novel approach for automatically generating high-quality Olympiad-level math problems. The proposed method synthesizes complex problems based on mathematical concepts and the rationale behind problem construction. Our method is evaluated on standard benchmarks including GSM8K, MATH-500, and AIME2024, where it consistently outperforms existing problem generation methods.
  arXiv  Detail & Related papers  (2025-03-04T06:32:30Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  MathGAP generates problem statements and chain-of-thought reasoning traces according to specifications about their arithmetic proof structure.<n>Using MathGAP, we find that LLMs show a significant decrease in performance as proofs get deeper and wider.
  arXiv  Detail & Related papers  (2024-10-17T12:48:14Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• 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)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems [7.722592882475735]
  We consider the problem of recovering a complex vector $mathbfxin mathbbCn$ from $mangle A-imathbfx, mathbfxr_i=1m arbitrary. In general, not only is the the quadratic problem NP-hard to solve, but it may in fact be unidentifiable.
  arXiv  Detail & Related papers  (2020-02-04T00:35:09Z)

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.