Isogeny-Based Key Agreement Clause Samples

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 ▇▇▇▇▇▇▇▇▇ [15], based on isogenies between ordinary elliptic curves, was subsequently shown by ▇▇▇▇▇▇, Jao, and ▇▇▇▇▇▇▇▇▇ [6] to offer only subexponential difficulty against quantum computers. The algorithm has recently been further improved by ▇▇▇▇▇▇▇▇▇ [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 ]. ▇▇▇▇▇ 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 . ▇▇▇▇▇ 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 ▇▇▇, ▇▇▇▇▇ computes an isogeny φ0A : EB EAB having kernel equal to [mA]φB(PA) + [nA]φB(QA) ; Bob proceeds symmetrically. ▇▇▇▇▇ and ▇▇▇ can then use the common j-invariant of EAB = φ0B(φA(E)) = φ0A(φB(E)...