Low-cost addition–subtraction sequences for the final exponentiation in pairings

In this paper, we address the problem of finding low cost addition–subtraction sequences for situations where a doubling step is significantly cheaper than a non-doubling one. One application of this setting appears in the computation of the final exponentiation step of the reduced Tate pairing defined on ordinary elliptic curves. In particular, we report efficient addition–subtraction sequences for the Kachisa–Schaefer–Scott family of pairing-friendly elliptic curves, whose parameters involve computing the multi-exponentiation of relatively large sequences of exponents with a size of up to 26 bits.     

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

Some classes of abstract simplicial complexes motivated by module theory

In this paper we analyze some classes of abstract simplicial complexes relying on algebraic models arising from module theory. To this regard, we consider a left-module on a unitary ring and find models of abstract complexes and related set operators having specific regularity properties, which are strictly interrelated to the algebraic properties of both the module and the ring.Next, taking inspiration from the aforementioned models, we carry out our analysis from modules to arbitrary sets. In such a more general perspective, we start with an abstract simplicial complex and an associated set operator. Endowing such a set operator with the corresponding properties obtained in our module instances, we investigate in detail and prove several properties of three subclasses of abstract complexes.More specifically, we provide uniformity conditions in relation to the cardinality of the maximal members of such classes. By means of the notion of OSS-bijection, we prove a correspondence theorem between a subclass of closure operators and one of the aforementioned families of abstract complexes, which is similar to the classic correspondence theorem between closure operators and Moore systems. Next, we show an extension property of a binary relation induced by set systems when they belong to one of the above families.Finally, we provide a representation result in terms of pairings between sets for one of the three classes of abstract simplicial complexes studied in this work.     

Provably secure non-interactive key distribution based on pairings

We define a security notion for non-interactive key distribution protocols. We identify an apparently hard computational problem related to pairings, the Bilinear Diffie-Hellman problem (BDH). After extending Sakai, Ohgishi, and Kasahara's pairing based protocol to a slightly more general setting, we show that breaking the system is polynomially equivalent to solving BDH in the random oracle model and thus establish a security proof.     

The Diffie–Hellman problem and generalization of Verheul’s theorem

Bilinear pairings on elliptic curves have been of much interest in cryptography recently. Most of the protocols involving pairings rely on the hardness of the bilinear Diffie–Hellman problem. In contrast to the discrete log (or Diffie–Hellman) problem in a finite field, the difficulty of this problem has not yet been much studied. In 2001, Verheul (Advances in Cryptology—EUROCRYPT 2001, LNCS 2045, pp. 195–210, 2001) proved that on a certain class of curves, the discrete log and Diffie–Hellman problems are unlikely to be provably equivalent to the same problems in a corresponding finite field unless both Diffie–Hellman problems are easy. In this paper we generalize Verheul’s theorem and discuss the implications on the security of pairing based systems.      

Computing pairings using <Emphasis Type="Italic">x</Emphasis>-coordinates only

To reduce bandwidth in elliptic curve cryptography one can transmit only x-coordinates of points (or x-coordinates together with an extra bit). This is called point compression. For further computation using the points one can either recover the y-coordinates by taking square roots or one can use point multiplication formulae which use x-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography when the embedding degree is even. We give a method to compute compressed pairings using x-coordinates only. We also show how to compute the compressed pairings using two x-coordinates and one y-coordinate. Our methods are more efficient than taking square roots when the embedding degree is small. We implemented the algorithms in the case of embedding degree 2 curves over where (mod 4) and found that our methods can be 10–15% faster than the analogous methods using square roots.      

Ordinary abelian varieties having small embedding degree

Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this paper we generalise their results by giving families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of group orders with embedding degrees 5, 10 and 12.     

Pairings for cryptographers

Many research papers in pairing-based cryptography treat pairings as a “black box”. These papers build cryptographic schemes making use of various properties of pairings. If this approach is taken, then it is easy for authors to make invalid assumptions concerning the properties of pairings. The cryptographic schemes developed may not be realizable in practice, or may not be as efficient as the authors assume.The aim of this paper is to outline, in as simple a fashion as possible, the basic choices that are available when using pairings in cryptography. For each choice, the main properties and efficiency issues are summarized. The paper is intended to be of use to non-specialists who are interested in using pairings to design cryptographic schemes.