Efficient algorithms verify special abelian surfaces in cryptography
Supersingularity and Superspeciality Verification of Abelian Surfaces
Cryptography and Security
Summary
It is important to check if certain mathematical objects called abelian surfaces have a special property (supersingularity) used in cryptography. Before this work, no fast method existed to do this verification. The authors developed a quick probabilistic algorithm and a certain conclusive one under some conditions that can efficiently tell if an abelian surface is supersingular. They also created ways to verify related properties for similar objects in higher dimensions.
What this means in practice
- •For cryptography engineers: Efficiently verify supersingularity of abelian surfaces in isogeny-based cryptographic systems to enhance key validation.
- •For mathematical software developers: Integrate new algorithms to verify minimality, maximality, and superspeciality for abelian varieties improving mathematical software toolkits.
Authors
Maria Corte-Real Santos, Gioella Lorenzon, Krijn Reijnders
Abstract
Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiate this research topic by giving an efficient Monte Carlo algorithm to verify if an abelian surface over $\mathbb{F}_p$ is supersingular in $O(\log p)$ with negligible failure probability, and an efficient conclusive algorithm if the order is smooth. We derive this algorithm by a careful analysis on the structure of supersingular Jacobians over $\mathbb{F}_p$. Furthermore, we derive efficient algorithms to verify if an abelian variety of any dimension is minimal or maximal, and to verify if a Jacobian of any dimension is superspecial.