Article Contents

2018, Volume 12, Issue 4: 741-759. Doi: 10.3934/amc.2018044

This issue Previous Article A class of skew-cyclic codes over $\mathbb{Z}_4+u\mathbb{Z}_4$ with derivation Next Article Higher weights and near-MDR codes over chain rings

Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields

1.
Computer Science Department, CINVESTAV-IPN, Mexico
2.
Centro de Investigación en Computación, Instituto Politécnico Nacional, Mexico
3.
Department of Combinatorics & Optimization, University of Waterloo, Canada

Received: November 2017

Published: November 2018

Abstract / Introduction Full Text(HTML) Figure(0) / Table(8) Related Papers Cited by

Abstract

Since 2013 there have been several developments in algorithms for computing discrete logarithms in small-characteristic finite fields, culminating in a quasi-polynomial algorithm. In this paper, we report on our successful computation of discrete logarithms in the cryptographically-interesting characteristic-three finite field $\mathbb{F}_{3^{6.509}}$ using these new algorithms; prior to 2013, it was believed that this field enjoyed a security level of 128 bits. We also show that a recent idea of Guillevic can be used to compute discrete logarithms in the cryptographically-interesting finite field $\mathbb{F}_{3^{6.709}}$ using essentially the same resources as we expended on the $\mathbb{F}_{3^{6.509}}$ computation. Finally, we argue that discrete logarithms in the finite field $\mathbb{F}_{3^{6.1429}}$ can feasibly be computed today; this is significant because this cryptographically-interesting field was previously believed to enjoy a security level of 192 bits.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 11Y16.

Citation:

Full Text(HTML)

Table 1. CPU times of each stage of the computation of discrete logarithms in $\mathbb{F}_{3^{6 \cdot 509}}$

Computation stage	CPU time (years)	CPU frequency (GHz)
Finding logarithms of quadratic polynomials
Relation generation	$0.0003$	3.20
Linear algebra	$0.49$	2.40
Finding logarithms of cubics
Relation generation	$0.14$	3.20
Linear algebra	$43.28$	2.60
Finding logarithms of quartics (29 families)
Relation generation	$4.01$	2.60
Linear algebra	$94.70$	2.60
Descent
Continued-fractions (508 to 40)	$51.00$	2.87
Classical (40 to 21)	$9.85$	2.66
Classical (21 to 15)	$10.10$	2.66
Small degree (15 to 4)	$6.18$	3.00
Total CPU time (years)	$219.75$

| Show Table

DownLoad: CSV

Table 4. Number of polynomials of each degree in the interval $[5, 15]$ obtained after the continued-fractions and classical descents. The total number of polynomials is 1409

Degree	5	6	7	8	9	10	11	12	13	14	15
Number of polynomials	101	107	94	98	92	116	137	123	155	173	213

| Show Table

DownLoad: CSV

Table 2. Expected number of irreducible quartics resulting from all the Gröbner bases and zigzag descent steps for each degree in $[5, 15]$

Degree	5	6	7	8	9	10	11	12	13	14	15
Number of degree-4 polynomials	$2^{14.18}$	$2^{14.26}$	$2^{21.27}$	$2^{16.13}$	$2^{22.11}$	$2^{23.88}$	$2^{28.54}$	$2^{23.97}$	$2^{28.74}$	$2^{24.88}$	$2^{30.45}$

| Show Table

DownLoad: CSV

Table 3. For every family from $\mathcal{B}_3$, $\mathcal{B}_{4, u^i}$, $i \in [0, 28]$, the inverse of the probability for a random irreducible quartic to descend based on that family

