The Algebraic Isogeny Model: A General Model with Applications to SQIsign and Key Exchanges

Summary

We introduce the Algebraic Isogeny Model (AIM): an algebraic model, akin to the Algebraic Group Model in the group setting, for isogenies and supersingular elliptic curves. This model is significantly more general than previous ones, such as the Algebraic Group Action Model: the AIM works with arbitrary isogenies over Fp2$$\mathbb {F}_{p^2}$$, rather than being limited to oriented ones, which gives considerably more power to the adversary.Within this model, we obtain three results. First, we show that any result in the AGAM can be lifted to the AIM, strengthening previous results against more powerful adversaries. Then, we prove that the SQIsign identification protocol is ID-sound: in turn, this implies that SQIsign is EUF-CMA secure in the Quantum Random Oracle Model, resolving (in the AIM) a long-standing open problem. Lastly, we establish the equivalence of the DLOG and CDH problems for all SIDH-derived key exchanges, such as M-SIDH, binSIDH, and terSIDH.