In cryptography, FourQ is an elliptic curve developed by Microsoft Research. It is designed for key agreements schemes (elliptic curve Diffie-Hellman) and digital signatures (Schnorr), and offers about 128 bits of security. It is equipped with a reference implementation made by the authors of the original paper. The open source implementation is called FourQlib and runs on Windows and Linux and is available for x86, x64, and ARM. It is licensed under MIT License and the source code is available on GitHub.
Its name is derived from the four dimensional Gallant-Lambert-Vanstone scalar multiplication, which allows high performance calculations. The curve is defined over a two dimensional extension of the prime field defined by the Mersenne prime .
The curve is defined by a twisted Edwards equation
is a non-square in , where is the Mersenne prime .
Most cryptographic primitives, and most notably ECDH, require fast computation of scalar multiplication, i.e. for a point on the curve and an integer .
Hence, for a given we may write
If we find small , we may compute quickly by utilizing the implied equation
Both properties (four dimensional decomposition and Mersenne prime characteristic), alongside usage of fast multiplication formulae (extended twisted Edwards coordinates), make FourQ the currently fastest elliptic curve for the 128 bit security level.
This section is missing information about uses.July 2019)(
- Costello, Craig; Longa, Patrick (2015). "FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime". Retrieved 23 May 2019. Cite journal requires
- "FourQlib". Microsoft Research. Retrieved 23 May 2019.
- Longa, Patrick; Sica, Francesco (2011). "Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication". arXiv:1106.5149. Retrieved 23 May 2019. Cite journal requires
- "draft-ladd-cfrg-4q-01". datatracker.ietf.org. Retrieved 23 May 2019.
- van Oorschot, Paul C.; Wiener, Michael J. (1996). "On Diffie-Hellman Key Agreement with Short Exponents". Advances in Cryptology – EUROCRYPT '96. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1070: 332–343. doi:10.1007/3-540-68339-9_29. ISBN 978-3-540-61186-8.
- Babai, L. (1 March 1986). "On Lovász' lattice reduction and the nearest lattice point problem". Combinatorica. 6 (1): 1–13. doi:10.1007/BF02579403. ISSN 1439-6912.
- "Introducing CIRCL". blog.cloudflare.com. Retrieved 28 July 2019.