Paper 2006/415
On the Minimal Embedding Field
Laura Hitt
Abstract
We discuss the underlying mathematics that causes the embedding degree of a curve of any genus to not necessarily correspond to the minimal embedding field, and hence why it may fail to capture the security of a pairingbased cryptosystem. Let $C$ be a curve of genus $g$ defined over a finite field $\F_q$, where $q=p^m$ for a prime $p$. The Jacobian of the curve is an abelian variety, $J_C(\F_q)$, of dimension $g$ defined over $\F_q$. For some prime $N$, coprime to $p$, the embedding degree of $J_C(\F_q)[N]$ is defined to be the smallest positive integer $k$ such that $N$ divides $q^k1$. Hence, $\F_{q^k}^*$ contains a subgroup of order $N$. To determine the security level of a pairingbased cryptosystem, it is important to know the minimal field containing the $N$th roots of unity, since the discrete logarithm problem can be transported from the curve to this field, where one can perform index calculus. We show that it is possible to have a dramatic (unbounded) difference between the size of the field given by the embedding degree, $\F_{p^{mk}}$, and the minimal embedding field that contains the $N$th roots of unity, $\F_{p^d}$, where $d\mid mk$. The embedding degree has utility as it indicates the field one must work over to compute the pairing, while a security parameter should indicate the minimal field containing the embedding. We discuss a way of measuring the difference between the size of the two fields and we advocate the use of two separate parameters. We offer a possible security parameter, $k'=\frac{\ord_Np}{g}$, and we present examples of elliptic curves and genus 2 curves which highlight the difference between them. While our observation provides a proper theoretical understanding of minimal embedding fields in pairingbased cryptography, it is unlikely to affect curves used in practice, as a discrepancy may only occur when $q$ is nonprime. Nevertheless, it is an important point to keep in mind and a motivation to recognize two separate parameters when describing a pairingbased cryptosystem.
Note: Repackaged, different emphasis
Metadata
 Available format(s)
 PDF PS
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 pairingbased cryptosystemsembedding degreediscrete logarithmelliptic curve cryptography
 Contact author(s)
 lhitt @ math utexas edu
 History
 20070227: last of 3 revisions
 20061114: received
 See all versions
 Short URL
 https://ia.cr/2006/415
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/415, author = {Laura Hitt}, title = {On the Minimal Embedding Field}, howpublished = {Cryptology ePrint Archive, Paper 2006/415}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/415}}, url = {https://eprint.iacr.org/2006/415} }