Paper 2008/417

On the security of pairing-friendly abelian varieties over non-prime fields

Naomi Benger, Manuel Charlemagne, and David Freeman

Abstract

Let $A$ be an abelian variety defined over a non-prime finite field ${\text{F}}_q$ that has embedding degree $k$ with respect to a subgroup of prime order $r$. In this paper we give explicit conditions on $q$, $k$, and $r$ that imply that the minimal embedding field of $A$ with respect to $r$ is ${\text{F}}_{q^k}$. When these conditions hold, the embedding degree $k$ is a good measure of the security level of a pairing-based cryptosystem that uses $A$. We apply our theorem to supersingular elliptic curves and to supersingular genus 2 curves, in each case computing a maximum $\rho$-value for which the minimal embedding field must be $$. Our results are in most cases stronger (i.e., give larger allowable $$-values) than previously known results for supersingular varieties, and our theorem holds for general abelian varieties, not only supersingular ones.