Blog

A Note on FESTA

In this short note we discuss a claim made in the FESTA article. The claim is that the choice of diagonal matrices to scale torsion point images in the countermeasure FESTA is not a singular choice, and that the security of the scheme shall not be jeopardized if the commutative subgroup of diagonal matrices could be replaced by any other commutative subgroup of invertible matrices, such as that of circulant matrices. In the framework of Isogeny Problems with Level Structure, it is interesting to ask if the corresponding level structures reduce to each other. Here we confirm that the circulant case indeed reduces to the diagonal case as proposed in FESTA when the scaling matrices are defined over \((\mathbb{Z} / N\mathbb{Z})\) for \(N = p^r\) for prime \(p > 2\). In the special case when the matrices are defined over finite fields i.e, \(N=p\) for some large prime, the reduction to the diagonal case holds for any (non-trivial) commutative subalgebra. However, when \( N = 2^k\), we show that a reduction between the two cases is not possible by our method, which is in contrast to the aforementioned claim.