## CryptoDB

### Robert Granger

#### Affiliation: Ecole Polytechnique Federale Lausanne

#### Publications

**Year**

**Venue**

**Title**

2016

EUROCRYPT

2015

EPRINT

2010

EPRINT

On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
Abstract

We show that for any elliptic curve $E(\F_{q^n})$, if an adversary has access to a Static Diffie-Hellman Problem (Static DHP) oracle, then by making $O(q^{1-\frac{1}{n+1}})$ Static DHP oracle queries during an initial learning phase, for fixed $n>1$ and $q \rightarrow \infty$ the adversary can solve {\em any} further instance of the Static DHP in {\em heuristic} time $\tilde{O}(q^{1-\frac{1}{n+1}})$. While practical only for very small $n$, our algorithm reduces the security of elliptic curves defined over $\F_{p^2}$ and $\F_{p^4}$ proposed by Galbraith, Lin and Scott at EUROCRYPT 2009, should these curves be used in any protocol where a user can be made to act as a proxy Static DHP oracle. Our proposal also solves the {\em Delayed Target DHP} as defined by Freeman, and naturally extends to provide algorithms for solving the {\em Delayed Target DLP}, the {\em One-More DHP} and {\em One-More DLP} as studied by Koblitz and Menezes in the context of Jacobians of hyperelliptic curves of small genus. Lastly, we argue that for {\em any} group in which index calculus can be effectively applied, the above problems have a natural relationship, and will {\em always} be easier than the DLP.

2006

EPRINT

High Security Pairing-Based Cryptography Revisited
Abstract

The security and performance of pairing based cryptography has provoked a
large volume of research, in part because of the exciting new cryptographic
schemes that it underpins. We re-examine how one should implement pairings over
ordinary elliptic curves for various practical levels of security. We conclude,
contrary to prior work, that the Tate pairing is more efficient than the
Weil pairing for all such security levels. This is achieved by using efficient exponentiation techniques
in the cyclotomic subgroup backed by efficient squaring routines within the
same subgroup.

2006

EPRINT

On Computing Products of Pairings
Abstract

In many pairing-based protocols often the evaluation of the product
of many pairing evaluations is required. In this paper we consider
methods to compute such products efficiently. Focusing on pairing-friendly fields
in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms
for ordinary elliptic curves at various security levels. Our operation counts
indicate that the minimal cost of each additional pairing relative to the cost of
one is $\approx 0.61$, $0.45$, and $0.43$, for each of these pairings
respectively at the 128-bit security level.
For larger security levels the Ate pairing can have a relative
additional cost of as low as $0.13$ for each additional pairing.
These estimates allow implementors to make optimal algorithm choices for
given scenarios, in which the number of pairings in the product,
the security level, and the embedding degree are
factors under consideration.

2004

EPRINT

On Small Characteristic Algebraic Tori in Pairing-Based Cryptography
Abstract

The output of the Tate pairing on an elliptic curve over a finite
field may be viewed as an element of an algebraic torus.
Using this simple observation, we transfer techniques recently
developed for torus-based cryptography to pairing-based cryptography,
resulting in more efficient computations, and lower bandwidth
requirements. To illustrate the efficacy of this approach, we
apply the method to pairings on supersingular elliptic curves in
characteristic three.

2004

EPRINT

Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three
Abstract

Although identity based cryptography offers a number of functional advantages over conventional public key methods, the computational costs are significantly greater. The dominant part of this cost is the Tate pairing which, in characteristic three, is best computed using the algorithm of Duursma and Lee. However, in hardware and constrained environments this algorithm is unattractive since it requires online computation of cube roots or enough storage space to pre-compute required results. We examine the use of normal basis arithmetic in characteristic three in an attempt to get the best of both worlds: an efficient method for computing the Tate pairing that requires no pre-computation and that may also be implemented in hardware to accelerate devices such as smart-cards. Since normal basis arithmetic in characteristic three has not received much attention before, we
also discuss the construction of suitable bases and associated curve
parameterisations.

2004

EPRINT

Practical Cryptography in High Dimensional Tori
Abstract

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

#### Program Committees

- Eurocrypt 2017

#### Coauthors

- Faruk Göloglu (1)
- Florian Hess (1)
- Philipp Jovanovic (2)
- Thorsten Kleinjung (4)
- Gary McGuire (1)
- Bart Mennink (2)
- Samuel Neves (2)
- Roger Oyono (1)
- Dan Page (5)
- Karl Rubin (2)
- Michael Scott (2)
- Alice Silverberg (2)
- Nigel P. Smart (2)
- Martijn Stam (4)
- Nicolas Thériault (1)
- Marten van Dijk (2)
- Frederik Vercauteren (2)
- David P. Woodruff (2)
- Jens Zumbrägel (5)