Miller's Weil Pairing Algorithm

History: In 1986 Victor Miller described an algorithm for evaluating the Weil pairing on an algebraic curve. The paper has never been published, but has nevertheless become the basis of many many follow on works in cryptography. Miller's algorithm is used to attack certain elliptic curve cryptosystems and has recently become the core of several new cryptosystems. As a result, Miller's paper is a frequently cited unpublished manuscript. The original unpublished manuscript is available for download below.

Author: V. Miller.

the problem of deducing a function on an algebraic curve having a given divisor is important in the field of indefinite integration. Indeed, it is the main computational step in determining whether an algebraic function possesses an indefinite integral. It has also become important recently in the study of discrete elliptic logarithm in cryptography and in the construction of the new class of error correcting codes which exceed the Varshamov-Gilbert bound. It can also be used to give partial answer to a question raised by Schoof in his paper on computing the exact number of points on an elliptic curve over a finite field.
Heretofore, the best known algorithm for calculating such functions was exponential in the size of the input. In this paper I give an algorithm which is linear in the size of the input (if arithmetic in the field under consideration takes constant time). For this algorithm it is necessary to represent the function as a straight-line program, for representation as a rational function may be exponential in the size of the input.

Unpublished manuscript.

Download paper:    pdf,    postscript.    (help)

Maintained by Dan Boneh.