## CryptoDB

### Laura Hitt

#### Publications

**Year**

**Venue**

**Title**

2007

EPRINT

Families of genus 2 curves with small embedding degree
Abstract

Hyperelliptic curves of small genus have the advantage of
providing a group of comparable size as that of elliptic curves,
while working over a field of smaller size. Pairing-friendly
hyperelliptic curves are those whose order of the Jacobian is
divisible by a large prime, whose embedding degree is small enough
for computations to be feasible, and whose minimal embedding field
is large enough for the discrete logarithm problem in it to be
difficult. We give a sequence of $\F_q$-isogeny classes for a family
of Jacobians of genus two curves over $\F_{q}$, for $q=2^m$, and
their corresponding small embedding degrees. We give examples of
the parameters for such curves with embedding degree $k<(\log q)^2$,
such as $k=8,13,16,23,26,37,46,52$.
For secure and efficient implementation of pairing-based
cryptography on genus g curves over $\F_q$, it is desirable that the
ratio $\rho=\frac{g\log_2 q}{\log_2N}$ be approximately 1, where $N$
is the order of the subgroup with embedding degree $k$. We show that
for our family of curves, $\rho$ is often near 1 and never more than
2.
We also give a sequence of $\F_q$-isogeny classes for a family of
Jacobians of genus 2 curves over $\F_{q}$ whose minimal embedding
field is much smaller than the finite field indicated by the
embedding degree $k$. That is, the extension degrees in this
example differ by a factor of $m$, where $q=2^m$, demonstrating that
the embedding degree can be a far from accurate measure of security.
As a result, we use an indicator $k'=\frac{\ord_N2}{m}$ to examine
the cryptographic security of our family of curves.

2007

EPRINT

Updated standards for validating elliptic curves
Abstract

We give a concise statement of a test for security of elliptic
curves that should be inserted into the standards for elliptic curve
cryptography. In particular, current validation for parameters
related to the MOV condition that appears in the latest draft of the
IEEE P1363 standard \cite[Section A.12.1, Section A.16.8]{P1363}
should be replaced with our subfield-adjusted MOV condition.
Similarly, the Standards for Efficient Cryptography Group's document
SEC 1 \cite{sec_1} should make adjustments accordingly.

2006

EPRINT

On the Minimal Embedding Field
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 pairing-based 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^k-1$. Hence, $\F_{q^k}^*$ contains a subgroup of order
$N$. To determine the security level of a pairing-based
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
pairing-based cryptography, it is unlikely to affect curves used in
practice, as a discrepancy may only occur when $q$ is non-prime.
Nevertheless, it is an important point to keep in mind and a
motivation to recognize two separate parameters when describing a
pairing-based cryptosystem.