Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- lattice basis reductionelliptic curvecurve9767
- Contact author(s)
- thomas pornin @ nccgroup com
- History
- 2020-04-20: received
- Short URL
- https://ia.cr/2020/454
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/454,
author = {Thomas Pornin},
title = {Optimized Lattice Basis Reduction In Dimension 2, and Fast Schnorr and {EdDSA} Signature Verification},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/454},
year = {2020},
url = {https://eprint.iacr.org/2020/454}
}
