Examine individual changes

[ 0 => '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 |date=2015 |url=https://eprint.iacr.org/2015/565 |accessdate=23 May 2019 }}</ref> It is equipped with a [[reference implementation]] made by the authors of the original paper.<ref name="msf">{{cite web |title=FourQlib |url=https://www.microsoft.com/en-us/research/project/fourqlib/ |website=Microsoft Research |accessdate=23 May 2019}}</ref>', 1 => false, 2 => '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 |accessdate=23 May 2019 |date=2011 |url=https://eprint.iacr.org/2011/608}}</ref> The curve is defined over a two dimensional [[field extension|extension]] of the [[prime]] field defined by the [[Mersenne prime]] <math>2^{127} - 1</math>.', 3 => false, 4 => '== History ==', 5 => 'The curve was published in [[2015]] by Craig Costello and Patrick Longa from [[Microsoft Research]] on [[Cryptology ePrint Archive|ePrint]].<ref name="4q"/>', 6 => false, 7 => '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"/>', 8 => false, 9 => 'There were some efforts to standardize usage of the curve under [[IETF]]; these efforts were withdrawn in late [[2017]].<ref>{{cite web |title=draft-ladd-cfrg-4q-01 |url=https://datatracker.ietf.org/doc/draft-ladd-cfrg-4q/ |website=datatracker.ietf.org |accessdate=23 May 2019}}</ref>', 10 => false, 11 => '== Mathematical Properties ==', 12 => 'The curve is defined by a [[twisted Edwards curve|twisted Edwards equation]]', 13 => ':<math>-x^2 + y^2 = 1 + d x^2 y^2</math>', 14 => '<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>.', 15 => false, 16 => 'In order to avoid [[Small subgroup confinement attack|small subgroup attacks]]<ref>{{cite journal |last1=van Oorschot |first1=Paul C. |last2=Wiener |first2=Michael J. |title=On Diffie-Hellman Key Agreement with Short Exponents |journal=Advances in Cryptology — EUROCRYPT ’96 |date=1996 |pages=332–343 |doi=10.1007/3-540-68339-9_29 |accessdate=23 May 2019 |url=https://link.springer.com/chapter/10.1007/3-540-68339-9_29 |publisher=Springer Berlin Heidelberg |language=en}}</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]] dividing the [[Order (group theory)|order]] of the group.', 17 => false, 18 => '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]]).', 19 => false, 20 => '== Cryptographic Properties ==', 21 => '=== Security ===', 22 => '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.', 23 => false, 24 => '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"/>', 25 => false, 26 => '=== Efficiency ===', 27 => '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>.', 28 => false, 29 => 'Since we look at a [[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.', 30 => false, 31 => 'Hence, for a given <math>k</math> we may write', 32 => ':<math>k = a_1 + a_2 \lambda_\phi + a_3 \lambda_\psi + a_4 \lambda_\phi\lambda_\psi \pmod N</math>', 33 => 'If we find small <math>a_i</math>, we may compute <math>[k]P</math> quickly by utilizing the implied equation', 34 => ':<math>[k]P = [a_1]P + [a_2] \phi(P) + [a_3] \psi(P) + [a_4] \phi(\psi(P))</math>', 35 => '[[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 |url=https://link.springer.com/article/10.1007/BF02579403 |accessdate=23 May 2019 |language=en |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>.', 36 => false, 37 => 'Moreover, as the [[Characteristic (algebra)|characteristic]] of the field is a [[Mersenne prime]], modulations can be carried efficiently.', 38 => false, 39 => '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.', 40 => false, 41 => '== Uses ==', 42 => '{{Missing information|section|uses|date=May 2019}}', 43 => false, 44 => '== See also ==', 45 => '*[[Elliptic-curve cryptography]]', 46 => '*[[Curve25519]]', 47 => '*[[Curve448]]', 48 => false, 49 => '==External links==', 50 => '* [https://www.microsoft.com/en-us/research/project/fourqlib/ Reference implementation by Microsoft]', 51 => false, 52 => '== References ==', 53 => '{{reflist}}', 54 => false, 55 => '[[Category:Elliptic curve cryptography]]' ]