International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Robert Granger

Affiliation: Ecole Polytechnique Federale Lausanne

Publications

Year
Venue
Title
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
PKC
2014
CRYPTO
2014
EPRINT
2014
EPRINT
2013
CRYPTO
2010
EPRINT
On the Static Diffie-Hellman Problem on Elliptic Curves over Extension Fields
Robert Granger
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.
2010
PKC
2010
ASIACRYPT
2007
EUROCRYPT
2006
EPRINT
High Security Pairing-Based Cryptography Revisited
R. Granger Nigel P. Smart D. Page
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
R Granger Nigel P. Smart
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.
2005
CRYPTO
2005
EUROCRYPT
2004
EPRINT
On Small Characteristic Algebraic Tori in Pairing-Based Cryptography
R. Granger D. Page M. Stam
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
R. Granger D. Page M. Stam
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
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