In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman developed it in 1994 [1] and then elaborated it together with M. D. Huang in 1999.[2] Previous work includes the work of D. Coppersmith [3] about the DLP in fields of characteristic two.

The discrete logarithm problem in a finite field consists of solving the equation for , a prime number and an integer. The function for a fixed is a one-way function used in cryptography. Several cryptographic methods are based on the DLP such as the Diffie-Hellman key exchange, the El Gamal cryptosystem and the Digital Signature Algorithm.

Number theoretical background

edit

Function Fields

edit

Let   be a polynomial defining an algebraic curve over a finite field  . A function field may be viewed as the field of fractions of the affine coordinate ring  , where   denotes the ideal generated by  . This is a special case of an algebraic function field. It is defined over the finite field   and has transcendence degree one. The transcendent element will be denoted by  .

There exist bijections between valuation rings in function fields and equivalence classes of places, as well as between valuation rings and equivalence classes of valuations.[4] This correspondence is frequently used in the Function Field Sieve algorithm.

Divisors

edit

A discrete valuation of the function field  , namely a discrete valuation ring  , has a unique maximal ideal   called a prime of the function field. The degree of   is   and we also define  .

A divisor is a  -linear combination over all primes, so   where   and only finitely many elements of the sum are non-zero. The divisor of an element   is defined as  , where   is the valuation corresponding to the prime  . The degree of a divisor is  .

Method

edit

The Function Field Sieve algorithm consists of a precomputation where the discrete logarithms of irreducible polynomials of small degree are found and a reduction step where they are combined to the logarithm of  .

Functions that decompose into irreducible function of degree smaller than some bound   are called  -smooth. This is analogous to the definition of a smooth number and such functions are useful because their decomposition can be found relatively fast. The set of those functions   is called the factor base. A pair of functions   is doubly-smooth if   and   are both smooth, where   is the norm of an element of   over  ,   is some parameter and   is viewed as an element of the function field of  .

The sieving step of the algorithm consists of finding doubly-smooth pairs of functions. In the subsequent step we use them to find linear relations including the logarithms of the functions in the decompositions. By solving a linear system we then calculate the logarithms. In the reduction step we express   as a combination of the logarithm we found before and thus solve the DLP.

Precomputation

edit

Parameter selection

edit

The algorithm requires the following parameters: an irreducible function   of degree  , a function   and a curve   of given degree   such that  . Here   is the power in the order of the base field  . Let   denote the function field defined by  .

This leads to an isomorphism   and a homomorphism  Using the isomorphism each element of   can be considered as a polynomial in  .

One also needs to set a smoothness bound   for the factor base  .

Sieving

edit

In this step doubly-smooth pairs of functions   are found.

One considers functions of the form  , then divides   by any   as many times as possible. Any   that is reduced to one in this process is  -smooth. To implement this, Gray code can be used to efficiently step through multiples of a given polynomial.

This is completely analogous to the sieving step in other sieving algorithms such as the Number Field Sieve or the index calculus algorithm. Instead of numbers one sieves through functions in   but those functions can be factored into irreducible polynomials just as numbers can be factored into primes.

Finding linear relations

edit

This is the most difficult part of the algorithm, involving function fields, places and divisors as defined above. The goal is to use the doubly-smooth pairs of functions to find linear relations involving the discrete logarithms of elements in the factor base.

For each irreducible function in the factor base we find places   of   that lie over them and surrogate functions   that correspond to the places. A surrogate function   corresponding to a place   satisfies   where   is the class number of   and   is any fixed discrete valuation with  . The function defined this way is unique up to a constant in  .

By the definition of a divisor   for  . Using this and the fact that   we get the following expression:

 

where   is any valuation with  . Then, using the fact that the divisor of a surrogate function is unique up to a constant, one gets

 
 

We now use the fact that   and the known decomposition of this expression into irreducible polynomials. Let   be the power of   in this decomposition. Then

 

Here we can take the discrete logarithm of the equation up to a unit. This is called the restricted discrete logarithm  . It is defined by the equation   for some unit  .

 

where   is the inverse of   modulo  .

The expressions   and the logarithms   are unknown. Once enough equations of this form are found, a linear system can be solved to find   for all  . Taking the whole expression   as an unknown helps to gain time, since  ,  ,   or   don't have to be computed. Eventually for each   the unit corresponding to the restricted discrete logarithm can be calculated which then gives  .

Reduction step

edit

First   mod   are computed for a random  . With sufficiently high probability this is  -smooth, so one can factor it as   for   with  . Each of these polynomials   can be reduced to polynomials of smaller degree using a generalization of the Coppersmith method.[2] We can reduce the degree until we get a product of  -smooth polynomials. Then, taking the logarithm to the base  , we can eventually compute

 , which solves the DLP.

Complexity

edit

The Function Field Sieve is thought to run in subexponential time in

 

using the L-notation. There is no rigorous proof of this complexity since it relies on some heuristic assumptions. For example in the sieving step we assume that numbers of the form   behave like random numbers in a given range.

Comparison with other methods

edit

There are two other well known algorithms that solve the discrete logarithm problem in sub-exponential time: the index calculus algorithm and a version of the Number Field Sieve.[5] In their easiest forms both solve the DLP in a finite field of prime order but they can be expanded to solve the DLP in   as well.

The Number Field Sieve for the DLP in   has a complexity of   [6] and is therefore slightly slower than the best performance of the Function Field Sieve. However, it is faster than the Function Field Sieve when  . It is not surprising that there exist two similar algorithms, one with number fields and the other one with function fields. In fact there is an extensive analogy between these two kinds of global fields.

The index calculus algorithm is much easier to state than the Function Field Sieve and the Number Field Sieve since it does not involve any advanced algebraic structures. It is asymptotically slower with a complexity of  . The main reason why the Number Field Sieve and the Function Field Sieve are faster is that these algorithms can run with a smaller smoothness bound  , so most of the computations can be done with smaller numbers.

See also

edit

References

edit
  1. ^ L. Adleman. "The function field sieve". In: Algorithmic Number Theory (ANTS-I). Lecture Notes in Computer Science. Springer (1994), pp.108-121.
  2. ^ a b L. Adleman, M.D. Huang. "Function Field Sieve Method for Discrete Logarithms over Finite Fields". In: Inf. Comput. 151 (May 1999), pp. 5-16. DOI: 10.1006/inco.1998.2761.
  3. ^ D. Coppersmith. (1984), "Fast evaluation of discrete logarithms in fields of characteristic two". In: IEEE Trans. Inform. Theory IT-39 (1984), pp. 587-594.
  4. ^ M. Fried and M. Jarden. In: "Field Arithmetic". vol. 11. (Jan. 2005). Chap. 2.1. DOI: 10.1007/b138352.
  5. ^ D. Gordon. "Discrete Logarithm in GF(P) Using the Number Field Sieve". In: Siam Journal on Discrete Mathematics - SIAMDM 6 (Feb. 1993), pp. 124-138. DOI: 10.1137/0406010.
  6. ^ R. Barbulescu, P. Gaudry, T. Kleinjung. "The Tower Number Field Sieve". In: Advances in Cryptology – Asiacrypt 2015. Vol. 9453. Springer, May 2015. pp. 31-58