Further refinements of Miller's algorithm on Edwards curves

DOI10.1007/S00200-015-0278-ZzbMATH Open1368.94110arXiv1305.2694OpenAlexW1516979521MaRDI QIDQ300877FDOQ300877

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)

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.

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

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

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)

Cites Work

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

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)