## CryptoDB

### Steven D. Galbraith

#### Affiliation: University of Auckland, New Zealand

#### Publications

**Year**

**Venue**

**Title**

2020

JOFC

Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems
Abstract

We present signature schemes whose security relies on computational assumptions relating to isogeny graphs of supersingular elliptic curves. We give two schemes, both of them based on interactive identification protocols. The first identification protocol is due to De Feo, Jao and Plût. The second one, and the main contribution of the paper, makes novel use of an algorithm of Kohel, Lauter, Petit and Tignol for the quaternion version of the $$\ell $$ ℓ -isogeny problem, for which we provide a more complete description and analysis, and is based on a more standard and potentially stronger computational problem. Both identification protocols lead to signatures that are existentially unforgeable under chosen message attacks in the random oracle model using the well-known Fiat-Shamir transform, and in the quantum random oracle model using another transform due to Unruh. A version of the first signature scheme was independently published by Yoo, Azarderakhsh, Jalali, Jao and Soukharev. This is the full version of a paper published at ASIACRYPT 2017.

2020

EUROCRYPT

Integral Matrix Gram Root and Lattice Gaussian Sampling without Floats
📺
Abstract

Many advanced lattice based cryptosystems require to sample lattice points from Gaussian distributions. One challenge for this task is that all current algorithms resort to floating-point arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for high-precision, lazy/backtracking techniques for efficiency, and may suffer from weak determinism which can completely break certain schemes.
In this paper, we give techniques to implement Gaussian sampling over general lattices without using FPA. To this end, we revisit the approach of Peikert, using perturbation sampling. Peikert's approach uses continuous Gaussian sampling and some decomposition $\BSigma = \matA \matA^t$ of the target covariance matrix $\BSigma$. The suggested decomposition, e.g. the Cholesky decomposition, gives rise to a square matrix $\matA$ with real (not integer) entries. Our idea, in a nutshell, is to replace this decomposition by an integral one. While there is in general no integer solution if we restrict $\matA$ to being a square matrix, we show that such a decomposition can be efficiently found by allowing $\matA$ to be wider (say $n \times 9n$). This can be viewed as an extension of Lagrange's four-square theorem to matrices. In addition, we adapt our integral decomposition algorithm to the ring setting: for power-of-2 cyclotomics, we can exploit the tower of rings structure for improved complexity and compactness.

2019

EUROCRYPT

SeaSign: Compact Isogeny Signatures from Class Group Actions
📺
Abstract

We give a new signature scheme for isogenies that combines the class group actions of CSIDH with the notion of Fiat-Shamir with aborts. Our techniques allow to have signatures of size less than one kilobyte at the 128-bit security level, even with tight security reduction (to a non-standard problem) in the quantum random oracle model. Hence our signatures are potentially shorter than lattice signatures, but signing and verification are currently very expensive.

2019

PKC

Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation
Abstract

We consider the problem of constructing Diffie-Hellman (DH) parameters which pass standard approaches to parameter validation but for which the Discrete Logarithm Problem (DLP) is relatively easy to solve. We consider both the finite field setting and the elliptic curve setting.For finite fields, we show how to construct DH parameters (p, q, g) for the safe prime setting in which
$$p=2q+1$$
is prime, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and g is of order q mod p. The construction involves modifying and combining known methods for obtaining Carmichael numbers. Concretely, we provide an example with 1024-bit p which passes OpenSSL’s Diffie-Hellman validation procedure with probability
$$2^{-24}$$
(for versions of OpenSSL prior to 1.1.0i). Here, the largest factor of q has 121 bits, meaning that the DLP can be solved with about
$$2^{64}$$
effort using the Pohlig-Hellman algorithm. We go on to explain how this parameter set can be used to mount offline dictionary attacks against PAKE protocols. In the elliptic curve case, we use an algorithm of Bröker and Stevenhagen to construct an elliptic curve E over a finite field
$${\mathbb {F}}_p$$
having a specified number of points n. We are able to select n of the form
$$h\cdot q$$
such that h is a small co-factor, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and E has a point of order q. Concretely, we provide example curves at the 128-bit security level with
$$h=1$$
, where q passes a single random-base Miller-Rabin primality test with probability 1/4 and where the elliptic curve DLP can be solved with about
$$2^{44}$$
effort. Alternatively, we can pass the test with probability 1/8 and solve the elliptic curve DLP with about
$$2^{35.5}$$
effort. These ECDH parameter sets lead to similar attacks on PAKE protocols relying on elliptic curves.Our work shows the importance of performing proper (EC)DH parameter validation in cryptographic implementations and/or the wisdom of relying on standardised parameter sets of known provenance.

