×

zbMATH — the first resource for mathematics

Collecting relations for the number field sieve in \(\text{GF}(p^6)\). (English) Zbl 1391.11161
Summary: In order to assess the security of cryptosystems based on the discrete logarithm problem in non-prime finite fields, as are the torus-based or pairing-based ones, we investigate thoroughly the case in \(\mathbb{F}_{p^6}\) with the number field sieve. We provide new insights, improvements, and comparisons between different methods to select polynomials intended for a sieve in dimension 3 using a special-\(\mathfrak{q}\) strategy. We also take into account the Galois action to increase the relation productivity of the sieving phase. To validate our results, we ran several experiments and real computations for various polynomial selection methods and field sizes with our publicly available implementation of the sieve in dimension 3, with special-\(\mathfrak{q}\) and various enumeration strategies.

MSC:
11Y16 Number-theoretic algorithms; complexity
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y40 Algebraic number theory computations
11-04 Software, source code, etc. for problems pertaining to number theory
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1090/S0025-5718-06-01870-9 · Zbl 1183.11079 · doi:10.1090/S0025-5718-06-01870-9
[2] DOI: 10.1007/3-540-44598-6_1 · doi:10.1007/3-540-44598-6_1
[3] Zajac, Tatra Mt. Math. Publ. 45 pp 161– (2010)
[4] DOI: 10.1098/rsta.1993.0139 · Zbl 0795.11063 · doi:10.1098/rsta.1993.0139
[5] DOI: 10.1007/11818175_19 · Zbl 1161.11417 · doi:10.1007/11818175_19
[6] DOI: 10.1090/S0025-5718-02-01482-5 · Zbl 1099.11074 · doi:10.1090/S0025-5718-02-01482-5
[7] Coppersmith, J. Cryptology 6 pp 169– (1993)
[8] Hayasaka, Number theory and cryptography pp 108– (2013)
[9] Commeine, PKC 2006 pp 174– (2006)
[10] Hanrot, Coding and Cryptology – Third International Workshop, IWCC 2011 pp 159– (2011)
[11] DOI: 10.1007/978-3-662-02945-9 · doi:10.1007/978-3-662-02945-9
[12] DOI: 10.1007/978-3-662-48797-6_7 · Zbl 1396.11141 · doi:10.1007/978-3-662-48797-6_7
[13] DOI: 10.1112/S1461157014000369 · Zbl 1369.11096 · doi:10.1112/S1461157014000369
[14] DOI: 10.1137/0406010 · Zbl 0772.11046 · doi:10.1137/0406010
[15] González, Math. Geosci. pp 42– (2010)
[16] DOI: 10.1007/s00145-009-9048-z · Zbl 1181.94094 · doi:10.1007/s00145-009-9048-z
[17] DOI: 10.1007/978-3-662-48800-3_2 · Zbl 1375.94096 · doi:10.1007/978-3-662-48800-3_2
[18] DOI: 10.1007/978-3-642-55220-5_1 · Zbl 1326.11080 · doi:10.1007/978-3-642-55220-5_1
[19] Barbulescu, EUROCRYPT 2015 pp 129– (2015)
[20] DOI: 10.1090/S0025-5718-2015-02926-3 · Zbl 1378.11104 · doi:10.1090/S0025-5718-2015-02926-3
[21] DOI: 10.1016/j.jalgor.2004.11.004 · Zbl 1207.11124 · doi:10.1016/j.jalgor.2004.11.004
[22] DOI: 10.1007/978-3-662-49890-3_17 · Zbl 1385.11075 · doi:10.1007/978-3-662-49890-3_17
[23] DOI: 10.1007/978-3-540-45146-4_21 · doi:10.1007/978-3-540-45146-4_21
[24] DOI: 10.1007/BFb0091538 · doi:10.1007/BFb0091538
[25] Pierrot, EUROCRYPT 2015 pp 156– (2015)
[26] Joux, Pairing 2013 pp 45– (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.