$\mathcal{B}_3\;\;2^{0.829}$	$\mathcal{B}_{4, u^0}\;\;2^{2.102}$	$\mathcal{B}_{4, u^1}\;\;2^{3.374}$	$\mathcal{B}_{4, u^2}\;\;2^{4.646}$	$\mathcal{B}_{4, u^3}\;\;2^{5.918}$
$\mathcal{B}_{4, u^4}\;\;2^{7.191}$	$\mathcal{B}_{4, u^5}\;\;2^{8.463}$	$\mathcal{B}_{4, u^6}\;\;2^{9.735}$	$\mathcal{B}_{4, u^7}\;\;2^{11.008}$	$\mathcal{B}_{4, u^8}\;\;2^{12.280}$
$\mathcal{B}_{4, u^9}\;\;2^{13.552}$	$\mathcal{B}_{4, u^{10}}\;\;2^{14.825}$	$\mathcal{B}_{4, u^{11}}\;\;2^{16.097}$	$\mathcal{B}_{4, u^{12}}\;\;2^{17.369}$	$\mathcal{B}_{4, u^{13}}\;\;2^{18.641}$
$\mathcal{B}_{4, u^{14}}\;\;2^{19.914}$	$\mathcal{B}_{4, u^{15}}\;\;2^{21.186}$	$\mathcal{B}_{4, u^{16}}\;\;2^{22.458}$	$\mathcal{B}_{4, u^{17}}\;\;2^{23.731}$	$\mathcal{B}_{4, u^{18}}\;\;2^{25.003}$
$\mathcal{B}_{4, u^{19}}\;\;2^{26.275}$	$\mathcal{B}_{4, u^{20}}\;\;2^{27.547}$	$\mathcal{B}_{4, u^{21}}\;\;2^{28.820}$	$\mathcal{B}_{4, u^{22}}\;\;2^{30.092}$	$\mathcal{B}_{4, u^{23}}\;\;2^{31.364}$
$\mathcal{B}_{4, u^{24}}\;\;2^{32.637}$	$\mathcal{B}_{4, u^{25}}\;\;2^{33.909}$	$\mathcal{B}_{4, u^{26}}\;\;2^{35.181}$	$\mathcal{B}_{4, u^{27}}\;\;2^{36.454}$	$\mathcal{B}_{4, u^{28}}\;\;2^{37.726}$

| Show Table

DownLoad: CSV

Table 5. Total and average CPU times in seconds to obtain the logarithms of all the polynomials of degrees in $[5, 15]$ that resulted from the continued-fractions and classical descents. The times assume that an Intel Xeon E5-2658 v2 2.40 GHz machine with 256 gigabytes of RAM is used

Degree	5	6	7	8	9	10	11	12	13	14	15
Total	$2^{10.21}$	$2^{10.29}$	$2^{17.30}$	$2^{12.16}$	$2^{18.14}$	$2^{19.92}$	$2^{24.57}$	$2^{20.00}$	$2^{24.78}$	$2^{20.91}$	$2^{26.48}$
Average	$2^{3.55}$	$2^{3.55}$	$2^{10.69}$	$2^{5.64}$	$2^{11.62}$	$2^{13.06}$	$2^{17.47}$	$2^{13.06}$	$2^{17.50}$	$2^{13.48}$	$2^{18.75}$

| Show Table

DownLoad: CSV

Table 6. Estimated costs of the main steps for computing discrete logarithms in $\mathbb{F}_{3^{6.1429}}$

Finding logarithms of polynomials of degree $\leq 4$
Degrees 1 and 2	$2^{50.7} M_q$
Degree 3	$2^{56.9} M_q$
Degree 4 (36 families)	$2^{56.3} M_q$
Descent
Guillevic (1428 to 71)	$2^{62.4} M_q$
Classical (71 to 32)	$2^{61.8} M_q$
Classical (31 to $\{1, \ldots, 16, 18, 20, 22, 24, 28, 32\}$)	$2^{59.2}M_q$
Small degree ($\{5, \ldots, 16, 18, 20, 22, 24, 28, 32\}$ to 4)	$2^{60.0}M_q$
Total cost	$2^{63.4} M_q$

| Show Table

DownLoad: CSV

Table 7. $M_q$ costs of performing all the $D$-to-4 descents for each $D \in S$

