Refinements of Miller's algorithm for computing the Weil/Tate pairing

The efficient computation of the Weil and Tate pairings is of significant interest in the implementation of certain recently developed cryptographic protocols. The standard method of such computations has been the Miller algorithm. Three refinements to Miller's algorithm are given in this work. The first refinement is an overall improvement. If the binary expansion of the involved integer has relatively high Hamming weight, the second improvement suggested shows significant gains. The third improvement is especially efficient when the underlying elliptic curve is over a finite field of characteristic three, which is a case of particular cryptographic interest. Comment on the performance analysis and characteristics of the refinements are given.     

On oriented supersingular elliptic curves

We revisit theoretical background on OSIDH (Oriented Supersingular Isogeny Diffie-Hellman protocol), which is an isogeny-based key-exchange protocol proposed by Colò and Kohel at NutMiC 2019. We give a proof of a fundamental theorem for OSIDH. The theorem was stated by Colò and Kohel without proof. Furthermore, we consider parameters of OSIDH, give a sufficient condition on the parameters for the protocol to work, and estimate the size of the parameters for a certain security level.     

On the supersingular reduction of elliptic curves

Let a∈Q and denote byE _a the curvey ² = (x ² + l)(x + a). We prove thatE _a(F_p) is cyclic for infinitely many primesp. This fact was known previously only under the assumption of the generalized Riemann hypothesis. Research partially supported by NSERC grant A9418.     

On computable isomorphisms in efficient asymmetric pairing-based systems

In this paper, we examine the hard problems underlying asymmetric pairings, their precise relationships and how they affect a number of existing protocols. Furthermore, we present a new model for the elliptic curve groups used in asymmetric pairings, which allows both an efficient pairing and an efficiently computable isomorphism.     

On isogeny graphs of supersingular elliptic curves over finite fields

We study the isogeny graphs of supersingular elliptic curves over finite fields, with an emphasis on the vertices corresponding to elliptic curves of j-invariant 0 and 1728.     

Faster computation of the Tate pairing

Text

This paper proposes new explicit formulas for the doubling and addition steps in Miller's algorithm to compute the Tate pairing on elliptic curves in Weierstrass and in Edwards form. For Edwards curves the formulas come from a new way of seeing the arithmetic. We state the first geometric interpretation of the group law on Edwards curves by presenting the functions which arise in addition and doubling. The Tate pairing on Edwards curves can be computed by using these functions in Miller's algorithm. Computing the sum of two points or the double of a point and the coefficients of the corresponding functions is faster with our formulas than with all previously proposed formulas for pairings on Edwards curves. They are even competitive with all published formulas for pairing computation on Weierstrass curves. We also improve the formulas for Tate pairing computation on Weierstrass curves in Jacobian coordinates. Finally, we present several examples of pairing-friendly Edwards curves.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=nideQo-K9ME/.     

Fibre products of supersingular curves and the enumeration of irreducible polynomials with prescribed coefficients

For any positive integers $n\ge 3$, $r\ge 1$ we present formulae for the number of irreducible polynomials of degree n over the finite field ${\mathbb{F}}_{2^r}$ where the coefficients of $x^{n-1}$, $x^{n-2}$ and $x^{n-3}$ are zero. Our proofs involve counting the number of points on certain algebraic curves over finite fields, a technique which arose from Fourier-analysing the known formulae for the ${\mathbb{F}}_2$ base field cases, reverse-engineering an economical new proof and then extending it. This approach gives rise to fibre products of supersingular curves and makes explicit why the formulae have period 24 in n.     

Efficient computation of sparse structures

Basic graph structures such as maximal independent sets (MIS's) have spurred much theoretical research in randomized and distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault‐tolerance or load‐balance properties. We propose and study “low‐average degree” or “sparse” versions of such structures. Interestingly, in sharp contrast to, say, MIS's, it can be shown that checking whether a structure is sparse, will take substantial time. Nevertheless, we are able to develop good sequential/distributed (randomized) algorithms for such sparse versions. We also complement our algorithms with several lower bounds. Randomization plays a key role in our upper and lower bound results. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 322–344, 2016     

Resultants and the algebraicity of the join pairing on Chow varieties

The Chow/Van der Waerden approach to algebraic cycles via resultants is used to give a purely algebraic proof for the algebraicity of the complex suspension. The algebraicity of the join pairing on Chow varieties then follows. The approach implies a more algebraic proof of Lawson's complex suspension theorem in characteristic 0. The continuity of the action of the linear isometries operad on the group completion of the stable Chow variety is a consequence.

     

Descent Calculations for the Elliptic Curves of Conductor 11

Let A be any one of the three elliptic curves over Q with conductor11. We show that A has Mordell–Weil rank zero over itsfield of 5-division points. In each case we also compute the5-primary part of the Tate–Shafarevich group. Our calculationsmake use of the Galois equivariance of the Cassels–Tatepairing. 2000 Mathematics Subject Classification 11G05, 11Y40,11R23.     

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.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Identifying quadric bundle structures on complex projective varieties

In this paper we characterize smooth complex projective varieties that admit a quadric bundle structure on some dense open subset in terms of the geometry of certain families of rational curves.      

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.