An algorithm for DLP on anomalous elliptic curves over Fp

This paper improves the method of discrete logarithm on anomalous elliptic curves, and establishes an isomorphism from E(F_p) to F_p which can be more easily implemented. Fruthermore, we give an optimized algorithm for discrete logarithm on anomalous elliptic curves E(F_p).     

有限域上椭圆曲线的分类及其性质

在这篇文章里，我们利用椭圆曲线的阶给出了椭圆曲线的一个分类，并推导出一些性质。     

Elliptic curve analogues of a pseudorandom generator

Using the discrete logarithm in [7] and [9] a large family of pseudorandom binary sequences was constructed. Here we extend this construction. An interesting feature of this extension is that in certain special cases we get sequences involving points on elliptic curves.     

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.     

椭圆曲线素阶群上的离散对数求解

该文对解椭圆曲线上离散对数的Pollard ρ算法和并行碰撞搜索算法分别建立了它 们的图论模型和分析了碰撞技巧,比较了两个算法,进而提出了设计迭代函数的准则并 给出一个改进的并行碰撞算法.     

Cover attacks for elliptic curves with cofactor two

For cryptographic applications, in order to avoid a reduction of the discrete logarithm problem via the Chinese remainder theorem, one usually considers elliptic curves over finite fields whose order is a prime times a small so-called cofactor c. It is, however, possible to attack specific curves with this property via dedicated attacks. Particularly, if an elliptic curve \(E/\mathbb {F}_{q^n}\) is given, one might try to use the idea of cover attacks to reduce the problem to the corresponding problem in the Jacobian of a curve of genus \(g \ge n\) over \(\mathbb {F}_q\). In the given situation, the only attack so far which follows this idea is the GHS attack, this attack requires that the cofactor c is divisible by 4 as otherwise the genus of the resulting curve is too large. We present an algorithm for finding genus 3 hyperelliptic covers for the case \(c=2\). The construction works in odd characteristic and the resulting cover map has degree 3. As an application, two explicit examples of elliptic curves whose order are respectively 2 times a 149-bit prime and 2 times a 256-bit prime vulnerable to the attack are given.     

The State of Elliptic Curve Cryptography

Since the introduction of public-key cryptography by Diffie and Hellman in 1976, the potential for the use of the discrete logarithm problem in public-key cryptosystems has been recognized. Although the discrete logarithm problem as first employed by Diffie and Hellman was defined explicitly as the problem of finding logarithms with respect to a generator in the multiplicative group of the integers modulo a prime, this idea can be extended to arbitrary groups and, in particular, to elliptic curve groups. The resulting public-key systems provide relatively small block size, high speed, and high security. This paper surveys the development of elliptic curve cryptosystems from their inception in 1985 by Koblitz and Miller to present day implementations.     

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).     

The modularity of some Q-curves

A Q-curve is an elliptic curve, defined over a number field, that is isogenous to each of its Galois conjugates. Ribet showed that Serre's conjectures imply that such curves should be modular. Let E be an elliptic curve defined over a quadratic field such that E is 3-isogenous to its Galois conjugate. We give an algorithm for proving any such E is modular and give an explicit example involving a quotient of J_o (169). As a by-product, we obtain a pair of 19-isogenous elliptic curves, and relate this to the existence of a rational point of order 19 on J₁ (13).     

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..     

Expander graphs based on GRH with an application to elliptic curve cryptography

Text

We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our result implies that the Cayley graph of ^∗(Z/qZ) with respect to small prime generators is an expander. As another application, we show that the graph of small prime degree isogenies between ordinary elliptic curves achieves nonnegligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem.

Video

For a video summary of this paper, please visit http://www.youtube.com/watch?v=7jwxmKWWsyM.     

The difference between the ordinary height and the canonical height on elliptic curves

We estimate the bounds for the difference between the ordinary height and the canonical height on elliptic curves over number fields. Our result is an improvement of the recent result of Cremona, Prickett, and Siksek [J.E. Cremona, M. Prickett, S. Siksek, Height difference bounds for elliptic curves over number fields, J. Number Theory 116 (2006) 42-68]. Our bounds are usually sharper than the other known bounds.     

Rank of <Emphasis Type="Italic">K</Emphasis><Subscript>2</Subscript> of elliptic curves

We prove that (i) rank(K2(E)) 1 for all elliptic curves E defined over Q with a rational torsion point of exact order N 4; (ii) rank(K2(E)) 1 for all but at most one R-isomorphism class of elliptic curves E defined over Q with a rational torsion point of exact order 3. We give some sufficient conditions for rank(K2(EZ)) 1.     

改进的基于ECDLP的无证书部分盲签名机制

对邵国金等人(四川大学学报(工程科学版),2012年第1期)提出的基于椭圆曲线离散对数难题(ECDLP)的无双线性对运算的部分盲签名方案进行安全性分析,发现方案不能抵抗公钥替换攻击.为此,提出了一个改进方案.在随机谕言模型下证明了改进方案对自适应选择消息和身份攻击是存在性不可伪造性的.将所提方案与部分现有的无证书部分盲签名方案的计算性能进行了比较,结果显示改进方案具有较高的运算效率.     

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.     

Improving the Gaudry–Schost algorithm for multidimensional discrete logarithms

Designs, Codes and Cryptography - The discrete logarithm problem arises from various areas, including counting the number of points of certain curves and diverse cryptographic schemes. The...     

Points of finite order on elliptic curves with complex multiplication

Let E be an elliptic curve defined overQ. The group ofQ- rational points of finite order on E is a finite group T(E). In this article T(E) is computed for all elliptic curves defined overQ admitting complex multiplication. The only possible values for the order t of T(E) are 1, 2, 3, 4, or 6 in these cases. A standard form for an affine equation describing an elliptic curve with a given j-invariant is obtained. This is used to show that if j ≠ 0, 2⁶ 3³, then the number ofQ- rational points of order 2 on E depends only on j. The results are summarized in the accompanying table.     

Hasse invariants and anomalous primes for elliptic curves with complex multiplication

Let C be an elliptic curve defined over Q. Let p be a prime where C has good reduction. By definition, p is anomalous for C if the Hasse invariant at p is congruent to 1 modulo p. The phenomenon of anomalous primes has been shown by Mazur to be of great interest in the study of rational points in towers of number fields. This paper is devoted to discussing the Hasse invariants and the anomalous primes of elliptic curves admitting complex multiplication. The two special cases Y² = X³ + a₄X and Y² = X³ + a₆ are studied at considerable length. As corollaries, some results in elementary number theory concerning the residue classes of the binomial coefficients (_n²ⁿ) (Resp. (_n³ⁿ)) modulo a prime p = 4n + 1 (resp. p = 6n + 1) are obtained. It is shown that certain classes of elliptic curves admitting complex multiplication do not have any anomalous primes and that others admit only very few anomalous primes.     

椭圆曲线有理点扭子群的明显分类

本文给出了有理数域Q上椭圆曲线E按其偶数阶循环扭子群Etors(Q)的分 类,并给出了Etors(Q)的生成元.这些结果,连同新近Ono在Etors(Q)非循环情形 的结果,完全解决了E含2阶有理点时的分类和参数化问题.     

对一群签名方案的分析与改进

通过对夏祥盛等人的动态门限群签名方案的研究,指出该方案的若干不足,其中最主要的不足是通过伪造和不可追踪性,并对该方案进行了改进．与现有群签名方案不同,新方案中用户的秘密数由用户自己选取,从而避免了双线性对的计算,大大提高了效率．分析说明改进的群签名方案几乎克服了原方案的所有缺点．