On the use of the lattice sieve in the 3D NFS

Zajac, Pavol

doi:10.2478/v10127-010-0012-y

Abstract

An adaptation of the Number Field Sieve (NFS) algorithm to solve a discrete logarithm problem in degree 6 finite fields (DLP6) requires a modified sieving procedure to find smooth elements of the three dimensional sieve space. In our successful solution [P. Zajac: Discrete Logarithms and Degree Six NumbereField Sieve: A practical Approach. VDM Verlag Dr. M¨uller, Saarbr¨ucken, 2009] we have used a modified line sieving to process a box-shaped region using a large factor base. In this contribution, we compare the results with an alternative approach based on the lattice sieving, which was used in most of the classical factorization and DLP record solutions. Results indicate that this approach does not scale to the 3D-case, making DLP6 more difficult in practice than comparable classical DLP cases.

References

[1] AOKI, K.-KIDA, Y.-SHIMOYAMA, T.-UEDA, H.: GNFS factoring statisticsof RSA-100, 110, . . . , 150, April 16, 2004, http://eprint.iacr.org/2004/095.pdf.
Search in Google Scholar
[2] COMMEINE, A.-SEMAEV, I.: An algorithm to solve the discrete logarithm problemwith the number field sieve, in: Public Key Cryptography-PKC ’06 (M. Yung et al., eds.), 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, 2006, Lecture Notes in Comput. Sci., Vol. 3958, Springer-Verlag, Berlin, 2006, pp. 174-190.
Search in Google Scholar
[3] JOUX, A.-LERCIER, R.: Improvements to the general number field sieve for discretelogarithms in prime fields: a comparison with the Gaussian integer method, Math. Comp. 72 (2003), 953-967.10.1090/S0025-5718-02-01482-5
Search in Google Scholar
[4] JOUX, A.-LERCIER, R.-SMART, N.-VERCAUTEREN, F.: The number field sievein the medium prime case, in: Advances in Cryptology-CRYPTO ’06 (C. Dwork, ed.), 26th Annual International Cryptology Conference, Santa Barbara, California, USA, 2006, Lecture Notes in Comput. Sci., Vol. 4117, Springer-Verlag, Berlin, 2006, pp. 326-344.
Search in Google Scholar
[5] The Development of the Number Field Sieve (A. K. Lenstra, H. W. Lenstra, Jr., eds.), Lecture Notes in Math., Vol. 1554, Springer-Verlag, Berlin, 1993.
Search in Google Scholar
[6] LENSTRA, A. K.-LENSTRA, H. W., JR.-MANASSE, M. S.-POLLARD, J. M.: Thenumber field sieve, in: The Development of the Number Field Sieve (A. K. Lenstra, H. W. Lenstra, Jr., eds.), Lecture Notes in Math., Vol. 1554, Springer-Verlag, Berlin, 1993, pp. 11-42.
Search in Google Scholar
[7] LENSTRA, A. K.-VERHEUL, E. R.: An overview of the XTR public key system, in: Public-Key Cryptography and Computational Number Theory (K. Alster et al., eds.) Proc. of the Internat. Conference Organized by the Stefan Banach Internat. Math. Center, Warsaw, Poland, 2000, de Gruyter, Berlin, 2001, pp. 151-180.
Search in Google Scholar
[8] POLLARD, J.: The lattice sieve, in: The Development of the Number Field Sieve (A. K. Lenstra et al., eds.), Lecture Notes in Math., Vol. 1554, Springer-Verlag, Berlin, 1993, pp. 43-49.
Search in Google Scholar
[9] SCHIROKAUER, O.: Virtual logarithms, J. Algorithms 57 (2005), 140-147.10.1016/j.jalgor.2004.11.004
Search in Google Scholar
[10] ZAJAC, P.: Generalized line sieve algorithm, in: Proc. of ELITECH ’07, STU Bratislava, 2007.
Search in Google Scholar
[11] ZAJAC, P.: Remarks on the NFS complexity, Tatra Mt. Math. Publ. 41 (2008), 79-91.
Search in Google Scholar
[12] ZAJAC, P.: Discrete Logarithms and Degree Six Numbere Field Sieve: A practical Approach. VDM Verlag Dr. M¨uller, Saarbrücken, 2009.
Search in Google Scholar

On the use of the lattice sieve in the 3D NFS

Abstract

Paradigm

My account