Complexity bounds on Semaev’s naive index calculus method for ECDLP
Since Semaev introduced summation polynomials in 2004, a number of studies have been devoted to improving the index calculus method for solving the elliptic curve discrete logarithm problem (ECDLP) with better complexity than generic methods such as Pollard’s rho method and the baby-step and giant-s...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-10-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2019-0029 |
| _version_ | 1828282375561281536 |
|---|---|
| author | Yokoyama Kazuhiro Yasuda Masaya Takahashi Yasushi Kogure Jun |
| author_facet | Yokoyama Kazuhiro Yasuda Masaya Takahashi Yasushi Kogure Jun |
| author_sort | Yokoyama Kazuhiro |
| collection | DOAJ |
| description | Since Semaev introduced summation polynomials in 2004, a number of studies have been devoted to improving the index calculus method for solving the elliptic curve discrete logarithm problem (ECDLP) with better complexity than generic methods such as Pollard’s rho method and the baby-step and giant-step method (BSGS). In this paper, we provide a deep analysis of Gröbner basis computation for solving polynomial systems appearing in the point decomposition problem (PDP) in Semaev’s naive index calculus method. Our analysis relies on linear algebra under simple statistical assumptions on summation polynomials. We show that the ideal derived from PDP has a special structure and Gröbner basis computation for the ideal is regarded as an extension of the extended Euclidean algorithm. This enables us to obtain a lower bound on the cost of Gröbner basis computation. With the lower bound, we prove that the naive index calculus method cannot be more efficient than generic methods. |
| first_indexed | 2024-04-13T08:29:19Z |
| format | Article |
| id | doaj.art-bb64b7a98fd2462c84a20ffe0d32dd6b |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-13T08:29:19Z |
| publishDate | 2020-10-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-bb64b7a98fd2462c84a20ffe0d32dd6b2022-12-22T02:54:20ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842020-10-0114146048510.1515/jmc-2019-0029jmc-2019-0029Complexity bounds on Semaev’s naive index calculus method for ECDLPYokoyama Kazuhiro0Yasuda Masaya1Takahashi Yasushi2Kogure Jun3Rikkyo University, Tokyo, JapanRikkyo University, Tokyo, JapanFUJITSU Laboratories LTD., Kawasaki, JapanFUJITSU Laboratories LTD., Kawasaki, JapanSince Semaev introduced summation polynomials in 2004, a number of studies have been devoted to improving the index calculus method for solving the elliptic curve discrete logarithm problem (ECDLP) with better complexity than generic methods such as Pollard’s rho method and the baby-step and giant-step method (BSGS). In this paper, we provide a deep analysis of Gröbner basis computation for solving polynomial systems appearing in the point decomposition problem (PDP) in Semaev’s naive index calculus method. Our analysis relies on linear algebra under simple statistical assumptions on summation polynomials. We show that the ideal derived from PDP has a special structure and Gröbner basis computation for the ideal is regarded as an extension of the extended Euclidean algorithm. This enables us to obtain a lower bound on the cost of Gröbner basis computation. With the lower bound, we prove that the naive index calculus method cannot be more efficient than generic methods.https://doi.org/10.1515/jmc-2019-0029ecdlpsummation polynomialsindex calculus methodsgröbner basis computationfall degreesprimary 94a60secondary 14g50 |
| spellingShingle | Yokoyama Kazuhiro Yasuda Masaya Takahashi Yasushi Kogure Jun Complexity bounds on Semaev’s naive index calculus method for ECDLP Journal of Mathematical Cryptology ecdlp summation polynomials index calculus methods gröbner basis computation fall degrees primary 94a60 secondary 14g50 |
| title | Complexity bounds on Semaev’s naive index calculus method for ECDLP |
| title_full | Complexity bounds on Semaev’s naive index calculus method for ECDLP |
| title_fullStr | Complexity bounds on Semaev’s naive index calculus method for ECDLP |
| title_full_unstemmed | Complexity bounds on Semaev’s naive index calculus method for ECDLP |
| title_short | Complexity bounds on Semaev’s naive index calculus method for ECDLP |
| title_sort | complexity bounds on semaev s naive index calculus method for ecdlp |
| topic | ecdlp summation polynomials index calculus methods gröbner basis computation fall degrees primary 94a60 secondary 14g50 |
| url | https://doi.org/10.1515/jmc-2019-0029 |
| work_keys_str_mv | AT yokoyamakazuhiro complexityboundsonsemaevsnaiveindexcalculusmethodforecdlp AT yasudamasaya complexityboundsonsemaevsnaiveindexcalculusmethodforecdlp AT takahashiyasushi complexityboundsonsemaevsnaiveindexcalculusmethodforecdlp AT kogurejun complexityboundsonsemaevsnaiveindexcalculusmethodforecdlp |