## CryptoDB

### Christophe Doche

#### Publications

**Year**

**Venue**

**Title**

2014

EPRINT

2014

ASIACRYPT

2008

EPRINT

Double-Base Number System for Multi-Scalar Multiplications
Abstract

The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form $[n]P+m[Q]$. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously $n$ and $m$. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can
find a chain of reasonable length that uses exactly the same terms to compute both $n$ and $m$. Furthermore, we discuss an algorithm to produce such a Joint Double-Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than $0.3945\log_2 n$. With respect to the Joint Sparse Form, this induces a reduction by more than $20\%$ of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, $P+Q$ and $P-Q$. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications.
Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves.
Our second contribution is a new way to evaluate $\overline\phi$, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute $\pm\overline\phi(P)$ with at most 2 multiplications and 2 squarings in $\F_{2^d}$. This represents a speed-up of about $50\%$ with respect to the fastest techniques known. This has very concrete consequences on scalar and multi-scalar multiplications on
Koblitz curves.

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

Efficient Scalar Multiplication by Isogeny Decompositions
Abstract

On an elliptic curve, the degree of an isogeny corresponds essentially to
the degrees of the polynomial expressions involved in its application.
The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore
the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$.
For a small prime $\ell\, (= 2, 3)$ such that the additive binary
representation provides no better performance, this represents the true
cost of application of scalar multiplication.
If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then
the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field
operations. Since we then have a product expression $[\ell] =
\hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on
an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to
$O(\ell)$ field operations for the evaluation of $[\ell](P)$ by na\"ive
application of the defining polynomials. In this work we investigate
actual improvements for small $\ell$ of this asymptotic complexity.
For this purpose, we describe the general construction of families of
curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$,
and provide explicit examples of such a family of curves with simple
decomposition for~$[3]$. Finally we derive a new tripling algorithm
to find complexity improvements to triplication on a curve in certain
projective coordinate systems, then combine this new operation to non-adjacent forms
for $\ell$-adic expansions in order to obtain an improved
strategy for scalar multiplication on elliptic curves.

2004

EPRINT

Redundant Trinomials for Finite Fields of Characteristic $2$
Abstract

In this paper we introduce a new way to represent elements of a finite field of
characteristic $2$.
We describe a new type of polynomial basis, called
{\it redundant trinomial basis}
and discuss how to implement it efficiently.
Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$
when no irreducible trinomial of degree $n$ exists.
Tests with {\tt NTL} show that
improvements for squaring and exponentiation are respectively
up to $45$\% and $25$\%.
More attention is given to relevant extension degrees for doing
elliptic and hyperelliptic curve cryptography.
For this range, a scalar multiplication can be speeded up by a factor up to $15$\%.

#### Program Committees

- Asiacrypt 2008

#### Coauthors

- Roberto Maria Avanzi (1)
- Vassil S. Dimitrov (1)
- Thomas Icart (2)
- Laurent Imbert (1)
- David Kohel (4)
- Francesco Sica (3)