Hello there!

B-SIDH, the twist-agnostic SIDH protocol

In the B-SIDH protocol proposed by Costello in [4], Alice and Bob work in the (p + 1)- and (p - 1)-torsion of a set of supersingular curves defined over 𝔽p2 and the set of their quadratic twist, respectively. In summary, B-SIDH can be viewed as a twist agnostic of SIDH protocol 1, which allows an optimized isogeny and Montgomery arithmetic by only using the x-coordinate of the points along with the A coefficient of the curve.

Let E / 𝔽p2 : By2 = x3 + Ax2 + x be a supersingular elliptic curve with (p+1)2 rational points, two rational points Pa, Qa ∊ E[ p + 1] of order M, and two zero-trace 𝔽p4-rational points Pb, Qb ∊ E[ p - 1] of order N. Now, let’s denote by E / ᐸRᐳ to the co-domain curve of the separable isogeny ɸ : E ⟶ E / ᐸRᐳ with kernel generated by R. Then, B-SIDH can be summarized as follows:

Alice Bob
ska ⟵ {0, …, M - 1}
Ra = Pa + [ska]Qa
ɸa : E ⟶ E / ᐸRaᐳ
Ea = E / ᐸRaᐳ

Ea, ɸa(Pb), ɸa(Qb)
―――――――ᐳ


Eb, ɸb(Pa), ɸb(Qa)
ᐸ―――――――		 skb ⟵ {0, …, N - 1}
Rb = Pb + [skb]Qb
ɸb : E ⟶ E / ᐸRbᐳ
Eb = E / ᐸRbᐳ
Ea,b = Eb / ᐸɸb(Ra)ᐳ Ea,b = Ea / ᐸɸa(Rb)ᐳ

The protocol flow of B-SIDH must perform two main phases, namely, key generation (keygen) and secret sharing (derive). In practice, the keygen block performs the isogeny evaluation of the projectivized x-coordinate points x(P), x(Q), and x(P - Q) 2. Thus for B-SIDH, derive is significantly cheaper than keygen. However, the most important challenge in any implementation of B-SIDH corresponds with the high computational cost associated with the large degree of isogenies involved in its execution 3; in contrast, B-SIDH also allows to work over smaller fields than SIDH does.

Regarding B-SIDH security, the task of an attacker is to find an isogeny between two supersingular curves E1 / 𝔽p2 and E2 / 𝔽p2, and the best classical and quantum procedures to forge it are the Delfs-Galbraith [8] algorithm and its quantum adaptation due to Biasse-Jao-Sankar [3], which have a running time of O(p½) and O(p¼) with “negligible” memory requirements, respectively.

References
[1] G. Adj, J.-J. Chi-Domínguez, F. Rodríguez-Henríquez, Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols. IACR Cryptol. ePrint Arch., 2020: 1109 (2020) 🔗.
[2] D. J. Bernstein, L. De Feo, A. Leroux, B. Smith, Faster computation of isogenies of large prime degree. IACR Cryptol. ePrint Arch., 2020: 341 (2020) 🔗.
[3] J.-F. Biasse, D. Jao, and A. Sankar, A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves, Progress in Cryptology - INDOCRYPT 2014, LNCS 8885, 428-442, 2014 🔗.
[4] C. Costello, B-SIDH: Supersingular Isogeny Diffie-Hellman Using Twisted Torsion. Advances in Cryptology - ASIACRYPT 2020, LNCS 12492, 440-463, 2020 🔗.
[5] C. Costello, Hüseyin Hisil, A Simple and Compact Algorithm for SIDH with Arbitrary Degree Isogenies. Advances in Cryptology - ASIACRYPT 2017, LNCS 10625, 303-329, 2017 🔗.
[6] L. De Feo, and D. Jao, Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. Post-Quantum Cryptography - PQCrypto 2011, LNCS 7071, 19-34, 2011 🔗.
[7] L. De Feo, D. Jao, and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Journal of Mathematical Cryptology, 8 (3), 209-247, 2014 🔗.
[8] C. Delfs, and S. D. Galbraith, Computing isogenies between supersingular elliptic curves over 𝔽p, Designs, Codes and Cryptography, 78 (2), 425-400, 2016 🔗.

  1. For more details regarding the SIDH protocol, to read [6] and [7]. ↩

  2. Here, P ∊ {Pa, Pb}, and Q ∊ {Qa, Qb}. ↩

  3. You can deep into the isogeny constructions/evaluations on Montgomery curves by reading [5] and [2, 1] for the traditional and the new sqrt Vélu formulæ, respectively. ↩