×

zbMATH — the first resource for mathematics

The function field sieve in the medium prime case. (English) Zbl 1140.94349
Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 254-270 (2006).
Summary: In this paper, we study the application of the function field sieve algorithm for computing discrete logarithms over finite fields of the form \({\mathbb {F}}_{q^n}\) when \(q\) is a medium-sized prime power. This approach is an alternative to a recent paper of Granger and Vercauteren for computing discrete logarithms in tori, using efficient torus representations. We show that when \(q\) is not too large, a very efficient \(L(1/3)\) variation of the function field sieve can be used. Surprisingly, using this algorithm, discrete logarithms computations over some of these fields are even easier than computations in the prime field and characteristic two field cases. We also show that this new algorithm has security implications on some existing cryptosystems, such as torus based cryptography in \(T_{30}\), short signature schemes in characteristic 3 and cryptosystems based on supersingular abelian varieties. On the other hand, cryptosystems involving larger basefields and smaller extension degrees, typically of degree at most 6, such as LUC, XTR or \(T_{6}\) torus cryptography, are not affected.
For the entire collection see [Zbl 1108.94002].

MSC:
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adleman, L., DeMarrais, J.: A subexponential algorithm for discrete logarithms over all finite fields. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 147–158. Springer, Heidelberg (1994) · Zbl 0871.11094 · doi:10.1007/3-540-48329-2_13
[2] Adleman, L., DeMarrais, J.: A subexponential algorithm for discrete logarithms over all finite fields. Math. Comp. 61(203), 1–15 (2003) · Zbl 0784.11060 · doi:10.1090/S0025-5718-1993-1225541-3
[3] Adleman, L.M.: The function field sieve. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 108–121. Springer, Heidelberg (1994) · Zbl 0839.11066 · doi:10.1007/3-540-58691-1_48
[4] Adleman, L.M., Huang, M.A.: Function field sieve method for discrete logarithms over finite fields. In: Information and Computation, vol. 151, pp. 5–16. Academic Press, London (1999) · Zbl 1006.11078
[5] Boneh, D., Franklin, M.: Identity based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13
[6] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001) · Zbl 1064.94554 · doi:10.1007/3-540-45682-1_30
[7] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. of Cryptology 17(4), 297–319 (2004) · Zbl 1070.94010 · doi:10.1007/s00145-004-0314-9
[8] Brouwer, A.E., Pellikaan, R., Verheul, E.R.: Doing More with Fewer Bits. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 321–332. Springer, Heidelberg (1999) · Zbl 0977.94025 · doi:10.1007/978-3-540-48000-6_26
[9] Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE transactions on information theory IT-30(4), 587–594 (1984) · Zbl 0554.12013 · doi:10.1109/TIT.1984.1056941
[10] Gordon, D.: Discrete logarithms in GF(p) using the number field sieve. SIAM J. Discrete Math. 6, 124–138 (1993) · Zbl 0772.11046 · doi:10.1137/0406010
[11] Granger, R., Holt, A., Page, D., Smart, N., Vercauteren, F.: Function field sieve in characteristic three. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 223–234. Springer, Heidelberg (2004) · Zbl 1125.11358 · doi:10.1007/978-3-540-24847-7_16
[12] Granger, R., Vercauteren, F.: On the discrete logarithm problem on algebraic tori. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 66–85. Springer, Heidelberg (2005) · Zbl 1145.94442 · doi:10.1007/11535218_5
[13] Joux, A.: A one round protocol for tripartite diffie-hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000) · Zbl 1029.94026 · doi:10.1007/10722028_23
[14] Joux, A., Lercier, R.: The function field sieve is quite special. In: Fieker, C., Kohel, D.R. (eds.) ANTS 2002. LNCS, vol. 2369, pp. 431–445. Springer, Heidelberg (2002) · Zbl 1057.11069 · doi:10.1007/3-540-45455-1_34
[15] Joux, A., Lercier, R.: Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method. Math. Comp. 72, 953–967 (2003) · Zbl 1099.11074
[16] Joux, A., Lercier, R., Smart, N., Vercauteren, F.: The number field sieve in the medium prime case (preprint) · Zbl 1161.11417
[17] LaMacchia, B.A., Odlyzko, A.M.: Solving Large Sparse Linear Systems Over Finite Fields. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 109–133. Springer, Heidelberg (1991) · Zbl 0786.65028 · doi:10.1007/3-540-38424-3_8
[18] Lanczos, C.: Solutions of systems of linear equations by minimized iterations (Bureau of Standards). J. Res. Nat. 49, 33–53 (1952)
[19] Lennon, M.J.J., Smith, P.J.: LUC: A New Public Key System. In: IFIP TC11 Ninth International Conference on Information Security IFIP/Sec., pp. 103–117 (1993)
[20] Lenstra, A.K., Lenstra Jr., H.W. (eds.): The development of the number field sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Heidelberg (1993) · Zbl 0777.00017
[21] Lenstra, A.K., Verheul, E.R.: The XTR Public Key System. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 1–19. Springer, Heidelberg (2000) · Zbl 0995.94538 · doi:10.1007/3-540-44598-6_1
[22] Lercier, R., Vercauteren, F.: Discrete logarithms in \(\mathbb{F}p^{18}\) - 101 digits. NMBRTHRY mailing list (June 2005)
[23] Odlyzko, A.M.: Discrete logarithms in finite fields and their cryptographic significance. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 224–314. Springer, Heidelberg (1985) · Zbl 0594.94016 · doi:10.1007/3-540-39757-4_20
[24] Panario, D., Gourdon, X., Flajolet, P.: An analytic approach to smooth polynomials over finite fields. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 226–236. Springer, Heidelberg (1998) · Zbl 0908.11057 · doi:10.1007/BFb0054865
[25] Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comp. 32, 918–924 (1978) · Zbl 0382.10001
[26] Rubin, K., Silverberg, A.: Supersingular abelian varieties in cryptology. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 336–353. Springer, Heidelberg (2002) · Zbl 1026.94540 · doi:10.1007/3-540-45708-9_22
[27] Rubin, K., Silverberg, A.: Torus-Based Cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 349–365. Springer, Heidelberg (2003) · Zbl 1122.94400 · doi:10.1007/978-3-540-45146-4_21
[28] Schirokauer, O.: Discrete logarithms and local units. Phil. Trans. R. Soc. Lond. A 345, 409–423 (1993) · Zbl 0795.11063
[29] van Dijk, M., Granger, R., Page, D., Rubin, K., Silverberg, A., Stam, M., Woodruff, D.: Practical cryptography in high dimensional tori. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 234–250. Springer, Heidelberg (2005) · Zbl 1137.94362 · doi:10.1007/11426639_14
[30] Wiedemann, D.H.: Solving Sparse Linear Equations Over Finite Fields. IEEE Trans. Information Theory 32, 54–62 (1986) · Zbl 0607.65015 · doi:10.1109/TIT.1986.1057137
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.