2019

TCC

Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems
Abstract

We consider the problem of obfuscating programs for fuzzy matching (in other words, testing whether the Hamming distance between an n-bit input and a fixed n-bit target vector is smaller than some predetermined threshold). This problem arises in biometric matching and other contexts. We present a virtual-black-box (VBB) secure and input-hiding obfuscator for fuzzy matching for Hamming distance, based on certain natural number-theoretic computational assumptions. In contrast to schemes based on coding theory, our obfuscator is based on computational hardness rather than information-theoretic hardness, and can be implemented for a much wider range of parameters. The Hamming distance obfuscator can also be applied to obfuscation of matching under the $$\ell _1$$ norm on $$\mathbb {Z}^n$$.We also consider obfuscating conjunctions. Conjunctions are equivalent to pattern matching with wildcards, which can be reduced in some cases to fuzzy matching. Our approach does not cover as general a range of parameters as other solutions, but it is much more compact. We study the relation between our obfuscation schemes and other obfuscators and give some advantages of our solution.

2019

JOFC

Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem
Abstract

The paper is about algorithms for the inhomogeneous short integer solution problem: given $$(\mathbf A , \mathbf s )$$ ( A , s ) to find a short vector $$\mathbf{x }$$ x such that $$\mathbf A \mathbf{x }\equiv \mathbf s \pmod {q}$$ A x ≡ s ( mod q ) . We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Minder and Sinclair; Howgrave–Graham and Joux (HGJ); Becker, Coron and Joux (BCJ). Our main results include: applying the Hermite normal form (HNF) to get faster algorithms; a heuristic analysis of the HGJ and BCJ algorithms in the case of density greater than one; an improved cryptanalysis of the SWIFFT hash function; a new method that exploits symmetries to speed up algorithms for Ring-SIS in some cases.

2017

ASIACRYPT

2015

EPRINT

2010

PKC

2009

EPRINT

Point Compression for Koblitz Elliptic Curves
Abstract

Elliptic curves over finite fields have applications in public key cryptography. A Koblitz curve is an elliptic curve $E$ over $\F_2$; the group $E( \Ftn )$ has convenient features for efficient implementation of elliptic curve cryptography.
Wiener and Zuccherato and Gallant, Lambert and Vanstone showed that one can accelerate the Pollard rho algorithm for the discrete logarithm problem on Koblitz curves. This implies that when using Koblitz curves, one has a lower security per bit than when using general elliptic curves defined over the same field. Hence for a fixed security level, systems using Koblitz curves require slightly more bandwidth.
We present a method to reduce this bandwidth. Our method is appropriate for applications such as Diffie-Hellman key exchange or
Elgamal encryption. We show that, with a low probability of failure, our method gives the expected bandwidth for a given security level.

2008

EPRINT

Exponentiation in pairing-friendly groups using homomorphisms
Abstract

We present efficiently computable homomorphisms of the groups $G_2$ and $G_T$ for pairings $G_1 \times G_2 \rightarrow G_T$. This allows
exponentiation in $G_2$ and $G_T$ to be accelerated using the Gallant-Lambert-Vanstone method.

