International Association for Cryptologic Research

International Association
for Cryptologic Research


Darrel Hankerson


On the Efficiency and Security of Pairing-Based Protocols in the Type 1 and Type 4 Settings
We focus on the implementation and security aspects of cryptographic protocols that use Type 1 and Type 4 pairings. On the implementation front, we report improved timings for Type 1 pairings derived from supersingular elliptic curves in characteristic 2 and 3 and the first timings for supersingular genus-2 curves in characteristic 2 at the 128-bit security level. In the case of Type 4 pairings, our main contribution is a new method for hashing into ${\mathbb G}_2$ which makes the Type 4 setting almost as efficient as Type 3. On the security front, for some well-known protocols we discuss to what extent the security arguments are tenable when one moves to genus-2 curves in the Type 1 case. In Type 4, we observe that the Boneh-Shacham group signature scheme, the very first protocol for which the Type 4 setting was introduced in the literature, is trivially insecure, and we describe a small modification that appears to restore its security.
Comparing Two Pairing-Based Aggregate Signature Schemes
In 2003, Boneh, Gentry, Lynn and Shacham (BGLS) devised the first provably-secure aggregate signature scheme. Their scheme uses bilinear pairings and their security proof is in the random oracle model. The first pairing-based aggregate signature scheme which has a security proof that does not make the random oracle assumption was proposed in 2006 by Lu, Ostrovsky, Sahai, Shacham and Waters (LOSSW). In this paper, we compare the security and efficiency of the BGLS and LOSSW schemes when asymmetric pairings derived from Barreto-Naehrig (BN) elliptic curves are employed.
Analyzing the Galbraith-Lin-Scott Point Multiplication Method for Elliptic Curves over Binary Fields
Darrel Hankerson Koray Karabina Alfred Menezes
Galbraith, Lin and Scott recently constructed efficiently-computable endomorphisms for a large family of elliptic curves defined over F_{q^2} and showed, in the case where q is prime, that the Gallant-Lambert-Vanstone point multiplication method for these curves is significantly faster than point multiplication for general elliptic curves over prime fields. In this paper, we investigate the potential benefits of using Galbraith-Lin-Scott elliptic curves in the case where q is a power of 2. The analysis differs from the q prime case because of several factors, including the availability of the point halving strategy for elliptic curves over binary fields. Our analysis and implementations show that Galbraith-Lin-Scott offers significant acceleration for curves over binary fields, in both doubling- and halving-based approaches. Experimentally, the acceleration surpasses that reported for prime fields (for the platform in common), a somewhat counterintuitive result given the relative costs of point addition and doubling in each case.