View source for FourQ

{{Use dmy dates|date=July 2019}}
{{Infobox software
| name                   = FourQ
| title                  = FourQ
| logo                   = 
| screenshot             = 
| caption                = 
| developer              = [[Microsoft Research]]
| released               = {{Start date and age|2015}}
| discontinued           = 
| latest release version = v3.1
| latest release date    = 
| repo                   = {{URL|https://github.com/microsoft/FourQlib}}
| programming language   = [[C (programming language)|C]]
| operating system       = [[Windows 10]], [[Linux]]
| platform               = [[IA-32]], [[x86-64]], [[ARM32]], [[ARM64]]
| size                   = 
| genre                  = [[elliptic-curve cryptography|Elliptic-curve]] cryptographic library
| license                = [[MIT License]]
| website                = {{URL|https://www.microsoft.com/en-us/research/project/fourqlib/}}
}}
In [[cryptography]], '''FourQ''' is an [[elliptic-curve cryptography|elliptic curve]] developed by [[Microsoft Research]]. It is designed for key agreements schemes ([[elliptic-curve Diffie–Hellman]]) and digital signatures ([[Schnorr signature|Schnorr]]), and offers about 128 [[Security level|bits of security]].<ref name="4q">{{cite journal |last1=Costello |first1=Craig |last2=Longa |first2=Patrick |title=FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime |year=2015 |url=https://eprint.iacr.org/2015/565 |access-date=23 May 2019 }}</ref> 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.<ref name="msf">{{cite web |title=FourQlib |url=https://www.microsoft.com/en-us/research/project/fourqlib/ |website=Microsoft Research |access-date=23 May 2019}}</ref> It is licensed under the [[MIT License]] and the source code is available on [[GitHub]].<ref>{{Cite web|url=https://github.com/microsoft/FourQlib|title = References| website=[[GitHub]] |date = 4 October 2021}}</ref>

Its name is derived from the four dimensional Gallant–Lambert–Vanstone scalar multiplication, which allows high performance calculations.<ref>{{cite journal |last1=Longa |first1=Patrick |last2=Sica |first2=Francesco |title=Four-Dimensional Gallant–Lambert–Vanstone Scalar Multiplication |access-date=23 May 2019 |year=2011 |url=https://eprint.iacr.org/2011/608|arxiv=1106.5149 }}</ref> The curve is defined over a two dimensional [[field extension|extension]] of the [[Prime number|prime]] field defined by the [[Mersenne prime]] <math>2^{127} - 1</math>.

== History ==
The curve was published in 2015 by Craig Costello and Patrick Longa from [[Microsoft Research]] on [[Cryptology ePrint Archive|ePrint]].<ref name="4q"/>

The paper was presented in [[Asiacrypt]] in 2015 in [[Auckland]], New Zealand, and consequently a [[reference implementation]] was published on [[Microsoft]]'s website.<ref name="msf"/>

There were some efforts to standardize usage of the curve under [[IETF]]; these efforts were withdrawn in late 2017.<ref>{{cite journal |title=draft-ladd-cfrg-4q-01 |url=https://datatracker.ietf.org/doc/draft-ladd-cfrg-4q/ |newspaper=Ietf Datatracker |date=27 March 2017 |access-date=23 May 2019|last1=Ladd |first1=Watson |last2=Longa |first2=Patrick |last3=Barnes |first3=Richard }}</ref>

== Mathematical properties ==
The curve is defined by a [[twisted Edwards curve|twisted Edwards equation]]
:<math>-x^2 + y^2 = 1 + d x^2 y^2</math>
<math>d</math> is a non-square in <math>\mathbb{F}_{p^2}</math>, where <math>p</math> is the [[Mersenne prime]] <math>2^{127}-1</math>.

In order to avoid [[Small subgroup confinement attack|small subgroup attacks]],<ref>{{cite book |last1=van Oorschot |first1=Paul C. |last2=Wiener |first2=Michael J. |title=Advances in Cryptology — EUROCRYPT '96 |chapter=On Diffie-Hellman Key Agreement with Short Exponents |volume=1070 |year=1996 |pages=332–343 |doi=10.1007/3-540-68339-9_29 |publisher=Springer Berlin Heidelberg |series=Lecture Notes in Computer Science |isbn=978-3-540-61186-8 |doi-access=free }}</ref> all points are verified to lie in an ''N''-[[Torsion subgroup|torsion]] subgroup of the [[elliptic curve]], where ''N'' is specified as a 246-bit [[Prime number|prime]] dividing the [[Order (group theory)|order]] of the group.

The curve is equipped with two nontrivial [[endomorphism]]s: <math>\psi</math> related to the <math>p</math>-power [[Frobenius map]], and  <math>\phi</math>, a low degree efficiently computable endomorphism (see [[complex multiplication]]).

== Cryptographic properties ==
=== Security ===
The currently best known [[discrete logarithm]] attack is the generic [[Pollard's rho algorithm]], requiring about <math>2^{122.5}</math> group operations on average. Therefore, it typically belongs to the 128 bit security level.

In order to prevent [[timing attack]]s, all group operations are done in constant time, i.e. without disclosing information about key material.<ref name="4q"/>

=== Efficiency ===
Most cryptographic primitives, and most notably [[Elliptic-curve Diffie–Hellman|ECDH]], require fast computation of scalar multiplication, i.e. <math>[k]P</math> for a point <math>P</math> on the curve and an integer <math>k</math>, which is usually thought as distributed uniformly at random over <math>\{0, \ldots, N-1\}</math>.

Since we look at a [[Prime number|prime]] order [[cyclic group|cyclic]] subgroup, one can write scalars <math>\lambda_\psi, \lambda_\phi</math> such that <math>\psi(P) = [\lambda_\psi]P</math> and <math>\phi(P) = [\lambda_\phi]P</math> for every point <math>P</math> in the ''N''-torsion subgroup.

Hence, for a given <math>k</math> we may write
:<math>k = a_1 + a_2 \lambda_\phi + a_3 \lambda_\psi + a_4 \lambda_\phi\lambda_\psi \pmod N</math>
If we find small <math>a_i</math>, we may compute <math>[k]P</math> quickly by utilizing the implied equation
:<math>[k]P = [a_1]P + [a_2] \phi(P) + [a_3] \psi(P) + [a_4] \phi(\psi(P))</math>
[[Babai rounding]] technique<ref>{{cite journal |last1=Babai |first1=L. |title=On Lovász' lattice reduction and the nearest lattice point problem |journal=Combinatorica |date=1 March 1986 |volume=6 |issue=1 |pages=1–13 |doi=10.1007/BF02579403 |s2cid=7914792 |issn=1439-6912}}</ref> is used to find small <math>a_i</math>. For FourQ it turns that one can guarantee an efficiently computable solution with <math>a_i < 2^{64}</math>.

Moreover, as the [[Characteristic (algebra)|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 ([[Twisted Edwards curve|extended twisted Edwards]] coordinates), make FourQ the currently fastest elliptic curve for the 128 bit security level.

== Uses ==
{{Missing information|section|uses|date=July 2019}}

FourQ is implemented in the cryptographic library [https://github.com/cloudflare/circl CIRCL], published by [[Cloudflare]].<ref>{{cite web |title=Introducing CIRCL |url=https://blog.cloudflare.com/introducing-circl/ |website=blog.cloudflare.com |date=20 June 2019 |access-date=28 July 2019}}</ref>

== See also ==
* [[Elliptic-curve cryptography]]
* [[Curve25519]]
* [[Curve448]]

== References ==
{{Reflist}}

== External links ==
* [https://www.microsoft.com/en-us/research/project/fourqlib/ Reference implementation by Microsoft]

{{Microsoft FOSS}}

[[Category:Elliptic curve cryptography]]
[[Category:Microsoft free software]]
[[Category:Software using the MIT license]]