2008

EPRINT

Endomorphisms for faster elliptic curve cryptography on a large class of curves
Abstract

Efficiently computable homomorphisms allow elliptic curve point
multiplication to be accelerated using the Gallant-Lambert-Vanstone
(GLV) method.
We extend results of Iijima, Matsuo, Chao and Tsujii which give
such homomorphisms
for a large class of elliptic curves by working over quadratic extensions
and demonstrate that these results can be applied to the
GLV method.
Our implementation runs in between 0.70 and 0.84 the time
of the previous best methods for elliptic
curve point multiplication on curves without small class number
complex multiplication. Further speedups are
possible when using more special curves.

2008

EPRINT

Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation
Abstract

From the viewpoint of x-coordinate-only arithmetic on elliptic curves, switching between the Edwards model and the Montgomery model is quasi cost-free. We use this observation to speed up Montgomery's algorithm, reducing the complexity of a doubling step from 2M + 2S to 1M + 3S for suitably chosen curve parameters.

2008

EPRINT

Pairings on hyperelliptic curves with a real model
Abstract

We analyse the efficiency of pairing computations on hyperelliptic curves given by a real model using a balanced divisor at infinity. Several optimisations are proposed and analysed. Genus two curves given by a real model arise when considering pairing friendly groups of order dividing $p^{2}-p+1$. We compare the performance of pairings on such groups in both elliptic and hyperelliptic versions. We conclude that pairings can be efficiently computable in real models of hyperelliptic curves.

2008

EPRINT

Computing Pairings Using x-Coordinates Only
Abstract

To reduce bandwidth in elliptic curve cryptography one can transmit
only $x$-coordinates of points (or $x$-coordinates together with an
extra bit). For further computation using the points one can either
recover the $y$-coordinates by taking square roots or one can use
point multiplication formulae which use $x$-coordinates only.
We consider how to efficiently use point compression in
pairing-based cryptography. We give a method to compute compressed
Weil pairings using $x$-coordinates only. We also show how to
compute the compressed Tate and ate pairings using only one
$y$-coordinate. Our methods are more efficient than taking square
roots when the embedding degree is small. We implemented the
algorithms in the case of embedding degree 2 curves over $\F_p$
where $p \equiv 3 \pmod{4}$ and found that our methods are
$10-15\%$ faster than the analogous methods using square roots.

2008

EPRINT

Efficient Hyperelliptic Arithmetic using Balanced Representation for Divisors
Abstract

We discuss arithmetic in the Jacobian of a
hyperelliptic curve $C$ of genus $g$. The traditional approach is to
fix a point $P_\infty \in C$ and represent divisor classes in the
form $E - d(P_\infty)$ where $E$ is effective and $0 \le d \le g$.
We propose a different representation which is balanced at infinity.
The resulting arithmetic is more efficient than previous approaches
when there are 2 points at infinity.
This is a corrected and extended version of the article presented in ANTS 2008. We include an appendix with explicit formulae to compute a very efficient `baby step' in genus 2 hyperelliptic curves given by an imaginary model.

2007

EPRINT

Aspects of Pairing Inversion
Abstract

We discuss some applications of the pairing inversion problem and outline some potential approaches for solving it. Our analysis of these approaches gives further evidence that pairing inversion is a hard problem.

2006

EPRINT

Pairings for Cryptographers
Abstract

Many research papers in pairing based cryptography
treat pairings as a ``black box''. These papers build
cryptographic schemes making use of various properties of
pairings.
If this approach is taken, then it is easy for authors to
make invalid assumptions concerning the properties of pairings.
The cryptographic schemes developed
may not be realizable in practice, or may not be
as efficient as the authors assume.
The aim of this paper is to outline, in as simple a fashion
as possible, the basic choices that are available when
using pairings in cryptography. For each choice, the main
properties and efficiency issues are summarized. The paper is
intended to be of use to non-specialists who are interested
in using pairings to design cryptographic schemes.

2006

EPRINT

Simplified pairing computation and security implications
Abstract

Recent progress on pairing implementation has made certain pairings
extremely simple and fast to compute. Hence, it is natural to examine if there are consequences for the security of pairing-based cryptography.
This paper gives a method to compute eta pairings in a way which avoids the requirement for a final exponentiation. The method does not lead to any improvement in the speed of pairing implementation. However, it seems appropriate to re-evaluate the security of pairing based cryptography in light of these new ideas. A multivariate attack on the pairing inversion problem is proposed and analysed. Our findings support the belief that pairing inversion is a hard computational problem.

2006

EPRINT

Disguising tori and elliptic curves
Abstract

Frey proposed the idea of `disguising' an elliptic curve. This is a method to obtain a `black box' representation of a group. We adapt this notion to finite fields and tori and study the question of whether such systems are secure.
Our main result is an algebraic attack which shows that it is not secure to disguise the torus $T_2$. We also show that some methods for disguising an elliptic curve are not secure. Finally, we present a method to disguise an elliptic curve which seems to resist our algebraic attack.

