## CryptoDB

#### Publications

Year
Venue
Title
2008
EPRINT
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
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
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
ASIACRYPT
2005
EPRINT
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
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
CHES
2004
PKC
2004
EPRINT
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
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
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.