Miller algorithm
E860121
The Miller algorithm is an efficient computational method used in elliptic curve cryptography to evaluate pairings such as the Weil and Tate pairings.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
cryptographic algorithm
ⓘ
pairing computation algorithm ⓘ |
| appliedIn |
Ate pairing variants
ⓘ
Tate pairing computation ⓘ Weil pairing computation ⓘ attribute-based encryption ⓘ identity-based encryption ⓘ key agreement protocols ⓘ pairing-based cryptographic protocols ⓘ reduced Tate pairing computation ⓘ short signature schemes ⓘ |
| assumption | elliptic curve group is cyclic of known order ⓘ |
| basedOn |
elliptic curve arithmetic
ⓘ
rational functions on elliptic curves ⓘ |
| complexity | O(log n) elliptic curve operations for scalar n ⓘ |
| computes | pairing value as a rational function evaluated at points ⓘ |
| domain |
finite fields of large characteristic
ⓘ
finite fields of small characteristic ⓘ |
| field | elliptic curve cryptography ⓘ |
| input |
an integer related to the group order
ⓘ
elliptic curve over a finite field ⓘ two points on an elliptic curve ⓘ |
| namedAfter | Victor S. Miller NERFINISHED ⓘ |
| optimizedBy |
using denominator elimination techniques
ⓘ
using efficient line evaluation formulas ⓘ using projective coordinates ⓘ using special forms of elliptic curves ⓘ |
| output | element of a finite field extension ⓘ |
| property |
efficient
ⓘ
iterative ⓘ runs in time proportional to the bit length of the scalar ⓘ uses double-and-add style loop ⓘ |
| proposedBy | Victor S. Miller NERFINISHED ⓘ |
| publicationContext | work on elliptic curve cryptography in the 1980s ⓘ |
| relatedTo |
bilinear map properties
ⓘ
double-and-add scalar multiplication ⓘ |
| requires |
finite field arithmetic
ⓘ
group law on elliptic curves ⓘ |
| step |
maintains a running value of a rational function
ⓘ
updates function value using line functions from point addition ⓘ updates function value using line functions from point doubling ⓘ |
| usedFor |
computing pairings on elliptic curves
ⓘ
efficient pairing computation ⓘ evaluating bilinear pairings ⓘ evaluating the Tate pairing ⓘ evaluating the Weil pairing ⓘ |
| usedIn | security proofs and constructions in pairing-based cryptography ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.