2006

EPRINT

Discrete Logarithms in Generalized Jacobians
Abstract

D\'ech\`ene has proposed generalized Jacobians as a source of groups for public-key cryptosystems based on the hardness of the Discrete Logarithm Problem (DLP). Her specific proposal gives rise to a group isomorphic to the semidirect product of an elliptic curve and a multiplicative group of a finite field. We explain why her proposal has no advantages over simply taking the direct product of groups. We then argue that generalized Jacobians offer poorer security and efficiency than standard Jacobians.

2006

EPRINT

Distortion maps for genus two curves
Abstract

Distortion maps are a useful tool for pairing based cryptography.
Compared with elliptic curves, the case of hyperelliptic curves
of genus $g > 1$ is more complicated since the full torsion subgroup
has rank $2g$. In this paper we prove that distortion maps always exist for supersingular curves of genus $g>1$ and we give several examples in genus $2$.

2005

EPRINT

The Weil pairing on elliptic curves over C
Abstract

To help motivate the Weil pairing, we discuss
it in the context of elliptic curves over the
field of complex numbers.

2004

EPRINT

Easy decision-Diffie-Hellman groups
Abstract

It is already known that the Weil and Tate pairings
can be used to solve many decision-Diffie-Hellman (DDH)
problems on elliptic curves.
A natural question is whether all DDH problems are
easy on supersingular curves.
To answer this question it is necessary to have
suitable distortion maps.
Verheul states that such maps exist,
and this paper gives methods to construct them.
The paper therefore shows that all DDH problems on
supersingular elliptic curves are easy.
We also discuss the issue of which DDH problems on ordinary
curves are easy.
A related contribution is a discussion of distortion maps
which are not isomorphisms. We give explicit
distortion maps for elliptic curves with complex
multiplication of discriminants $D=-7$ and $D=-8$.

2004

EPRINT

Ordinary abelian varieties having small embedding degree
Abstract

Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this paper we generalise their results by giving
families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of
group orders with embedding degrees 5, 10 and 12.

2004

EPRINT

Efficient Pairing Computation on Supersingular Abelian Varieties
Abstract

We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three.
We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method.
These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.

2003

EPRINT

Cryptanalysis of a Cryptosystem based on Drinfeld modules
Abstract

A public key cryptosystem based on Drinfeld modules has been proposed
by Gillard, Leprevost, Panchishkin and Roblot. The paper shows how an
adversary can directly recover a private key using only
the public key, and so the cryptosystem is insecure.

2002

EPRINT

Secure Bilinear Diffie-Hellman Bits
Abstract

