FourQ

FourQDeveloper(s)| Microsoft Research

|

Initial release| 2015; 11 years ago (2015)
Stable release|

v3.1

Repository| github.com/microsoft/FourQlib
Written in| C
Operating system| Windows 10, Linux
Platform| IA-32, x86-64, ARM32, ARM64
Type| Elliptic-curve cryptographic library
License| MIT License
Website| www.microsoft.com/en-us/research/project/fourqlib/

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.[1] 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.[2] It is licensed under the MIT License and the source code is available on GitHub.[3]

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 2127−1.

## Contents

* 1 History
* 2 Mathematical properties
* 3 Cryptographic properties
* 3.1 Security
* 3.2 Efficiency
* 4 Uses
* 5 See also
* 6 References
* 7 External links

## History

The curve was published in 2015 by Craig Costello and Patrick Longa from Microsoft Research on ePrint.[1]

The paper was presented in Asiacrypt in 2015 in Auckland, New Zealand, and consequently a reference implementation was published on Microsoft's website.[2]

There were some efforts to standardize usage of the curve under IETF; these efforts were withdrawn in late 2017.[5]

## Mathematical properties

The curve is defined by a twisted Edwards equation

−x2+y2=1+dx2y2

d is a non-square in 𝔽p2, where p is the Mersenne prime 2127−1.

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 p-power Frobenius map, and ϕ, 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 2122.5 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. [k]P for a point P on the curve and an integer k, which is usually thought as distributed uniformly at random over {0,…,N−1}.

Since we look at a prime order cyclic subgroup, one can write scalars λψ,λϕ such that ψ(P)=[λψ]P and ϕ(P)=[λϕ]P for every point P in the N-torsion subgroup.

Hence, for a given k we may write

k=a1+a2λϕ+a3λψ+a4λϕλψ(modN)

If we find small ai, we may compute [k]P quickly by utilizing the implied equation

[k]P=[a1]P+[a2]ϕ(P)+[a3]ψ(P)+[a4]ϕ(ψ(P))

Babai rounding technique[7] is used to find small ai. For FourQ it turns that one can guarantee an efficiently computable solution with ai<264.

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. Please expand the section to include this information. Further details may exist on the talk page. (July 2019)

|

FourQ is implemented in the cryptographic library CIRCL, published by Cloudflare.[8]

## See also

* Elliptic-curve cryptography
* Curve25519
* Curve448

## References

1. ↑ 1.0 1.1 1.2 Costello, Craig; Longa, Patrick (2015). FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime. https://eprint.iacr.org/2015/565. Retrieved 23 May 2019.
2. ↑ 2.0 2.1 "FourQlib". https://www.microsoft.com/en-us/research/project/fourqlib/.
3. ↑ "References". 4 October 2021. https://github.com/microsoft/FourQlib.
4. ↑ Longa, Patrick; Sica, Francesco (2011). Four-Dimensional Gallant–Lambert–Vanstone Scalar Multiplication. https://eprint.iacr.org/2011/608. Retrieved 23 May 2019.
5. ↑ Ladd, Watson; Longa, Patrick; Barnes, Richard (27 March 2017). draft-ladd-cfrg-4q-01. https://datatracker.ietf.org/doc/draft-ladd-cfrg-4q/. Retrieved 23 May 2019.
6. ↑ 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. 1070. Springer Berlin Heidelberg. pp. 332–343. doi:10.1007/3-540-68339-9_29. ISBN 978-3-540-61186-8.
7. ↑ 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.
8. ↑ "Introducing CIRCL". 20 June 2019. https://blog.cloudflare.com/introducing-circl/.

## External links

* Reference implementation by Microsoft

* v
* t
* e

Microsoft free and open-source software (FOSS)

Overview|

* Microsoft and open source
* Shared Source Initiative

Software|

| Applications|

* Atom
* Conference XP
* File Manager
* Open Live Writer
* PowerToys for Windows 10
* Windows Calculator
* Windows Console
* Windows Terminal
* WorldWide Telescope
* XML Notepad

|

Video games|

* Allegiance

Programming languages|

* Bosque
* C#
* Dafny
* F#
* F*
* IronPython
* IronRuby
* P
* PowerShell
* Q#
* R Open
* Small Basic
* TypeScript
* Visual Basic .NET

Frameworks and
development tools|

* .NET Bio
* .NET Core
* .NET Framework
* .NET Micro Framework
* AirSim
* ASP.NET
* ASP.NET AJAX
* ASP.NET Core
* ASP.NET MVC
* ASP.NET Razor
* ASP.NET Web Forms
* Blazor
* C++/WinRT
* ChakraCore
* CLR Profiler
* DiskSpd
* Dryad
* Electron
* Entity Framework
* Managed Extensibility Framework
* Microsoft Automatic Graph Layout
* Microsoft Cognitive Toolkit
* Microsoft Detours
* ML.NET
* Mono
* MonoDevelop
* MSBuild
* NuGet
* Open Management Infrastructure
* Orleans
* ProcDump
* R Tools for Visual Studio
* Roslyn
* Sandcastle
* SignalR
* StyleCop
* SVNBridge
* T2 Temporal Prover
* Text Template Transformation Toolkit
* vcpkg
* Virtual File System for Git
* Visual Studio Code
* Windows Communication Foundation
* Windows Driver Frameworks
* Windows Forms
* Windows Presentation Foundation
* Windows Template Library
* WinJS
* WiX
* Z3 Theorem Prover

Operating systems|

* MS-DOS
* Barrelfish

Licenses|

* Microsoft Public License
* Microsoft Reciprocal License

Related|

* .NET Foundation
* F Sharp Software Foundation
* Microsoft Open Specification Promise
* Outercurve Foundation

Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/FourQ. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=FourQ&oldid=4345173"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template