Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem

In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately , given that the unknown logarithm has a specified number of 1's, say , in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity , and a Las Vegas algorithm with complexity

.

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with complexity . We also present some explicit constructions for splitting systems that make use of perfect hash families.

     

Solvability of the problem of taking the discrete logarithm

It is proved that consideration of the solvability problem for taking the discrete logarithm in a residue ring modulo composite M can be reduced to consideration of a similar problem in residue rings modulo pq, where p and q are prime divisors of M. For moduli of form pq, necessary and sufficient conditions for solvability checking are obtained in some cases. In addition, the problem of raising a solution of an exponential comparison in a residue ring modulo p ^α is solved.     

On the discrete logarithm problem for prime-field elliptic curves

In recent years several papers have appeared that investigate the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. With a notable exception by Petit et al. in 2016, all numerous papers on the subject have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev's method and the specialised algorithm by Petit et al..     

The discrete logarithm problem from a local duality perspective

The discrete logarithm problem is analyzed from the perspective of Tate local duality. Local duality in the multiplicative case and the case of Jacobians of curves over p-adic local fields are considered. When the local field contains the necessary roots of unity, the case of curves over local fields is polynomial time reducible to the multiplicative case, and the multiplicative case is polynomial time equivalent to computing discrete logarithm in finite fields. When the local field does not contains the necessary roots of unity, similar results can be obtained at the cost of going to an extension that contains these roots of unity. There was evidence in the analysis that suggests that the minimal extension where the local duality can be rationally and algorithmically defined must contain the roots of unity. Therefore, the discrete logarithm problem appears to be well protected against an attack using local duality. These results are also of independent interest for algorithmic study of arithmetic duality as they explicitly relate local duality in the case of curves over local fields to the multiplicative case and Tate-Lichtenbaum pairing (over finite fields).     

Some heuristics and results for small cycles of the discrete logarithm

Brizolis asked the question: does every prime have a pair such that is a fixed point for the discrete logarithm with base ? The first author previously extended this question to ask about not only fixed points but also two-cycles, and gave heuristics (building on work of Zhang, Cobeli, Zaharescu, Campbell, and Pomerance) for estimating the number of such pairs given certain conditions on and . In this paper we extend these heuristics and prove results for some of them, building again on the aforementioned work. We also make some new conjectures and prove some average versions of the results.

     

Slope packings and coverings,and generic algorithms for the discrete logarithm problem

We consider the set of slopes of lines formed by joining all pairs of points in some subset S of a Desarguesian affine plane of prime order p. If all the slopes are distinct and non‐infinite, we have a slope packing; if every possible non‐infinite slope occurs, then we have a slope covering. We review and unify some results on these problems that can be derived from the study of Sidon sets and sum covers. Then we report some computational results, we have obtained for small values of p. Finally, we point out some connections between slope packings and coverings and generic algorithms for the discrete logarithm problem in prime order (sub)groups. Our results provide a combinatorial characterization of such algorithms, in the sense that any generic algorithm implies the existence of a certain slope packing or covering, and conversely. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 36–50, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10033     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

Comment: A new blind signature based on the discrete logarithm problem for untraceability

In 2004, Lee et al. [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press] proposed a new untraceable blind signature based on DLP in order to overcome the “security limits” of Carmenisch et al.’s scheme. However, we show there are two mistakes in [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press]: 1. The Carmenisch et al.’s scheme does meet the requirement of untraceability and the cryptanalysis proposed by Lee et al. is not correct; 2. Though Lee et al.’s scheme is untraceable, the proof of its untraceability in [C.C. Lee, M.S. Hwang, W.P. Yang, A new blind signature based on the discrete logarithm problem for untraceability, Appl. Math. Comput., in press] is wrong (in this paper we also give the correct proof of its untraceability). So Lee et al.’s scheme does not have any advantage and it is unpractical since the cost of the scheme is higher compared with Carmenisch et al.’s scheme.     

Some variants of the logarithm

We construct certain extensions of Hodge structures using points on algebraic curves and study them. We also introduce and use a related function theory which forms a genus g > 0 version of that of classical hyperlogarithms. Received: 9 May 2000 / Revised version: 8 December 2000     

