Since the discovery of identity-based encryption schemes in 2000, bilinear pairings have been used in the design of hundreds of cryptographic protocols. The most commonly used pairings are constructed from elliptic curves over finite fields with small embedding degree. These pairings can have different security, performance, and functionality characteristics, and were therefore classified into Types 1, 2, 3 and 4. In this paper, we observe that this conventional classification is not applicable to pairings from elliptic curves with embedding degree one. It is important to understand the security, efficiency, and functionality of these pairings in light of recent attacks on certain pairings constructed from elliptic curves with embedding degree greater than one. We define three kinds of pairings from elliptic curves with embedding degree one, discuss some subtleties with using them to implement pairing-based protocols, and provide an estimated cost of implementing them on modern processors.

Several papers have studied fault attacks on computing a pairing value e(P,Q), where P is a public point and Q is a secret point. In this paper, we observe that these attacks are in fact effective only on a small number of pairing-based protocols, and that too only when the protocols are implemented with specific symmetric pairings. We demonstrate the effectiveness of the fault attacks on a public-key encryption scheme, an identity-based encryption scheme, and an oblivious transfer protocol when implemented with a symmetric pairing derived from a supersingular elliptic curve with embedding degree 2.

Galbraith, Lin, and Scott recently constructed efficiently computable endomorphisms for a large family of elliptic curves defined over IFq2 and showed, in the case where q is a 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 point multiplication method 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.

The Unified Model (UM) key agreement protocol is an efficient Diffie-Hellman scheme that has been included in many cryptographic standards, most recently in the NIST SP 800-56A standard. The UM protocol is believed to possess all important security attributes including key authentication and secrecy, resistance to unknown key-share attacks, forward secrecy, resistance to known-session key attacks, and resistance to leakage of ephemeral private keys, but is known to succumb to key-compromise impersonation attacks. In this paper we present a strengthening of the Canetti-Krawczyk security definition for key agreement that captures resistance to all important attacks that have been identified in the literature with the exception of key-compromise impersonation attacks. We then present a reductionist security proof that the UM protocol satisfies this new definition in the random oracle model under the Gap Diffie-Hellman assumption.

Fast algorithms for multiplication in finite fields are required for several cryptographic applications, in particular for implementing elliptic curve operations over binary fields F/sub 2m/. In this paper, we present new software algorithms for efficient multiplication over F/sub 2m/ that use a Gaussian normal basis representation. Two approaches are presented, direct normal basis multiplication and a method that exploits a mapping to a ring where fast polynomial-based techniques can be employed. Our analysis, including experimental results on an Intel Pentium family processor, shows that the new algorithms are faster and can use memory more efficiently than previous methods. Despite significant improvements, we conclude that the penalty in multiplication is still sufficiently large to discourage the use of normal bases in software implementations of elliptic curve systems.

We present a careful analysis of elliptic curve point multiplication methods that use the point halving technique of Knudsen and Schroeppel and compare these methods to traditional algorithms that use point doubling. The performance advantage of halving methods is clearest in the case of point multiplication kP, where P is not known in advance and smaller field inversion to multiplication ratios generally favor halving. Although halving essentially operates on affine coordinate representations, we adapt an algorithm of Knuth to allow efficient use of projective coordinates with halving-based windowing methods for point multiplication.

Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of curves that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.>

This paper presents a generalization of Moenck’s root finding algorithm over $GF(q)$, for q a prime or prime power. The generalized algorithm, like its predecessor, is deterministic, given a primitive element $\omega $ for $GF(q)$. If $q - 1$ is b-smooth, where $b = (\log q)^{O(1)} $, then the algorithm runs in polynomial time. An analogue of this generalization which applies to extension fields $GF(q^m )$ is also considered. The analogue is a deterministic algorithm based on the recently introduced affine method for root finding in $GF(q^m )$, where $m > 1$; it is, however, less efficient that the affine method itself.

Previously, no general-purpose algorithm was known for the elliptic curve logarithm problem that ran in better than exponential time.In this paper we demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying hit e field.For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.The implications of our results to public key cryptography are discussed. , the subgroup of 2? generated by P, and the subgroup of nth roots of unity in Fqk, where n denot es the order of P. The isomorphism is given by the Weil pairing.Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.This is indeed the case for special classes of elliptic curves, including the