$D$	5	6	7	8	9	10	11	12	13
$e_D$	73	68	65	63	63	63	64	65	67
$\log_2(\mbox{cost})$	36.7	36.6	43.7	38.6	44.6	46.0	50.5	46.1	50.6
$D$	14	15	16	18	20	22	24	28	32
$e_D$	69	72	75	83	92	103	117	151	200
$\log_2(\mbox{cost})$	46.6	51.9	48.4	54.5	56.1	56.4	56.4	57.2	59.3

| Show Table

DownLoad: CSV

Table 8. Estimated calendar time for computing a discrete logarithm in $\mathbb{F}_{3^{6.1429}}$ using machines ${\mathcal{A}}$ and ${\mathcal{B}}$

Computation	# cores	# days
Degree-3 logarithms	5824	2
Degree-4 logarithms	9000	1
Guillevic descent	9000	59
First classical descent	9000	39
Second classical descent	9000	7
Small degree descent	1500	65
Total time		173

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	ABACUS Supercomputer - Cinvestav, http://www.abacus.cinvestav.mx/.
	G. Adj, Logaritmo discreto en campos finitos de característica pequeña: atacando la criptografía basada en emparejamientos de Tipo 1, Ph.D. thesis, CINVESTAV-IPN, 2016. Available at http://www.cs.cinvestav.mx/TesisGraduados/2016/TesisGoraAdj.pdf.
	G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 509}}$ for discrete logarithm cryptography, in: Pairing-Based Cryptography - Pairing 2013, LNCS, 8365 (2014), 20-44. doi: 10.1007/978-3-319-04873-4_2.
	G. Adj , A. Menezes , T. Oliveira and F. Rodríguez-Henríquez , Weakness of $\mathbb{F}_{3^{6 · 1429}}$ and $\mathbb{F}_{2^{4 · 3041}}$ for discrete logarithm cryptography, Finite Fields and Their Applications, 32 (2015) , 148-170. doi: 10.1016/j.ffa.2014.10.009.
	G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Computing discrete logarithms in $\mathbb{F}_{3^{6 · 137}}$ and $\mathbb{F}_{3^{6 · 163}}$ using Magma, in: WAIFI 2014, LNCS, 9061 (2015), 3-22. doi: 10.1007/978-3-319-16277-5_1.
	R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic: Improvements over FFS in small to medium characteristic, in: Advances in Cryptology - EUROCRYPT 2014, LNCS, 8441 (2014), 1-16. doi: 10.1007/978-3-642-55220-5_1.
	P. Barreto , S. Galbraith , C. ÓhÉigeartaigh and M. Scott , Efficient pairing computation on supersingular abelian varieties, Designs, Codes and Cryptography, 42 (2007) , 239-271. doi: 10.1007/s10623-006-9033-6.
	P. Barreto, H. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems, in: Advances in Cryptology - CRYPTO 2002, LNCS, 2442 (2002), 354-368. doi: 10.1007/3-540-45708-9_23.
	I. Blake , R. Fuji-Hara , R. Mullin and S. Vanstone , Computing logarithms in finite fields of characteristic two, SIAM Journal on Algebraic and Discrete Methods, 5 (1984) , 276-285. doi: 10.1137/0605029.
	D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology - CRYPTO 2001, LNCS, 2139 (2001), 213-229. doi: 10.1007/3-540-44647-8_13.
	D. Boneh , B. Lynn and H. Shacham , Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004) , 297-319. doi: 10.1007/s00145-004-0314-9.
	I. Canales-Martínez, Implementación eficiente de prueba de suavidad para polinomios, Tesis de Maestría, CINVESTAV-IPN, 2015. Available at http://delta.cs.cinvestav.mx/~francisco/Thesis_IAC.pdf.
	D. Coppersmith , Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984) , 587-594. doi: 10.1109/TIT.1984.1056941.
	The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/.
	J. Faugère , A new efficient algorithm for computing Gröbner bases ($F_4$), Journal of Pure and Applied Algebra, 139 (1999) , 61-88. doi: 10.1016/S0022-4049(99)00005-5.
	G. Frey and H. Rück , A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62 (1994) , 865-874. doi: 10.2307/2153546.
	S. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology - ASIACRYPT 2001, LNCS 2248 (2001), 495-513. doi: 10.1007/3-540-45682-1_29.
	S. Galbraith, K. Harrison and D. Soldera, Implementing the Tate pairing, in: Algorithmic Number Theory - ANTS 2002, LNCS, 2369 (2002), 324-337. doi: 10.1007/3-540-45455-1_26.
	F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in $\mathbb{F}_{2^{1971}}$ , in: Advances in Cryptology - CRYPTO 2013, LNCS, 8043 (2013), 109-128. doi: 10.1007/978-3-642-40084-1_7.
	F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, Solving a 6120-bit DLP on a desktop computer, in: Selected Areas in Cryptography - SAC 2014, LNC, S 8282 (2014), 136-152.
	D. Gordon , Discrete logarithms in $GF(p)$ using the number field sieve, SIAM Journal on Discrete Mathematics, 6 (1993) , 124-138. doi: 10.1137/0406010.
	R. Granger, T. Kleinjung and J. Zumbrägel, Breaking `128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$ and $\mathbb{F}_{2^{12 · 367}}$) , in: Advances in Cryptology - CRYPTO 2014, Part II, LNCS, 8617 (2014), 126-145. doi: 10.1007/978-3-662-44381-1_8.
	R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$ and $\mathbb{F}_{2^{12 · 367}}$) , Cryptology ePrint Archive: Report 2014/119, http://eprint.iacr.org/2014/119.
	R. Granger , T. Kleinjung and J. Zumbrägel , On the discrete logarithm problem in finite fields of fixed characteristic, Transactions of the AMS, 370 (2018) , 3129-3145. doi: 10.1090/tran/7027.
	A. Guillevic, Faster individual discrete logarithms with the QPA and NFS variants, Cryptology ePrint Archive: Report 2016/684, https://eprint.iacr.org/2016/684.
	A. Joux, A new index calculus algorithm with complexity $L(1/4 + o(1))$ in very small characteristic, in: Selected Areas in Cryptography - SAC 2013, LNCS, 8282 (2014), 355-379. doi: 10.1007/978-3-662-43414-7_18.
	A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology - EUROCRYPT 2006, LNCS, 4004 (2006), 254-270. doi: 10.1007/11761679_16.
	A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology - ASIACRYPT 2014, LNCS, 8873 (2014), 378-397. doi: 10.1007/978-3-662-45611-8_20.
	A. Joux and C. Pierrot , Technical history of discrete logarithms in small characteristic finite fields, Designs, Codes and Cryptography, 78 (2016) , 73-85. doi: 10.1007/s10623-015-0147-6.
	A. Knopfmacher and J. Knopfmacher , Counting irreducible factors of polynomials over a finite fields, Discrete Mathematics, 112 (1993) , 103-118. doi: 10.1016/0012-365X(93)90227-K.
	A. Lenstra, Unbelievable security: Matching AES security using public key systems, in: Advances in Cryptology - ASIACRYPT 2001, LNCS, 2248 (2001), 67-86. doi: 10.1007/3-540-45682-1_5.
	Magma v2.19-7, http://magma.maths.usyd.edu.au/magma/.
	Maple 2016, http://www.maplesoft.com/products/maple/.
	A. Menezes , T. Okamoto and S. Vanstone , Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, 39 (1993) , 1639-1646. doi: 10.1109/18.259647.
	O. Schirokauer , Discrete logarithms and local units, Philosophical Transactions of the Royal Society London A, 345 (1993) , 409-423. doi: 10.1098/rsta.1993.0139.
	D. Wiedemann , Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, 32 (1986) , 54-62. doi: 10.1109/TIT.1986.1057137.