Related papers: Minors solve the elliptic curve discrete logarithm problem

Minors solve the elliptic curve discrete logarithm problem

URL: http://arxiv.org/abs/2310.04132v1
Date: Fri, 6 Oct 2023 10:05:25 GMT
Title: Minors solve the elliptic curve discrete logarithm problem
Authors: Ansari Abdullah, Ayan Mahalanobis,
Abstract summary: This paper explores ways to solve the elliptic curve discrete logarithm problem. It follows our earlier work, where we tried to solve this problem by finding a zero minor in a matrix over the same finite field on which the elliptic curve is defined.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The elliptic curve discrete logarithm problem is of fundamental importance in public-key cryptography. It is in use for a long time. Moreover, it is an interesting challenge in computational mathematics. Its solution is supposed to provide interesting research directions. In this paper, we explore ways to solve the elliptic curve discrete logarithm problem. Our results are mostly computational. However, it seems, the methods that we develop and directions that we pursue can provide a potent attack on this problem. This work follows our earlier work, where we tried to solve this problem by finding a zero minor in a matrix over the same finite field on which the elliptic curve is defined. This paper is self-contained.

Related papers

Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field [8.950235011733273]
We propose the double index calculus algorithm to solve the discrete logarithm problem in a finite prime field. Our algorithm is faster than the index calculus algorithm. Our algorithm is more general than the index calculus algorithm.
arXiv Detail & Related papers (2024-09-13T12:41:32Z)
Elliptic Curves in Continuous-Variable Quantum Systems [0.0]
We give an algorithm for computing elliptic curve group addition using a single continuous-variable mode. This result could lead to improvements in the efficiency of elliptic curve discrete logarithms using a quantum device.
arXiv Detail & Related papers (2024-01-21T20:04:40Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
arXiv Detail & Related papers (2023-05-22T17:43:34Z)
Private Isotonic Regression [54.32252900997422]
We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
arXiv Detail & Related papers (2022-10-27T05:08:07Z)
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)
Damped Online Newton Step for Portfolio Selection [96.0297968061824]
We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth. Existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale with the total number of rounds. We present the first practical online portfolio selection algorithm with a logarithmic regret and whose per-round time and space complexities depend only logarithmically on the horizon.
arXiv Detail & Related papers (2022-02-15T17:01:55Z)
A Homotopy Algorithm for Optimal Transport [0.0]
The optimal transport problem has many applications in machine learning, physics, biology, economics, etc. Here, we propose a homotopy algorithm that first transforms the problem into an easy form, by changing the target distribution. It then transforms the problem back to the original form through a series of iterations, tracing a path of solutions until it finds the optimal solution for the original problem.
arXiv Detail & Related papers (2021-12-13T16:17:51Z)
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)
Mean Field Approximation for solving QUBO problems [0.0]
We show that the statistical physics approach and the quantum mechanical approach in the mean field annealing give the same result. Our methods consist of a set of simple gradient-based minimizations with continuous variables, thus easy to simulate.
arXiv Detail & Related papers (2021-06-06T20:35:28Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
arXiv Detail & Related papers (2020-06-24T11:37:33Z)
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.