## CryptoDB

### Alfred Menezes

#### Affiliation: University of Waterloo

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Intractable Problems in Cryptography
Abstract

We examine several variants of the Diffie-Hellman and Discrete Log problems
that are connected to the security of cryptographic protocols. We discuss
the reductions that are known between them and the challenges in trying
to assess the true level of difficulty of these problems, particularly
if they are interactive or have complicated input.

2010

EPRINT

On the Efficiency and Security of Pairing-Based Protocols in the Type 1 and Type 4 Settings
Abstract

We focus on the implementation and security aspects of cryptographic protocols that use Type 1 and Type 4 pairings. On the implementation front, we report improved timings for Type 1 pairings derived from supersingular elliptic curves in characteristic 2 and 3 and the first timings for supersingular genus-2 curves in characteristic 2
at the 128-bit security level. In the case of Type 4 pairings, our main contribution is a new method for hashing into ${\mathbb G}_2$ which makes the Type 4 setting almost as efficient as Type 3. On the security front, for some well-known protocols we discuss to what
extent the security arguments are tenable when one moves to genus-2
curves in the Type 1 case. In Type 4, we observe that the Boneh-Shacham group signature scheme, the very first protocol for which the Type 4 setting was introduced in the literature, is trivially insecure, and we describe a small modification that appears to restore its security.

2009

EPRINT

Comparing Two Pairing-Based Aggregate Signature Schemes
Abstract

In 2003, Boneh, Gentry, Lynn and Shacham (BGLS) devised the first
provably-secure aggregate signature scheme. Their scheme uses bilinear
pairings and their security proof is in the random oracle model.
The first pairing-based aggregate signature scheme which has a security
proof that does not make the random oracle assumption was proposed in
2006 by Lu, Ostrovsky, Sahai, Shacham and Waters (LOSSW). In this paper,
we compare the security and efficiency of the BGLS and LOSSW schemes
when asymmetric pairings derived from Barreto-Naehrig (BN) elliptic
curves are employed.

2008

EPRINT

Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift
Abstract

Over a period of sixteen years elliptic curve cryptography went from being an approach that many people mistrusted or misunderstood to being a public key technology that enjoys almost unquestioned acceptance. We describe the sometimes surprising twists and turns in this paradigm shift, and compare this story with the commonly accepted Ideal Model
of how research and development function in cryptography. We also
discuss to what extent the ideas in the literature on "social
construction of technology" can contribute to a better understanding
of this history.

2008

EPRINT

Analyzing the Galbraith-Lin-Scott Point Multiplication Method for Elliptic Curves over Binary Fields
Abstract

Galbraith, Lin and Scott recently constructed efficiently-computable
endomorphisms for a large family of elliptic curves defined over
F_{q^2} and showed, in the case where q is prime, that the
Gallant-Lambert-Vanstone point multiplication method for these curves
is significantly faster than point multiplication for general elliptic
curves over prime fields. In this paper, we investigate the potential
benefits of using Galbraith-Lin-Scott elliptic curves in the case
where q is a power of 2. The analysis differs from the q prime case
because of several factors, including the availability of the point
halving strategy for elliptic curves over binary fields. Our analysis
and implementations show that Galbraith-Lin-Scott offers significant
acceleration for curves over binary fields, in both doubling- and
halving-based approaches. Experimentally, the acceleration surpasses
that reported for prime fields (for the platform in common), a
somewhat counterintuitive result given the relative costs of point
addition and doubling in each case.

2007

EPRINT

Another Look at Non-Standard Discrete Log and Diffie-Hellman Problems
Abstract

We examine several versions of the one-more-discrete-log and
one-more-Diffie-Hellman problems. In attempting to evaluate
their intractability, we find conflicting evidence of the
relative hardness of the different problems. Much of this
evidence comes from natural families of groups associated with
curves of genus 2, 3, 4, 5, and 6. This leads to questions
about how to interpret reductionist security arguments that
rely on these non-standard problems.

2006

EPRINT

Another Look at "Provable Security". II
Abstract

We discuss the question of how to interpret reduction arguments
in cryptography. We give some examples to show the subtlety
and difficulty of this question.

2006

EPRINT

Another Look at Generic Groups
Abstract

