Paper 2015/565

FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime

Craig Costello and Patrick Longa

Abstract

We introduce FourQ, a high-security, high-performance elliptic curve that targets the 128-bit security level. At the highest arithmetic level, cryptographic scalar multiplications on FourQ can use a four-dimensional Gallant-Lambert-Vanstone decomposition to minimize the total number of elliptic curve group operations. At the group arithmetic level, FourQ admits the use of extended twisted Edwards coordinates and can therefore exploit the fastest known elliptic curve addition formulas over large prime characteristic fields. Finally, at the finite field level, arithmetic is performed modulo the extremely fast Mersenne prime $p=2^{127}-1$. We show that this powerful combination facilitates scalar multiplications that are significantly faster than all prior works. On Intel's Broadwell, Haswell, Ivy Bridge and Sandy Bridge architectures, our software computes a variable-base scalar multiplication in 50,000, 56,000, 69,000 cycles and 72,000 cycles, respectively; and, on the same platforms, our software computes a Diffie-Hellman shared secret in 80,000, 88,000, 104,000 cycles and 112,000 cycles, respectively. These results show that, in practice, FourQ is around four to five times faster than the original NIST P-256 curve and between two and three times faster than curves that are currently under consideration as NIST alternatives, such as Curve25519.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Contact author(s)
craigco @ microsoft com
plonga @ microsoft com
History
2016-09-22: last of 5 revisions
2015-06-17: received
See all versions
Short URL
https://ia.cr/2015/565
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/565,
      author = {Craig Costello and Patrick Longa},
      title = {FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime},
      howpublished = {Cryptology ePrint Archive, Paper 2015/565},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/565}},
      url = {https://eprint.iacr.org/2015/565}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.