## CryptoDB

### Laurent Imbert

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Hybrid Binary-Ternary Joint Sparse Form and its Application in Elliptic Curve Cryptography
Abstract

Multi-exponentiation is a common and time consuming operation in public-key cryptography. Its elliptic curve counterpart, called multi-scalar multiplication is extensively used for digital signature verification. Several algorithms have been proposed to speed-up those critical computations. They are based on simultaneously recoding a set of integers in order to minimize the number of general multiplications or point additions. When signed-digit recoding techniques can be used, as in the world of elliptic curves, Joint Sparse Form (JSF) and interleaving $w$-NAF are the most efficient algorithms. In this paper, a novel recoding algorithm for a pair of integers is proposed, based on a decomposition that mixes powers of 2 and powers of 3. The so-called Hybrid Binary-Ternary Joint Sparse Form require fewer digits and is sparser than the JSF and the interleaving $w$-NAF. Its advantages are illustrated for elliptic curve double-scalar multiplication; the operation counts show a gain of up to 18\%.

2006

EPRINT

Extended Double-Base Number System with applications to Elliptic Curve Cryptography
Abstract

We investigate the impact of larger digit sets on the length of
Double-Base Number system (DBNS) expansions.
We present a new representation system called {\em extended DBNS}
whose expansions can be extremely sparse.
When compared with double-base chains, the average length of
extended DBNS expansions of integers of size in the range 200--500 bits
is approximately reduced by $20\%$ using one precomputed point, $30\%$ using two, and $38\%$ using
four.
We also discuss a new approach to approximate an integer $n$ by $d2^a3^b$ where $d$ belongs to a given digit set.
This method, which requires some precomputations as well, leads to realistic DBNS implementations.
Finally, a left-to-right scalar multiplication relying on extended DBNS is given.
On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to $13\%$
overall can be expected with this approach when compared to window NAF methods
using the same number of precomputed points.
In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a
generic elliptic curve.

2005

EPRINT

Fast Elliptic Curve Point Multiplication using Double-Base Chains
Abstract

Among the various arithmetic operations required in implementing public key
cryptographic algorithms, the elliptic curve point multiplication has probably
received the maximum attention from the research community in the
last decade.
Many methods for efficient and secure implementation of point
multiplication have been proposed.
The efficiency of these methods mainly depends on the representation
one uses for the scalar multiplier.
In the current work we propose an efficient algorithm based on the
so-called double-base number system.
We introduce the new concept of double-base chains which, if
manipulated with care, can significantly reduce the complexity of
scalar multiplication on elliptic curves.
Besides we have adopted some other measures to further reduce the
operation count.
Our algorithm compares favorably against classical and other
similar approaches.

2004

EPRINT

Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic
Abstract

We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a
subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$.
Using the Chinese Remainder Theorem, we represent the elements of
$\mathrm{GF}(2^k)$; i.e. the polynomials in
$\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder
modulo a set of $n$ pairwise prime trinomials,
$T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$.
Our algorithm is based on Montgomery's multiplication applied to the ring formed
by the direct product of the trinomials.

#### Coauthors

- Jithra Adikari (1)
- Jean-Claude Bajard (2)
- Guilhem Castagnos (1)
- Vassil S. Dimitrov (3)
- Christophe Doche (1)
- Eleonora Guerrini (1)
- Graham A. Jullien (1)
- Fabien Laguillaumie (1)
- Pierre-Yvan Liardet (1)
- Pradeep Kumar Mishra (2)
- Yannick Teglia (1)
- Théo Winterhalter (1)