Further refinements of Miller's algorithm on Edwards curves

DOI10.1007/S00200-015-0278-ZMaRDI QIDQ300877zbMATH OpenOpenAlexFDO

Authors Duc-Phong Le, Chik How Tan

Publication date 29 June 2016

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2694

zbMATH Keywords

Edwards curvesMiller's algorithmpairing computationTate/Weil pairings

Mathematics Subject Classification ID

Cryptography (94A60) Elliptic curves over local fields (11G07) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Abstract: Recently, Edwards curves have received a lot of attention in the cryptographic community due to their fast scalar multiplication algorithms. Then, many works on the application of these curves to pairing-based cryptography have been introduced. Xu and Lin (CT-RSA, 2010) presented refinements to improve the Miller algorithm that is central role compute pairings on Edwards curves. In this paper, we study further refinements to Miller algorithm. Our approach is generic, hence it allow to compute both Weil and Tate pairings on pairing-friendly Edwards curves of any embedding degree. We analyze and show that our algorithm is faster than the original Miller algorithm and the Xu-Lin's refinements.

Recommendations

• Refinement of Miller's algorithm over Edwards curves
• Refinements of Miller's algorithm for computing the Weil/Tate pairing
• Further refinement of pairing computation based on Miller's algorithm
• Faster computation of the Tate pairing
• A variant of Miller's formula and algorithm

Cites work

• scientific article; zbMATH DE number 1643939 (Why is no real title available?)
• scientific article; zbMATH DE number 1942431 (Why is no real title available?)
• scientific article; zbMATH DE number 1842494 (Why is no real title available?)
• A complete set of addition laws for incomplete Edwards curves
• A variant of Miller's formula and algorithm
• Another Approach to Pairing Computation in Edwards Coordinates
• Efficient pairing computation on supersingular abelian varieties
• Faster Addition and Doubling on Elliptic Curves
• Faster computation of the Tate pairing
• Faster pairing computations on curves with high-degree twists
• Improved Miller’s Algorithm for Computing Pairings on Edwards Curves
• Inverted Edwards Coordinates
• Optimal Pairings
• Pairing Computation on Twisted Edwards Form Elliptic Curves
• Pairing Lattices
• Pairing-Friendly Elliptic Curves of Prime Order
• Refinement of Miller's algorithm over Edwards curves
• Refinements of Miller's algorithm for computing the Weil/Tate pairing
• The Eta Pairing Revisited
• The Weil pairing, and its efficient calculation
• Twisted Edwards Curves
• Twisted Edwards Curves Revisited

Cited in

(7)

• Refinements of Miller's algorithm for computing the Weil/Tate pairing
• Pairing computation on Edwards curves with high-degree twists
• A variant of Miller's formula and algorithm
• Refinement of Miller's algorithm over Edwards curves
• Application of scalar multiplication of Edwards curves to pairing-based cryptography
• Further refinement of pairing computation based on Miller's algorithm
• The contribution of W. L. Edge to the study of Humbert’s curves

This page was built for publication: Further refinements of Miller's algorithm on Edwards curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300877)