TL;DR
This paper explores the relationship between the well-known Elliptic Curve Discrete Logarithm Problem (ECDLP) and several newly defined "hard problems" related to elliptic divisibility sequences (EDS). The authors demonstrate that solving these EDS-related problems in sub-exponential time is equivalent to solving the ECDLP in sub-exponential time, thereby strengthening the theoretical foundations of ECDLP's security.
What Problem Does This Paper Address?
The security of modern cryptography, particularly in elliptic curve cryptography (ECC), relies on the assumption that the Elliptic Curve Discrete Logarithm Problem (ECDLP) is computationally hard. The ECDLP asks to find an integer $k$ given two points $P$ and $Q$ on an elliptic curve such that $Q = [k]P$. While the hardness of ECDLP is a cornerstone of ECC, understanding its theoretical underpinnings and exploring equivalent hard problems is crucial for a deeper understanding of its security. This paper addresses this by investigating the connection between ECDLP and problems involving elliptic divisibility sequences (EDS), which are recurrence relations defined on elliptic curves. The authors aim to establish equivalences between these problems, showing that advancements in solving EDS-related problems would directly impact the security of ECDLP.
Methods
The paper introduces and defines three new hard problems related to elliptic divisibility sequences:
- EDS Association: Given an elliptic curve and points $P, Q$, determine a specific term in the EDS sequence $W_{E,P}(k)$ related to $Q = [k]P$.
- EDS Residue: Determine the quadratic residuosity of an EDS term $W_{E,P}(k)$.
- Width $s$ EDS Discrete Log: Given a segment of an EDS, determine the index $k$.
The core of the paper involves proving equivalences between these EDS problems and ECDLP. This is achieved through:
- Relating EDS to Elliptic Nets: The paper builds upon existing work to define elliptic nets, which are generalizations of EDS, and establishes how elliptic curves and points give rise to these nets.
- Mathematical Proofs of Equivalence: The authors provide rigorous mathematical proofs demonstrating that if any of the defined EDS problems can be solved in sub-exponential time, then ECDLP can also be solved in sub-exponential time, and vice-versa. This is a key contribution, establishing a strong theoretical link.
- Leveraging Existing Algorithms: The paper references and builds upon existing algorithms for computing EDS terms and for solving discrete logarithms in finite fields (F* DLP), such as those by Shipsey, and connects them to the newly defined problems.
- Analysis of Attacks: The paper discusses how the MOV and Frey-Rück attacks on ECDLP relate to EDS and explains their limitations from an EDS perspective.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Equivalence of Hardness: The most significant insight is the formal proof that solving certain problems related to elliptic divisibility sequences is computationally equivalent to solving the ECDLP. This means that any sub-exponential algorithm for these EDS problems would break ECDLP, and vice-versa.
- EDS as a Cryptographic Primitive: The paper suggests that EDS, and the problems associated with them, could potentially serve as building blocks or related primitives for cryptographic constructions, offering new avenues for analysis.
- Quadratic Residues for ECDLP: A novel attack vector is proposed by analyzing the quadratic residuosity of EDS terms. This suggests that determining even partial information about EDS terms (like their quadratic residue status) can be leveraged to solve ECDLP.
- Connection to Existing Attacks: The paper clarifies the relationship between EDS and established ECDLP attacks like MOV and Frey-Rück, providing a more unified understanding of these cryptographic vulnerabilities.
- Perfectly Periodic Sequences: The concept of "perfectly periodic" EDS is introduced and analyzed, showing how it simplifies certain computations and relates to the underlying elliptic curve structure.
Key Results
- Theorem 1: Establishes the equivalence in sub-exponential time solvability between ECDLP and three specific EDS-related problems (EDS Association, EDS Residue, and Width 3 EDS Discrete Log for perfectly periodic sequences).
- Proposition 1 & 3: Demonstrate that knowledge of specific products of EDS terms (or their quadratic residuosity) can lead to solving ECDLP in sub-exponential time.
- Corollary 2: Shows that determining the quadratic residuosity of an EDS term can be used to solve ECDLP.
- Theorems 7, 8, 9, 10: Provide algorithms and complexity bounds for computing EDS terms and solving related discrete logarithm problems, often in terms of $O((\log q)^c)$ for some constant $c$.
Limitations and Future Work
- Sub-exponential vs. Polynomial Time: While the paper establishes equivalences in sub-exponential time, it does not claim to break ECDLP in polynomial time. The focus is on theoretical hardness and the relationships between problems.
- Practicality of EDS Attacks: The paper discusses theoretical connections and potential attack vectors. The practical efficiency and applicability of these EDS-based attacks in real-world scenarios would require further investigation.
- Quadratic Residue Attack Limitations: Proposition 3 and Corollary 2 highlight that the quadratic residue attack works best when certain conditions are met (e.g., order of $P$ is relatively prime to $q-1$, and $(P)$ is a quadratic non-residue). The paper acknowledges that alternative strategies might be needed when these conditions don't hold.
- Future Work: The paper implicitly suggests further research into exploring other variations of EDS-related problems and their connections to ECDLP, as well as investigating the practical implications of these theoretical equivalences for cryptographic security. The authors also mention that the relationship with MOV and Frey-Rück attacks is discussed in Section 5, indicating potential for further exploration in that area.
Summary updated