Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic
Lattice sieving in two dimensions has proven to be an indispensable practical aid in integer factorization and discrete log computations involving the number field sieve. The main contribution of this article is to show that a different method of lattice sieving in three dimensions will provide a si...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-11-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2020-0008 |
| _version_ | 1817991135066324992 |
|---|---|
| author | McGuire Gary Robinson Oisín |
| author_facet | McGuire Gary Robinson Oisín |
| author_sort | McGuire Gary |
| collection | DOAJ |
| description | Lattice sieving in two dimensions has proven to be an indispensable practical aid in integer factorization and discrete log computations involving the number field sieve. The main contribution of this article is to show that a different method of lattice sieving in three dimensions will provide a significant speedup in medium characteristic. Our method is to use the successive minima and shortest vectors of the lattice instead of transition vectors to iterate through lattice points. We showcase the new method by a record computation in a 133-bit subgroup of Fp6${{\mathbb{F}}_{{{p}^{6}}}}$, with p6 having 423 bits. Our overall timing is nearly 3 times faster than the previous record of a 132-bit subgroup in a 422-bit field. The approach generalizes to dimensions 4 or more, overcoming one key obstruction to the implementation of the tower number field sieve. |
| first_indexed | 2024-04-14T01:09:20Z |
| format | Article |
| id | doaj.art-6a606add87ce49308c28a3a7bd58de9f |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-04-14T01:09:20Z |
| publishDate | 2020-11-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-6a606add87ce49308c28a3a7bd58de9f2022-12-22T02:21:09ZengDe GruyterJournal of Mathematical Cryptology1862-29842020-11-0115122323610.1515/jmc-2020-0008jmc-2020-0008Lattice Sieving in Three Dimensions for Discrete Log in Medium CharacteristicMcGuire Gary0Robinson Oisín1UCD School of Mathematics and Statistics, University College Dublin, DublinIrelandUCD School of Mathematics and Statistics, University College Dublin, DublinIrelandLattice sieving in two dimensions has proven to be an indispensable practical aid in integer factorization and discrete log computations involving the number field sieve. The main contribution of this article is to show that a different method of lattice sieving in three dimensions will provide a significant speedup in medium characteristic. Our method is to use the successive minima and shortest vectors of the lattice instead of transition vectors to iterate through lattice points. We showcase the new method by a record computation in a 133-bit subgroup of Fp6${{\mathbb{F}}_{{{p}^{6}}}}$, with p6 having 423 bits. Our overall timing is nearly 3 times faster than the previous record of a 132-bit subgroup in a 422-bit field. The approach generalizes to dimensions 4 or more, overcoming one key obstruction to the implementation of the tower number field sieve.https://doi.org/10.1515/jmc-2020-0008number field sievediscrete log11y05 |
| spellingShingle | McGuire Gary Robinson Oisín Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic Journal of Mathematical Cryptology number field sieve discrete log 11y05 |
| title | Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic |
| title_full | Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic |
| title_fullStr | Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic |
| title_full_unstemmed | Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic |
| title_short | Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic |
| title_sort | lattice sieving in three dimensions for discrete log in medium characteristic |
| topic | number field sieve discrete log 11y05 |
| url | https://doi.org/10.1515/jmc-2020-0008 |
| work_keys_str_mv | AT mcguiregary latticesievinginthreedimensionsfordiscreteloginmediumcharacteristic AT robinsonoisin latticesievinginthreedimensionsfordiscreteloginmediumcharacteristic |