Cryptology ePrint Archive: Report 2008/417

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

Naomi Benger and Manuel Charlemagne and David Freeman

Abstract: Let $A$ be an abelian variety defined over a non-prime finite field $\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 $\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 $\F_{q^k}$. Our results are in most cases stronger (i.e., give larger allowable $\rho$-values) than previously known results for supersingular varieties, and our theorem holds for general abelian varieties, not only supersingular ones.

Category / Keywords: pairing-friendly abelian varieties, non-prime fields, security

Date: received 29 Sep 2008, last revised 10 Mar 2009

Contact author: nbenger at computing dcu ie

Available formats: PDF | BibTeX Citation

Version: 20090310:152128 (All versions of this report)

Discussion forum: Show discussion | Start new discussion