The Weil and Tate pairings are a popular new
gadget in cryptography and have found many applications,
including identity-based cryptography.
In particular, the pairings have been used for key exchange
protocols.
This paper studies the bit security of keys obtained
using protocols based on pairings (that is,
we show that obtaining certain bits of the common key
is as hard as computing the entire key).
These results are valuable as they give insight into
how many ``hard-core'' bits can be obtained from
key exchange using pairings.

2001

EPRINT

Cryptanalysis of some elliptic curve based cryptosystems of Paillier
Abstract

Two public key encryption schemes
based on anomalous elliptic curves over rings
are studied.
It is argued that these schemes are not secure.

2001

EPRINT

Elliptic curve Paillier schemes
Abstract

This paper is concerned with
generalisations of Paillier's
probabilistic encryption scheme
from the integers modulo a square
to elliptic curves over rings.
Paillier himself described
two public key encryption schemes
based on anomalous elliptic curves over rings.
It is argued that these schemes are not secure.
A more natural generalisation of Paillier's scheme to
elliptic curves is given.

2001

EPRINT

Extending the GHS Weil Descent Attack
Abstract

In this paper we extend the Weil descent attack
due to Gaudry, Hess and Smart (GHS) to
a much larger class of elliptic curves.
This extended attack still only works for fields of composite
degree over $\F_2$.
The principle behind the extended attack is to use
isogenies to
find a new elliptic curve for which the GHS attack is
effective.
The discrete logarithm problem on the target curve
can be transformed into a discrete logarithm problem
on the new isogenous curve.
One contribution of the paper is to give
an improvement to an algorithm of Galbraith
for constructing isogenies between elliptic curves,
and this is of independent interest in
elliptic curve cryptography.
We conclude that fields of the form $\F_{q^7}$ should be
considered weaker from a cryptographic standpoint than
other fields.
In addition we show that a larger proportion than previously
thought of elliptic curves over $\F_{2^{155}}$ should be
considered weak.

#### Program Committees

- PKC 2020
- Asiacrypt 2019
- Asiacrypt 2018
- Crypto 2018
- Asiacrypt 2017
- Asiacrypt 2016
- Crypto 2016
- PKC 2015
- Crypto 2015
- Asiacrypt 2014
- Eurocrypt 2013
- PKC 2013
- Eurocrypt 2012
- Crypto 2012
- Crypto 2011
- Eurocrypt 2010
- Crypto 2009
- PKC 2008
- Asiacrypt 2007
- PKC 2007
- Crypto 2007
- Eurocrypt 2005

#### Coauthors

- Shi Bai (2)
- Paulo S. L. M. Barreto (1)
- Simon R. Blackburn (2)
- Wouter Castryck (1)
- Carlos Cid (1)
- Ricardo Dahab (1)
- Luca De Feo (1)
- Léo Ducas (1)
- P.N.J. Eagle (1)
- Reza Rezaeian Farashahi (1)
- Pierrick Gaudry (1)
- Michael Harrison (1)
- Colm O hEigeartaigh (2)
- Florian Hess (3)
- Herbie J. Hopkins (1)
- Liangze Li (2)
- Xibin Lin (5)
- Jake Massimo (1)
- J. McKee (1)
- David Mireles (1)
- Eduardo Morais (1)
- David J. Mireles Morales (1)
- Kenneth G. Paterson (2)
- Christophe Petit (3)
- Thomas Prest (1)
- Jordi Pujol\`as (1)
- Christophe Ritzenthaler (1)
- Victor Rotger (1)
- Raminder S. Ruprai (1)
- Michael Scott (5)
- Barak Shani (2)
- Caroline Sheedy (1)
- Daniel Sheffield (2)
- Igor E. Shparlinski (1)
- Javier Silva (2)
- Nigel P. Smart (3)
- Benjamin Smith (2)
- Yan Bo Ti (1)
- P. Valenca (1)
- Frederik Vercauteren (1)
- Eric R. Verheul (1)
- Ping Wang (1)
- Yang Yu (1)
- Fangguo Zhang (1)
- Lukas Zobernig (1)