On Shioda-Inose structures of one-parameter families of K3 surfaces

We develop an algorithm to determine a one-parameter family of elliptic curves associated to a one-parameter family of K3 surfaces with generic Picard number 19 by a Shioda-Inose structure. The family of elliptic curves is determined up to an isomorphism and an isogeny. An application to a generalized congruence number problem is also discussed.     

Efficient Arithmetic on Koblitz Curves

It has become increasingly common to implement discrete-logarithm based public-key protocols on elliptic curves over finite fields. The basic operation is scalar multiplication: taking a given integer multiple of a given point on the curve. The cost of the protocols depends on that of the elliptic scalar multiplication operation.Koblitz introduced a family of curves which admit especially fast elliptic scalar multiplication. His algorithm was later modified by Meier and Staffelbach. We give an improved version of the algorithm which runs 50 than any previous version. It is based on a new kind of representation of an integer, analogous to certain kinds of binary expansions. We also outline further speedups using precomputation and storage.     

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

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

Construction of CM Picard curves

In this article we generalize the CM method for elliptic and hyperelliptic curves to Picard curves. We describe the algorithm in detail and discuss the results of our implementation.

     

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(Fp) to Fp which can be more easily implemented. Fruthermore, we give an optimized algorithm for discrete logarithm on anomalous elliptic curves E(Fp).     

有限域上最优正规基的乘法表

本文给出了有限域上最优正规基乘法表的一个计算方法,改进了孙琦的相应结果.在有限域上椭圆曲线密码体制的应用中,本文给出的算法是非常有效的.     

Efficient pairing computation on supersingular Abelian varieties

We present a general technique for the efficient computation of pairings on Jacobians of supersingular curves. This formulation, which we call the eta pairing, generalizes results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic 3. We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma–Lee method. These ideas are applied to elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.      

The Igusa local zeta functions of elliptic curves

We determine the explicit form of the Igusa local zeta function associated to an elliptic curve. The denominator is known to be trivial. Here we determine the possible numerators and classify them according to the Kodaira-Néron classification of the special fibers of elliptic curves as determined by Tate's algorithm.

     

Chaotic maps-based password-authenticated key agreement using smart cards

Password-based authenticated key agreement using smart cards has been widely and intensively researched. Inspired by the semi-group property of Chebyshev maps and key agreement protocols based on chaotic maps, we proposed a novel chaotic maps-based password-authenticated key agreement protocol with smart cards. In our protocol, we avoid modular exponential computing or scalar multiplication on elliptic curve used in traditional authenticated key agreement protocols using smart cards. Our analysis shows that our protocol has comprehensive characteristics and can withstand attacks, including the insider attack, replay attack, and others, satisfying essential security requirements. Performance analysis shows that our protocol can refrain from consuming modular exponential computing and scalar multiplication on an elliptic curve. The computational cost of our protocol compared with related protocols is acceptable.     

Computing isogenies between elliptic curves over using Couveignes's algorithm

The heart of the improvements by Elkies to Schoof's algorithm for computing the cardinality of elliptic curves over a finite field is the ability to compute isogenies between curves. Elkies' approach is well suited for the case where the characteristic of the field is large. Couveignes showed how to compute isogenies in small characteristic. The aim of this paper is to describe the first successful implementation of Couveignes's algorithm. In particular, we describe the use of fast algorithms for performing incremental operations on series. We also insist on the particular case of the characteristic 2.

     

Constructing hyperelliptic curves of genus 2 suitable for cryptography

In this article we show how to generalize the CM-method for elliptic curves to genus two. We describe the algorithm in detail and discuss the results of our implementation.

     

Some Properties of Reduced Modular Polynomials

In this paper we will discuss some properties of reduced modular polynomials used in SEA algorithm for computing the number of rational points of elliptic curves on 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).     

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

How to Choose Secret Parameters for RSA-Type Cryptosystems over Elliptic Curves

Recently, and contrary to the common belief, Rivest and Silverman argued that the use of strong primes is unnecessary in the RSA cryptosystem. This paper analyzes how valid this assertion is for RSA-type cryptosystems over elliptic curves. The analysis is more difficult because the underlying groups are not always cyclic. Previous papers suggested the use of strong primes in order to prevent factoring attacks and cycling attacks. In this paper, we only focus on cycling attacks because for both RSA and its elliptic curve-based analogues, the length of the RSA-modulus n is typically the same. Therefore, a factoring attack will succeed with equal probability against all RSA-type cryptosystems. We also prove that cycling attacks reduce to find fixed points, and derive a factorization algorithm which (most probably) completely breaks RSA-type systems over elliptic curves if a fixed point is found.     

椭圆曲线密码的快速算法

80年代,椭圆曲线理论被引入数据加密领域,形成了一种新的公开密钥体制即椭圆曲线密码体制(ECC).该体制中,最耗时的运算是倍点运算也就是椭圆曲线上的点与一个整数的乘法运算.因此倍点运算的快速计算是椭圆曲线密码快速实现的关键.本文提出一种计算kP新的算法,使效率提高38%以上.     

On Quadratic Twists of Elliptic Curves and Some Applications of a Refined Version of Yu's Formula

In this article, we study some cohomology groups and quadratic twists of elliptic curves, and apply Tate local duality and the results of Kramer–Tunnell on local norm cokernel to give a refined version of Yu's formula in the case of elliptic curves. Then, by using this refinement formula, we obtain explicit orders of Shafarevich–Tate groups of some elliptic curves in quadratic number fields, including a few unconditional cases.     

Computing the Rational Torsion of an Elliptic Curve Using Tate Normal Form

It is a classical result (apparently due to Tate) that all elliptic curves with a torsion point of order n(4?n?10, or n=12) lie in a one-parameter family. However, this fact does not appear to have been used ever for computing the torsion of an elliptic curve. We present here an extremely down-to-earth algorithm using the existence of such a family.     

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.     

A procedure to calculate torsion¶of elliptic curves over ℚ

We present an algorithm which uses the analytic parameterization of elliptic curves to rapidly calculate torsion subgroups, and calculate its running time. This algorithm is much faster than the “traditional” Lutz–Nagell algorithm used by most computer algebra systems to calculate torsion subgroups. Received: 7 August 1997 / Revised version: 28 November 1997