Please use this identifier to cite or link to this item:
https://doi.org/10.1093/comjnl/bxr039
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. https://doi.org/10.1093/comjnl/bxr039 | 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 | URI: | http://scholarbank.nus.edu.sg/handle/10635/111473 | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.