Cryptology ePrint Archive: Report 2010/542

Squaring in cyclotomic subgroups

Koray Karabina

Abstract: We propose new squaring formulae for cyclotomic subgroups of certain finite fields. Our formulae use a compressed representation of elements having the property that decompression can be performed at a very low cost. The squaring formulae lead to new exponentiation algorithms in cyclotomic subgroups which outperform the fastest previously-known exponentiation algorithms when the exponent has low Hamming weight. Our algorithms can be adapted to accelerate the final exponentiation step of pairing computations.

Category / Keywords: public-key cryptography / Cyclotomic subgroups, squaring, pairing-based cryptography

Date: received 22 Oct 2010, last revised 22 Oct 2010

Contact author: kkarabin at uwaterloo ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20101025:151152 (All versions of this report)

Short URL: ia.cr/2010/542

Discussion forum: Show discussion | Start new discussion