文档介绍：Efficient Algorithms
for Pairing-Based Cryptosystems
Paulo . Barreto1, Hae Y. Kim1, Ben Lynn2, and Michael Scott3
1 Universidade de S˜ao Paulo, Escola Polit´ecnica
Av. Prof. Luciano Gualberto, tr. 3, 158
BR 05508-900, S˜ao Paulo(SP), Brazil
******@, ******@
puter Science Department, Stanford University, USA
******@
3 School puter Applications
Dublin City University
Ballymun, Dublin 9, Ireland
******@
Abstract. We describe fast new algorithms to implement recent crypto-
systems based on the Tate pairing. In particular, our techniques improve
pairing evaluation speed by a factor of about pared to previously
known methods in characteristic 3, and attain parable
to that of RSA in larger characteristics. We also propose faster algorithms
for scalar multiplication in characteristic 3 and square root extraction
over Fpm , the latter technique being also useful in contexts other than
that of pairing-based cryptography.
1 Introduction
The recent discovery [11] of groups where the Decision Diffie-Hellman (DDH)
problem is easy while putational Diffie-Hellman (CDH) problem is hard,
and the subsequent definition of a new class of problems variously called the
Gap Diffie-Hellman [11], Bilinear Diffie-Hellman [2], or Tate-Diffie-Hellman [6]
class, has given rise to the development of a new, ever expanding family of
cryptosystems based on pairings, such as:
– Short signatures [3].
– Identity-based encryption and escrow ElGamal encryption [2].
– Identity-based authenticated key agreement [29].
– Identity-based signature schemes [8,22,24].
– Tripartite Diffie-Hellman [10].
– Self-blindable credentials [33].
The growing interest and active research in this branch of cryptography has
led to new analyses of the associated security properties and to extensions to
more general (. hyperelliptic and superelliptic) algebraic curves [6,23].
However, a central operation in these systems puting