The index calculus method using non-smooth polynomials

We study a generalized version of the index calculus method for the discrete logarithm problem in , when , is a small prime and . The database consists of the logarithms of all irreducible polynomials of degree between given bounds; the original version of the algorithm uses lower bound equal to one. We show theoretically that the algorithm has the same asymptotic running time as the original version. The analysis shows that the best upper limit for the interval coincides with the one for the original version. The lower limit for the interval remains a free variable of the process. We provide experimental results that indicate practical values for that bound. We also give heuristic arguments for the running time of the Waterloo variant and of the Coppersmith method with our generalized database.

     

Polynomial approximation of bilinear Diffie–Hellman maps

The problem of computing bilinear Diffie–Hellman maps is considered. It is shown that the problem of computing the map is equivalent to computing a diagonal version of it. Various lower bounds on the degree of any polynomial that interpolates this diagonal version of the map are found that shows that such an interpolation will involve a polynomial of large degree, relative to the size of the set on which it interpolates.     

The trace of an optimal normal element and low complexity normal bases

Let ${\mathbb{F}}_{q}$ be a finite field and consider an extension ${\mathbb{F}}_{q^{n}}$ where an optimal normal element exists. Using the trace of an optimal normal element in ${\mathbb{F}}_{q^{n}}$ , we provide low complexity normal elements in ${\mathbb{F}}_{q^{m}}$ , with m = n/k. We give theorems for Type I and Type II optimal normal elements. When Type I normal elements are used with m = n/2, m odd and q even, our construction gives Type II optimal normal elements in ${\mathbb{F}}_{q^{m}}$ ; otherwise we give low complexity normal elements. Since optimal normal elements do not exist for every extension degree m of every finite field ${\mathbb{F}}_{q}$ , our results could have a practical impact in expanding the available extension degrees for fast arithmetic using normal bases.     

On the existence of primitive completely normal bases of finite fields

Let ${\mathbb{F}}_q$ be the finite field of characteristic p with q elements and ${\mathbb{F}}_{q^n}$ its extension of degree n. We prove that there exists a primitive element of ${\mathbb{F}}_{q^n}$ that produces a completely normal basis of ${\mathbb{F}}_{q^n}$ over ${\mathbb{F}}_q$, provided that $n=p^{?}m$ with $(m,p)=1$ and $q>m$.     

Gauss periods as constructions of low complexity normal bases

Optimal normal bases are special cases of the so-called Gauss periods (Disquisitiones Arithmeticae, Articles 343–366); in particular, optimal normal bases are Gauss periods of type (n, 1) for any characteristic and of type (n, 2) for characteristic 2. We present the multiplication tables and complexities of Gauss periods of type (n, t) for all n and t = 3, 4, 5 over any finite field and give a slightly weaker result for Gauss periods of type (n, 6). In addition, we give some general results on the so-called cyclotomic numbers, which are intimately related to the structure of Gauss periods. We also present the general form of a normal basis obtained by the trace of any normal basis in a finite extension field. Then, as an application of the trace construction, we give upper bounds on the complexity of the trace of a Gauss period of type (n, 3).     

On the Security of the Digital Signature Algorithm

We present a key-recovery attack against the Digital Signature Algorithm (DSA). Our method is based on the work of Coppersmith [7], and is similar in nature to the attacks of Boneh et al. [5,9] which use lattice reduction techniques to determine upper bounds on the size of an RSA decryption exponent under which it will be revealed by the attack. This work similarly determines provable upper bounds on the sizes of the two key parameters in the DSA for which the system can be broken. Specifically if about half of the total number of bits in the secret and ephemeral keys, assuming contiguous unknown bits in each key, are known, the system can be shown to be insecure. The same technique shows that if about half of the total number of bits in two ephemeral keys are known, again assumed contiguous unknown bits in each key, but with no knowledge of the secret key, the system can be shown to be insecure.