Welcome to the resource topic for 2023/1433
Title:
A polynomial-time attack on instances of M-SIDH and FESTA
Authors: Wouter Castryck, Frederik Vercauteren
Abstract:The recent devastating attacks on SIDH rely on the fact that the protocol reveals the images \varphi(P) and \varphi(Q) of the secret isogeny \varphi : E_0 \rightarrow E on a basis \{P, Q\} of the N-torsion subgroup E_0[N] where N^2 > \deg(\varphi). To thwart this attack, two recent proposals, M-SIDH and FESTA, proceed by only revealing the images upto unknown scalars \lambda_1, \lambda_2 \in \mathbb{Z}_N^\times, i.e., only \lambda_1 \varphi(P) and \lambda_2 \varphi(Q) are revealed, where \lambda_1 = \lambda_2 for M-SIDH and \lambda_1 = \lambda_2^{-1} for FESTA. Similar information is leaked in CSIDH since \varphi maps the eigenspaces of Frobenius on E_0 to the corresponding eigenspaces on E.
In this paper, we introduce a new polynomial time attack that generalizes the well known “lollipop” attack and analyze how it applies to M-SIDH, FESTA and CSIDH. We show that M-SIDH can be broken in polynomial time whenever E_0 or E is \mathbb{F}_p-rational, even when the endomorphism rings of E_0 and E are unknown. This can be generalized to the case where the starting (or end) curve is not \mathbb{F}_p-rational, but is connected to its Frobenius conjugate by an isogeny of small degree.
For FESTA, where the curve E_0 is already \mathbb{F}_p-rational, we obtain a polynomial time attack under the added requirement that at least one of the basis points P, Q spans an eigenspace of Frobenius, of an endomorphism of low degree, or of a composition of both. We note that the current implementation of FESTA does not choose such a basis. Since it is always possible to construct an endomorphism, typically of large degree, with either P, Q an eigenvector, we conclude that FESTA with overstretched parameters is insecure.
Although the information leaked in CSIDH is very similar to FESTA, we show that our attack does not reveal any new information about the secret isogeny, i.e., we only learn that it is \mathbb{F}_p-rational, which is a priori knowledge.
Finally, we analyze if and how it would be possible to backdoor M-SIDH and FESTA by choosing system parameters that look inconspicuous, but in fact reduce to the special cases above via a secret isogeny chosen by the adversary.
ePrint: https://eprint.iacr.org/2023/1433
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .