Lie Algebras and the Security of Cryptosystems Based on Classical Varieties in Disguise

In 2006 de Graaf et al. devised a Lie-algebra-based strategy for finding a linear transformation $T \in PGL_{N+1}(\mathbb{Q})$ connecting two linearly equivalent projective varieties $X, X' \subseteq \mathbb{P}^N$ over $\mathbb{Q}$. The method succeeds for several families of "classical" varieties such as Veronese varieties, which have large automorphism groups. In this paper, we study the Lie algebra method over finite fields, which comes with new technicalities when compared to $\mathbb{Q}$ due to, e.g., the characteristic being positive. Concretely, we make the method work for Veronese varieties of dimension $r \geq 2$ and (heuristically) for secant varieties of Grassmannians of planes. This leads to classical polynomial-time attacks against two candidate-post-quantum key exchange protocols based on disguised Veronese surfaces and threefolds, which were recently proposed by Alzati et al., as well as a digital signature scheme based on secant varieties of Grassmannians of planes due to Di Tullio and Gyawali. We provide an implementation in Magma.