Isogeny-Based Key Agreement Sample Clauses

Isogeny-Based Key Agreement. The term ECC (elliptic-curve cryptography) typically refers to cryptographic primi- tives and protocols whose security is based on the hardness of the discrete logarithm problem on elliptic curves. This hardness assumption is invalid against quantum com- puters [13]. Hence, traditional elliptic-curve cryptography is not a viable foundation for constructing quantum-resistant cryptosystems. As a result, alternative elliptic-curve cryptosystems based on hardness assumptions other than discrete logarithms have been proposed for use in settings where quantum resistance is desired. One early proposal by Xxxxxxxxx [15], based on isogenies between ordinary elliptic curves, was subse- quently shown by Xxxxxx, Xxx, and Xxxxxxxxx [6] to offer only subexponential difficulty AInput: A, B, sID IBnput: B mA, nA ∈R Z/4eA Z mB, nB ∈R Z/4eB Z → → φA : E EA = φB : E EB = ( ) ( ) E/ [mA]PA + [nA]QA E/ [mB]PB + [nB]QB A,sID,φA(PB),φA(QB),EA −B−,s−ID−,φ−(P− )−,φ−(−Q−),−E→ EAB := ←− − − − − − − −− := EB/([mA]φB(PA)+[nA]φB(QA)) EA/([mB]φA(PB)+[nB]φA(QB)) Output: j(EAB), sID Output: j(EBA), sID Fig. 1: Key Agreement protocol using isogenies on supersingular curves.

Isogeny-Based Key Agreement. The term ECC (elliptic-curve cryptography) typically refers to cryptographic primitives and protocols whose security is based on the hardness of the discrete logarithm problem on elliptic curves. This hardness assumption is invalid against quantum computers [13]. Hence, traditional elliptic-curve cryptography is not a viable foundation for con- structing quantum-resistant cryptosystems. As a result, alternative elliptic-curve cryptosystems based on hardness as- sumptions other than discrete logarithms have been proposed for use in settings where quantum resistance is desired. One early proposal by Xxxxxxxxx [15], based on isogenies between ordinary elliptic curves, was subsequently shown by Xxxxxx, Jao, and Xxxxxxxxx [6] to offer only subexponential difficulty against quantum computers. The algorithm has recently been further improved by Xxxxxxxxx [2]. In response to these developments, Jao, Pluˆt and De Feo [9] proposed a new collection of quantum-resistant public-key cryptographic protocols for entity authentication, key exchange, and public-key cryptography, based on the difficulty of computing isogenies between supersingular elliptic curves. We review here the most fundamental protocol in the collection - key exchange protocol, which forms the main building block for our proposed schemes. Fix a prime p of the form p = `eA `eB · f ± 1, where `A and `B are small primes, eA and eB are positive integers, and f is some (typically very small) cofactor. { } ⊂ { } { } { } A B Then, fx a supersingular curve E defned over Fp2 , and bases PA, QA and PB, QB which generate E[` ] and E[` ] respectively, so that PA, QA = E[`eA ] and PB, QB = E[`eB ]. Xxxxx chooses two random elements mA, nA R Z/`eA Z, not both divisible by `A, and computes an isogeny φA : E EA with kernel KA := [mA]PA + [nA]QA . Xxxxx also computes the points φA(PB), φA(QB) EA(Fp2 ) obtained by applying her secret isogeny φA to the basis PB, QB for E[`eB ], which are called auxiliary points, and sends these points to Bob together with EA. Similarly, Bob selects B eB → h i random elements mB, nB ∈R Z/`B Z, not both divisible by `B, and computes an isogeny φB : E → EB having kernel KB := h[mB]PB + [nB]QBi, along with the auxiliary points {φB(PA), φB(QA)}. Upon receipt of EB and φB(PA), φB(QA) ∈ EB(Fp2 ) from Xxx, Xxxxx computes an isogeny φ0A : EB EAB having kernel equal to [mA]φB(PA) + [nA]φB(QA) ; Bob proceeds symmetrically. Xxxxx and Xxx can then use the common j-invariant of EAB = φ0B(φA(E)) = φ0A(φB(E)...