## CryptoDB

### Vassil S. Dimitrov

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Fast Multiple Point Multiplication on Elliptic Curves over Prime and Binary Fields using the Double-Base Number System
Abstract

Multiple-point multiplication on elliptic curves is
the highest computational complex operation in the elliptic curve
cyptographic based digital signature schemes. We describe three
algorithms for multiple-point multiplication on elliptic curves
over prime and binary fields, based on the representations
of two scalars, as sums of mixed powers of 2 and 3. Our
approaches include sliding window mechanism and some precomputed
values of points on the curve. A proof for formulae to
calculate the number of double-based elements, doublings and
triplings below 2^n is listed. Affine coordinates and Jacobian
coordinates are considered in both prime fields and binary fields.
We have achieved upto 24% of improvements in new algorithms
for multiple-point multiplication.

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\%.

2007

EPRINT

Efficient Quintuple Formulas for Elliptic Curves and Efficient Scalar Multiplication Using Multibase Number Representation
Abstract

In the current work we propose two efficient formulas for computing the $5$-fold ($5P$) of an elliptic curve point $P$. One formula is for curves over finite fields of even characteristic and the other is for curves over prime fields. Double base number systems (DBNS) have been gainfully exploited to compute scalar multiplication efficiently in ECC. Using the proposed point quintupling formulas one can use 2,5 and 3,5 (besides 3,5) as bases of the double base number system. In the current work we propose a scalar multiplication algorithm, which expands the scalar using three bases 2, 3 and 5 and computes the scalar multiplication very efficiently. The proposed scheme is faster than all sequential scalar multiplication algorithms reported in literature.

2006

EPRINT

Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation
Abstract

We describe algorithms for point multiplication on Koblitz curves
using multiple-base expansions of the form $k = \sum \pm \tau^a
(\tau-1)^b$ and $k= \sum \pm \tau^a (\tau-1)^b (\tau^2 - \tau - 1)^c.$
We prove that the number of terms in the second type is sublinear in
the bit length of k, which leads to the first provably sublinear point
multiplication algorithm on Koblitz curves. For the first type, we
conjecture that the number of terms is sublinear and provide
numerical evidence demonstrating that the number of terms is
significantly less than that of $\tau$-adic non-adjacent form
expansions. We present details of an innovative FPGA
implementation of our algorithm and performance data demonstrating the
efficiency of our method.

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.

#### Coauthors

- Jithra Adikari (2)
- Roberto Maria Avanzi (1)
- W. F. Chan (2)
- Christophe Doche (1)
- Z. Huang (2)
- Laurent Imbert (3)
- M. J. Jacobson (2)
- K.U. Jaervinen (1)
- Kimmo U. Järvinen (3)
- Pradeep Kumar Mishra (4)
- Sujoy Sinha Roy (2)
- Francesco Sica (1)
- Ingrid Verbauwhede (2)
- Frederik Vercauteren (2)