## CryptoDB

### Edlyn Teske

#### Publications

**Year**

**Venue**

**Title**

2007

EPRINT

On prime-order elliptic curves with embedding degrees k=3,4 and 6
Abstract

We further analyze the solutions to the Diophantine equations from which prime-order elliptic curves of embedding degrees $k=3,4$ or $6$ (MNT curves) may be obtained. We give an explicit algorithm to generate such curves. We derive a heuristic lower bound for the number $E(z)$ of MNT curves with $k=6$ and discriminant $D\le z$, and compare this lower bound with experimental data.

2006

EPRINT

A taxonomy of pairing-friendly elliptic curves
Abstract

Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" curves are rare and thus require specific constructions. In this paper we give a single coherent framework that encompasses all of the constructions of pairing-friendly elliptic curves currently existing in the literature. We also include new constructions of pairing-friendly curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, we provide recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.

2004

EPRINT

Cryptographic Implications of Hess' Generalized GHS Attack
Abstract

A finite field K is said to be weak for elliptic curve cryptography if all instances of the discrete logarithm problem for all elliptic curves over K can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. By considering the GHS Weil descent attack, it was previously shown that characteristic two finite fields GF(q^5) are weak. In this paper, we examine characteristic two finite fields GF(q^n) for weakness under Hess' generalization of the GHS attack. We show that the fields GF(q^7) are potentially partially weak in the sense that any instance of the discrete logarithm problem for half of all elliptic curves over GF(q^7), namely those curves E for which #E is divisible by 4, can likely be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We also show that the fields GF(q^3) are partially weak, that the fields GF(q^6) are potentially weak, and that the fields GF(q^8) are potentially partially weak. Finally, we argue that the other fields GF(2^N) where N is not divisible by 3, 5, 6, 7 or 8, are not weak under Hess' generalized GHS attack.

2003

EPRINT

An Elliptic Curve Trapdoor System
Abstract

We propose an elliptic curve trapdoor system which is of interest in
key escrow applications. In this system, a pair
($E_{\rm s}, E_{\rm pb}$) of elliptic curves over $\F_{2^{161}}$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $E_{\rm s}(\F_{2^{161}})$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not trivial; (ii) $E_{\rm pb}$ is isogenous to $E_{\rm s}$; (iii) the best attack on the
ECDLP in $E_{\rm pb}(\F_{2^{161}})$ is the parallelized Pollard rho method.\\
The curve $E_{\rm pb}$ is used just as usual in elliptic curve cryptosystems. The curve $E_{\rm s} is submitted to a trusted authorityfor the purpose of key escrow. The crucial difference from other key escrow scenarios is that the trusted authority has to invest a considerable amount of computation to compromise a user's
private key, which makes applications such as widespread wire-tapping
impossible.

2003

EPRINT

Weak Fields for ECC
Abstract

We demonstrate that some finite fields, including GF(2^210) are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.

2002

EPRINT

On some Attacks on Multi-prime RSA
Abstract

Using more than two factors in the modulus of the RSA cryptosystem
has the arithmetic advantage that the private key computations can be
speeded up using Chinese remaindering. At the same time, with a proper
choice of parameters, one does not have to work with a larger
modulus to achieve the same level of security in terms of the difficulty of the integer factorization problem.
However, numerous attacks on specific instances on the RSA cryptosystem are known that apply if, for example, the decryption or encryption exponent are chosen too small, or if partial knowledge of the private key is available. Little work is known on how such attacks perform in the multi-prime case.
It turns out that for most of these attacks it is crucial that the
modulus contains exactly two primes. They become much less effective, or fail, when the modulus factors into more than two distinct primes.

2001

EPRINT

Analysis of the GHS Weil Descent Attack on the ECDLP over Characteristic Two Finite Fields of Composite Degree
Abstract

In this paper, we analyze the Gaudry-Hess-Smart (GHS) Weil descent
attack on the elliptic curve discrete logarithm problem (ECDLP) for
elliptic curves defined over characteristic two finite fields of
composite extension degree. For each such field $F_{2^N}$,
$N \in [100,600]$, we identify elliptic curve parameters such
that (i) there should exist a cryptographically interesting elliptic
curve $E$ over $F_{2^N}$ with these parameters; and (ii) the GHS
attack is more efficient for solving the ECDLP in $E(F_{2^N})$ than
for solving the ECDLP on any other cryptographically interesting
elliptic curve over $F_{2^N}$. We examine the feasibility of the
GHS attack on the specific elliptic curves over $F_{2^{176}}$,
$F_{2^{208}}$, $F_{2^{272}}$, $F_{2^{304}}$, and $F_{2^{368}}$
that are provided as examples inthe ANSI X9.62 standard for the
elliptic curve signature scheme ECDSA. Finally, we provide several
concrete instances of the ECDLP over $F_{2^N}$, $N$ composite,
of increasing difficulty which resist all previously known attacks
but which are within reach of the GHS attack.

#### Program Committees

- PKC 2011
- PKC 2008
- Crypto 2006
- PKC 2006
- PKC 2005
- Eurocrypt 2004

#### Coauthors

- David Freeman (2)
- M. Jason Hinek (1)
- Koray Karabina (1)
- Mo King Low (1)
- Markus Maurer (1)
- Alfred Menezes (3)
- Michael Scott (2)
- Annegret Weng (1)