Starting with Shoup's seminal paper [24], the generic
group model has been an important tool in reductionist security
arguments. After an informal explanation of this model and
Shoup's theorem, we discuss the danger of flaws in proofs. We
next describe an ontological difference between the generic
group assumption and the random oracle model for hash
functions. We then examine some criticisms that have
been leveled at the generic group model and raise some
questions of our own.

2005

EPRINT

Pairing-Based Cryptography at High Security Levels
Abstract

In recent years cryptographic protocols based on the Weil and Tate pairings on elliptic curves have attracted much attention. A notable success in this area was the elegant solution by Boneh and Franklin of the problem of efficient identity-based encryption. At the same time, the security standards for public key cryptosystems are expected to increase, so that in the future they will be capable of providing security equivalent to 128-, 192-, or 256-bit AES keys. In this paper we examine the implications of heightened security needs for pairing-based cryptosystems. We first describe three different reasons why high-security users might have concerns about the long-term viability of these systems. However, in our view none of the risks inherent in pairing-based systems are sufficiently serious to warrant pulling them from the shelves.
We next discuss two families of elliptic curves E for use in pairing-based cryptosystems. The first has the property that the pairing takes values in the prime field F_p over which the curve is defined;
the second family consists of supersingular curves with embedding
degree k=2. Finally, we examine the efficiency of the Weil pairing
as opposed to the Tate pairing and compare a range of choices of
embedding degree k, including k=1 and k=24.

2005

EPRINT

Another look at HMQV
Abstract

HMQV is a `hashed variant' of the MQV key agreement protocol. It was recently introduced by Krawczyk, who claimed that HMQV has very significant advantages over MQV: (i) a security proof under reasonable assumptions in the (extended) Canetti-Krawczyk model for key exchange; and (ii) superior performance in some situations.
In this paper we demonstrate that HMQV is insecure by presenting realistic attacks in the Canetti-Krawczyk model that recover a victim's static private key. We propose HMQV-1, a patched version of HMQV that resists our attacks (but does not have any performance advantages over MQV). We also identify the fallacies in the security proof for HMQV, critique the security model, and raise some questions about the assurances that proofs in this model can provide.

2004

EPRINT

Another Look at ``Provable Security''
Abstract

We give an informal analysis and critique of several typical
``provable security'' results. In some cases there are
intuitive but convincing arguments for rejecting the conclusions
suggested by the formal terminology and ``proofs,'' whereas
in other cases the formalism seems to be consistent with common
sense. We discuss the reasons why the search for mathematically
convincing theoretical evidence to support the security of
public-key systems has been an important theme of
researchers. But we argue that the theorem-proof paradigm
of theoretical mathematics is of limited relevance here
and often leads to papers that are confusing and misleading.
Because our paper is aimed at the general mathematical public,
it is self-contained and as jargon-free as possible.

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

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.

2001

EPRINT

Solving Elliptic Curve Discrete Logarithm Problems Using Weil Descent
Abstract

We provide a concrete instance of the discrete logarithm problem
on an elliptic curve over F_{2^{155}} which resists all previously
known attacks, but which can be solved with modest computer
resources using the Weil descent attack methodology of Frey. We
report on our implementation of index-calculus methods for
hyperelliptic curves over characteristic two finite fields, and
discuss the cryptographic implications of our results.

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

- Asiacrypt 2011
- Eurocrypt 2011
- PKC 2010
- Eurocrypt 2008
- Crypto 2007
- PKC 2007
- Asiacrypt 2005
- PKC 2004
- Crypto 2002
- Asiacrypt 2002
- Eurocrypt 2000
- Asiacrypt 2000
- Crypto 1998
- Crypto 1994

#### Coauthors

- Gora Adj (1)
- Adrian Antipa (1)
- Simon Blake-Wilson (1)
- Daniel R. L. Brown (1)
- Sanjit Chatterjee (4)
- Darrel Hankerson (4)
- Greg Harper (1)
- M. J. Jacobson (1)
- Koray Karabina (2)
- Edward Knapp (1)
- Ann Hibner Koblitz (1)
- Neal Koblitz (10)
- Julio López (1)
- Markus Maurer (1)
- Thomaz Oliveira (1)
- Francisco Rodríguez-Henríquez (1)
- Andreas Stein (1)
- René Struik (1)
- Edlyn Teske (3)
- Scott A. Vanstone (4)
- Annegret Weng (1)