## CryptoDB

### Francesco Sica

#### Affiliation: Nazarbayev University

#### Publications

**Year**

**Venue**

**Title**

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

Scalar Multiplication on Koblitz Curves using Double Bases
Abstract

The paper is an examination of double-base decompositions of
integers $n$, namely expansions loosely of the form
$$
n = \sum_{i,j} A^iB^j
$$
for some base $\{A,B\}$. This was examined in previous
works in the case when $A,B$ lie in
$\mathbb{N}$.
On the positive side, we show how to extend previous results
of to Koblitz curves over binary fields. Namely, we
obtain a sublinear scalar algorithm to compute, given a generic
positive integer $n$ and an elliptic curve point $P$, the point $nP$
in time $O\left(\frac{\log n}{\log\log n}\right)$ elliptic curve
operations with essentially no storage, thus making the method
asymptotically faster than any know scalar multiplication algorithm
on Koblitz curves.
On the negative side, we analyze scalar multiplication using double
base numbers and show that on a generic elliptic curve over a finite
field, we cannot expect a sublinear algorithm with double bases. Finally, we show that
all algorithms used hitherto need at least $\frac{\log n}{\log\log
n}$ curve operations.

2003

EUROCRYPT

#### Coauthors

- Roberto Maria Avanzi (3)
- Mathieu Ciet (3)
- Vassil S. Dimitrov (1)
- Christophe Doche (3)
- David Kohel (2)
- Tanja Lange (1)
- Patrick Longa (2)
- Jean-Jacques Quisquater (2)