EllipticalCurveCryptography_StudyNotes

An elliptic curve equation takes one of several standard forms, including (but not limited to) Weierstrass, Montgomery, and Edwards.

The curve E induces an algebraic group whose elements are those points with coordinates (x, y) satisfying the curve equation, and where x and y are elements of F.  
This group has order n, meaning that there are n distinct points. Elliptic curves induce subgroups of prime order.

E : y^2 = x^3 + A * x + B,
where A, B are in F_p and satisfies 4 * A^3 + 27 * B^2 != 0 mod p.

Solutions (x,y) for an elliptic curve E, as well as the point at infinity, O_E are called the F_p rational points. 
If P and Q are two points on the curve E, we can define R = P + Q as the opposite point of the intersection between the curve E and the line that intersects P and Q. We can define P + O_E = P = O_E + P as well. 

O_E: the point at infinity over an elliptic curve E.
#E(F_p): number of points on an elliptic curve E over F_p.
h: a cofactor such that h = #E(F_p)/r.
k: an embedding degree, a minimum integer such that r is a divisor of p^k - 1.

Mappings in Elliptic Curves

In general, the set of all points that mapping can produce overall possible inputs may be only a subset of the points on an elliptic curve (i.e., the mapping may not be surjective).  
In addition, a mapping may output the same point for two or more distinct inputs (i.e., the mapping may not be injective).

For example, consider a mapping from F to an elliptic curve having n points: if the number of elements of F is not equal to n, then this mapping cannot be bijective (i.e., both injective and surjective) since it is defined to be deterministic.

Encodings in Elliptic Curves

Encodings are closely related to mappings. As a mapping, encoding is a function that outputs a point on an elliptic curve. In contrast to a mapping, however, the input to encoding is an arbitrary string.  Encodings can be deterministic or probabilistic. Deterministic encodings are preferred for security because probabilistic ones are more likely to leak information through side channels.

Two different types of encodings are possible: nonuniform encodings, whose output distribution is not uniformly random, and random oracle encodings, whose output distribution is indistinguishable from uniformly random.

Serialization and Deserialisation of Elliptic Curves 

Random Oracles

Cryptographic protocols that use random oracles are often analyzed under the assumption that random oracles answer only queries generated by that protocol.  In practice, this assumption does not hold if two protocols query the same random oracle.

Domain Separation in Random Oracles

Allowing a single random oracle to simulate multiple independent oracles. 

Endomorphism Rings

The endomorphism ring End(E) of E consists of morphisms from E to itself that are also group homomorphisms on its points. If E is supersingular, then End(E) is an order in a quaternion algebra. If E is ordinary, then End(E) is an order in an imaginary quadratic field. 





Twist Security

Quadratic twist needs to have a large enough prime divisor for the discrete logarithm problem to be hard enough. This prevents an invalid-curve attack in which an attacker obtains multiples with secret values of a point on the quadratic twist. 

Pairing based cryptography

Pairing is a special map defined over elliptic curves. Generally, elliptic curves are defined so that pairing is not efficiently computable since elliptic curve cryptography is broken if the pairing is efficiently computable. As the importance of pairing grows, elliptic curves where pairing is efficiently computable are studied and the special curves called pairing-friendly curves are proposed.

Applications of pairing-based cryptography

Identity-based cryptography
Certificateless signatures
Sasaki Kasahara Key Encryption (SAKKE)
Identity-Based Authenticated Key Exchange (IBAKE)
Multimedia Internet Keying (MIKEY)
Identity based key agreement schemes
Multi-Factor Authentication Protocol (M-Pin)
Elliptic Curve Direct Anonymous Attestation (ECDAA)

ECDAA is used for the Trusted Platform Module (TPM). CDAA is a protocol for proving the attestation held by a TPM to a verifier without revealing the attestation held by that TPM. Pairing is used for constructing ECDAA.

DFNITY utilized a threshold signature scheme to generate the decentralized random beacons. They constructed a BLS signature scheme which is based on pairings. 

Ethereum 2.0 applies signature aggregation for scalability benefits by leveraging DFINITY random beacon chain playground. 

Pairing friendly elliptic curves

A cryptographic pairing is a bilinear map between two groups in which the discrete logarithm problem is hard. The cryptographic pairings used to construct these systems in practice are based on the Weil and Tate pairings on elliptic curves over finite fields.  Pairing is a kind of the bilinear map defined over an elliptic curve. Examples include Weil pairing, Tate pairing, optimal Ate pairing. Especially, optimal Ate pairing is considered to be efficient to compute and mainly used for practical implementation.

These pairings are bilinear maps from an elliptic curve group E(Fq) to the multiplicative group of some extension field. Fq k. The parameter k is called the embedding degree of the elliptic curve. The pairing is considered to be secure if taking discrete logarithms in the groups E(Fq) and F ∗ q k are both computationally infeasible.


Cycles of pairing friendly elliptic curves

A list of elliptic curves over finite fields such that the number of points on one curve is equal to the size of the field of definition of the next, in a cyclic way.  Example - MNT curves of cycle length 4

Cycles of composite order elliptic curves cannot exist.

History of cycles of elliptic curves - aliquot cycles. Two cycles of ordinary curves are known as amicable pairs, introduced in the context of primality proving. 

A pairing-friendly 2-cycle can be obtained from pairing-friendly prime-order curves of embedding degrees 4 and 6

MNT Curves - Miyaji, Nakabayashi, Takano

Pairing friendly elliptic curves

MNT Curves
Freeman Curves
Baretto Naehrig Curves

Curves in the cycle have different security levels

BLS12-381

Hashing to the groups of the bilinear pairings

BLS12-381 widely adopted in pairing friendly SNARKs, GGPR13, PHGR13, BCTV14, Gro16.

BLS signature scheme requires a hash function to the points in the prime order subgroups of a pairing friendly elliptic curve. A folklore method, Map to Group, Hash to Check

Pick a random element in the elliptic curve’s base field and check whether it is the x-coordinate of a rational point on the curve.  If it is, return the point, otherwise try again. 

It is not possible to make hash and check run in constant time. 
For BLS signatures, a constant time hash function is not strictly necessary. 

A constant size hash function is always desirable against future misuse.
Deterministic mapping to rational points in elliptic curve
Evaluating the map requires evaluating Legendre symbols 

Shallue–van de Woestijne map

Barreto-Lynn-Scott and other pairing-friendly curves, one group of the bilinear pairing is a subgroup of an elliptic curve over an even-order extension field 

Hessian curves and hyperelliptic curves
Injective encodings to elliptic curves
Distortion Maps and Supersingular Elliptic Curves

Hash functions to curves as random oracles

Icart Maps

Primitives 

BLS Signature - Boneh, Lynn, Schacham
Boneh Franklin Encryption
Baretto - Lynn - Scott (BLS) family

References :

Hash to Elliptic Curves
https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-07

Pairing friendly elliptic curves
https://tools.ietf.org/id/draft-yonezawa-pairing-friendly-curves-00.html