Cryptology ePrint Archive: Report 2020/454

Optimized Lattice Basis Reduction In Dimension 2, and Fast Schnorr and EdDSA Signature Verification

Thomas Pornin

Abstract: We present an optimization of Lagrange's algorithm for lattice basis reduction in dimension 2. The optimized algorithm is proven to be correct and to always terminate with quadratic complexity; it uses more iterations on average than Lagrange's algorithm, but each iteration is much simpler to implement, and faster. The achieved speed is such that it makes application of the speed-up on ECDSA and EC Schnorr signatures described by Antipa et al worthwhile, even for very fast curves such as Ed25519. We applied this technique to signature verification in Curve9767, and reduced verification time by 30 to 33% on both small (ARM Cortex M0+ and M4) and large (Intel Coffee Lake with AVX2) architectures.

Category / Keywords: implementation / lattice basis reduction, elliptic curve, curve9767

Date: received 18 Apr 2020

Contact author: thomas pornin at nccgroup com

Available format(s): PDF | BibTeX Citation

Version: 20200420:093455 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]