## CryptoDB

### Pradeep Kumar Mishra

#### Affiliation: CISaC, University of Calgary, Canada.

#### 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.

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

Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Crytosystems
Abstract

Elliptic (ECC) and hyperelliptic curve cryptosystems (HECC) have emerged as cryptosystems of choice for small handheld and mobile devices. A lot of research has been devoted to the secure and efficient implementation on these devices. As such devices come with very low amount of resources, efficient memory management is an important issue in all such implementations. HECC arithmetic is now generally performed using so called explicit formulae. In literature, there is no result which focuses on the exact memory requirement for implementation these formulae. This is the first work to report such minimal memory requirement. Also, in the work we have provided a general methodology for realization of explicit formulae with minimal number of registers. Applying such methodology this work settles the issue for some important explicit formula available in the literature. This is an attempt to experimentally solve a particular instance based on HECC explicit formulae of the so called ``Register Sufficiency Problem", which is an NP-complete problem.

2005

EPRINT

A Metric on the Set of Elliptic Curves over ${\mathbf F}_p$
Abstract

Elliptic Curves over finite field have found application in many areas including cryptography. In the current article we define a metric on the set of elliptic curves defined over a prime field ${\mathbf F}_p, p>3$.

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

Scalar Multiplication in Elliptic Curve Cryptosystems: Pipelining with Pre-computations
Abstract

The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms the best known sequential and parallel schemes. On the security front, our algorithm uses two countermeasures against SPA and hence are doubly secured against SPA. Also, it is secure against DPA using the Joye-Tymen's curve randomization countermeasure.

2003

ASIACRYPT

2003

EPRINT

Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves
Abstract

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel
algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of
arithmetic using affine coordinates.

2003

EPRINT

Inversion of Several Field Elements: A New Parallel Algorithm
Abstract

In many crypographic hardware or software packages, a considerable part is devoted to finite field arithmetic. The finite field arithmetic is a very costly operation in comparison to other finite field operations. Taming the complexity of this operation has been a major challenge for researchers and implementers. One approach for the purpose is accumulate all the elements to be inverted and to compute several inversions simultaneously at the cost of one inversion and some multiplictions. One such algorithm is known as Montgomery's trick. However Montgomery's trick does not allow much parallelism. In~\cite{SMB03} an algorithm for computation of inverses of several field elements simultaneously in parallel has been proposed. The algorithm allows ample scope for parallelism and performes well if there is no restriction on the number of processors used. In the current work, we present an algorithm, which is same in complexity as Montgomery's trick but suitable for a parallel implementation. In parallel implementation, it computes inverse of $n$ elements in $2\log n$ parallel rounds. It performs better than both the previous algorithms under the circumstances where the restricted number of multipliers is used.

#### Coauthors

- Jithra Adikari (1)
- Vassil S. Dimitrov (4)
- Kishan Chand Gupta (1)
- Laurent Imbert (2)
- Pinakpani Pal (1)
- Palash Sarkar (5)