FourQ
Developer(s) | Microsoft Research |
---|---|
Initial release | 2015 |
Stable release | v3.1
|
ARM64 | |
Type | Elliptic-curve cryptographic library |
License | MIT License |
Website | www |
In
Its name is derived from the four dimensional Gallant–Lambert–Vanstone scalar multiplication, which allows high performance calculations.[4] The curve is defined over a two dimensional extension of the prime field defined by the Mersenne prime .
History
The curve was published in 2015 by Craig Costello and Patrick Longa from Microsoft Research on ePrint.[1]
The paper was presented in
There were some efforts to standardize usage of the curve under
Mathematical properties
The curve is defined by a twisted Edwards equation
is a non-square in , where is the Mersenne prime .
In order to avoid small subgroup attacks,[6] all points are verified to lie in an N-torsion subgroup of the elliptic curve, where N is specified as a 246-bit prime dividing the order of the group.
The curve is equipped with two nontrivial endomorphisms: related to the -power
Cryptographic properties
Security
The currently best known discrete logarithm attack is the generic Pollard's rho algorithm, requiring about group operations on average. Therefore, it typically belongs to the 128 bit security level.
In order to prevent timing attacks, all group operations are done in constant time, i.e. without disclosing information about key material.[1]
Efficiency
Most cryptographic primitives, and most notably ECDH, require fast computation of scalar multiplication, i.e. for a point on the curve and an integer , which is usually thought as distributed uniformly at random over .
Since we look at a prime order cyclic subgroup, one can write scalars such that and for every point in the N-torsion subgroup.
Hence, for a given we may write
If we find small , we may compute quickly by utilizing the implied equation
Babai rounding technique[7] is used to find small . For FourQ it turns that one can guarantee an efficiently computable solution with .
Moreover, as the characteristic of the field is a Mersenne prime, modulations can be carried efficiently.
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.
Uses
This section is missing information about uses.(July 2019) |
FourQ is implemented in the cryptographic library CIRCL, published by Cloudflare.[8]
See also
References
- ^ a b c Costello, Craig; Longa, Patrick (2015). "FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime". Retrieved 23 May 2019.
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ a b "FourQlib". Microsoft Research. Retrieved 23 May 2019.
- ^ "References". GitHub. 4 October 2021.
- )
- ^ Ladd, Watson; Longa, Patrick; Barnes, Richard (27 March 2017). "draft-ladd-cfrg-4q-01". Ietf Datatracker. Retrieved 23 May 2019.
- ISBN 978-3-540-61186-8.
- S2CID 7914792.
- ^ "Introducing CIRCL". blog.cloudflare.com. 20 June 2019. Retrieved 28 July 2019.