Please use this identifier to cite or link to this item:
Title: Refinements of Miller's algorithm over Weierstrass curves revisited
Authors: Le, D.-P. 
Liu, C.-L.
Keywords: efficient computation
Miller's algorithm
Tate pairing
Weierstrass curves
Weil pairing
Issue Date: Oct-2011
Citation: Le, D.-P., Liu, C.-L. (2011-10). Refinements of Miller's algorithm over Weierstrass curves revisited. Computer Journal 54 (10) : 1582-1591. ScholarBank@NUS Repository.
Abstract: In 1986, Victor Miller described an algorithm for computing the Weil pairing in his unpublished manuscript. This algorithm has then become the core of all pairing-based cryptosystems. Many improvements of the algorithm have been presented. Most of them involve a choice of elliptic curves of a special form to exploit a possible twist during Tate pairing computation. Other improvements involve a reduction of the number of iterations in the Miller's algorithm. For the generic case, Blake, Murty and Xu proposed three refinements to Miller's algorithm over Weierstrass curves. Though their refinements, which only reduce the total number of vertical lines in Miller's algorithm, did not give an efficient computation as other optimizations, they can be applied for computing both Weil and Tate pairings on all pairing-friendly elliptic curves. In this paper, we extend the Blake-Murty-Xu's method and show how to perform an elimination of all vertical lines in Miller's algorithm during computation of Weil/Tate pairings, on general elliptic curves. Experimental results show that our algorithm is faster by ∼25% in comparison with the original Miller's algorithm.
Source Title: Computer Journal
ISSN: 00104620
DOI: 10.1093/comjnl/bxr039
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 12, 2021


checked on Oct 12, 2021

Page view(s)

checked on Oct 14, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.