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.
Abstract:
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.
Reference:
Unpublished manuscript.
Download paper: pdf, postscript. (help)