Complexity of a determinate algorithm for the discrete logarithm

Translated from Matematicheskie Zametki, Vol. 55, No. 2, pp. 91–101, February, 1994.     

On the discrete logarithm in the divisor class group of curves

Let be a curve which is defined over a finite field of characteristic . We show that one can evaluate the discrete logarithm in by operations in . This generalizes a result of Semaev for elliptic curves to curves of arbitrary genus.

     

Two-side estimates of the number of fixed points of a discrete logarithm

Lower and upper bounds are obtained for an average number of solutions to the congruence g _x ?? x (mod p) in nonnegative integer numbers x ?? p ? 1, where g is a primitive root modulo p.     

Speeding up elliptic curve discrete logarithm computations with point halving

Pollard rho method and its parallelized variants are at present known as the best generic algorithms for computing elliptic curve discrete logarithms. We propose new iteration function for the rho method by exploiting the fact that point halving is more efficient than point addition for elliptic curves over binary fields. We present a careful analysis of the alternative rho method with new iteration function. Compared to the previous r-adding walk, generally the new method can achieve a significant speedup for computing elliptic curve discrete logarithms over binary fields. For instance, for certain NIST-recommended curves over binary fields, the new method is about 12–17% faster than the previous best methods.     

Efficient discrete logarithm based multi-signature scheme in the plain public key model

In this paper, we provide a new multi-signature scheme that is proven secure in the plain public key model. Our scheme is practical and efficient according to computational costs, signature size and security assumptions. At first, our scheme matches the single ordinary discrete logarithm based signature scheme in terms of signing time, verification time and signature size. Secondly, our scheme requires only two rounds of interactions and each signer needs nothing more than a certified public key to produce the signature, meaning that our scheme is compatible with existing PKIs. Thirdly, our scheme has been proven secure in the random oracle model under standard discrete logarithm (DL) assumption. It outperforms a newly proposed multi-signature scheme by Bagherzandi, Cheon and Jarecki (BCJ scheme) in terms of both computational costs and signature size.     

Some laws of the iterated logarithm in Hilbertian autoregressive models

We consider the law of the iterated logarithm for the empirical covariance of Hilbertian autoregressive processes. As an application, we obtain laws of the iterated logarithm for the eigenvalues and associated projectors of the empirical covariance.     

Some exact rates in the functional law of the iterated logarithm

We find exact convergence rate in the Strassen's functional law of the iterated logarithm for a class of elements on the boundary of the limit set. Our result applies, in particular, to the power functions c_αx^α with α ]1/2,1[, thus solving a small ball estimate problem which was open for ten years.     

Analysis of the Herlestam and Johannesson discrete logarithm scheme inGF(2 N ) for largeN

The Herlestam and Johannesson algorithm for computing discrete logarithms inGF(2 ⁿ ) requires the precomputation of logarithms for a target set consisting of all field elements of Hamming weight less than some predetermined value. The procedure, both in precomputation and at run-time, selects elements of lowest weight from large sets of elements. These sets are not randomly chosen but their minimum weight statistics parallel those for sets of equal size chosen entirely at random. By analyzing the statistics for randomly chosen sets, we show that the target set must contain all elements up to about weightn/3–8. This is clearly impractical for even moderately large values ofn.This work was supported by MITRE Corp. IR & D funds.Dr. Berkovits was on leave from the University of Lowell, Lowell, MA, 01854.     

Regular splittings and the discrete Neumann problem

Summary Iterative methods are discussed for approximating a solution to a singular but consistent square linear systemAx=b. The methods are based upon splittingA=M–N withM nonsingular. Monotonicity and the concept of regular splittings, introduced by Varga, are used to determine some necessary and some sufficient conditions in order that the iterationx ⁱ⁺¹=M^–1Nxⁱ+M^–1b converge to a solution to the linear system. Finally, applications are given to solving the discrete Neumann problem by iteration which are based upon the inherent monotonicity in the formulation.This research was supported by the U. S. Army Research Office-Durham under contract no. DAHCO4 74 C 0019.