Multi-base number representation in application to scalar multiplication and pairing computation

Elliptic curves scalar multiplication over finite fields has become a highly active research area. The efficiency of elliptic curves scalar multiplication is about keeping the memory and running time to be as low as possible. Providing new methods using chains beyond the binary chain will increase t...

Full description

Saved in:

Bibliographic Details
Main Author:	Mohammed Ismail, Abdelwahed
Format:	Thesis
Language:	English English
Published:	2011
Subjects:	Scalar field theory Number theory
Online Access:	http://psasir.upm.edu.my/id/eprint/26781/1/IPM%202011%2018R.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-upm-ir.26781
record_format	uketd_dc
spelling	my-upm-ir.267812022-01-26T05:37:11Z Multi-base number representation in application to scalar multiplication and pairing computation 2011-04 Mohammed Ismail, Abdelwahed Elliptic curves scalar multiplication over finite fields has become a highly active research area. The efficiency of elliptic curves scalar multiplication is about keeping the memory and running time to be as low as possible. Providing new methods using chains beyond the binary chain will increase the efficiency and speed of elliptic based curve cryptosystems. In this work, an extension of Greedy algorithm called xGreedy, is proposed. It finds the best approximated powers of each base to be used to convert large integers to new addition chains. Then multi-bases number representation is applied to produce new elliptic curve single-scalar multiplication algorithm. Multi-base chains are provided with and without doubling operation. Due to the efficiency of point halving and its low costs,for ordinary curves defined over binary finite fields, the results show fewer arithmetic operations. The multi-bases number representation is also applied to construct another new elliptic curve joint-scalar multiplication algorithm, called the joint-multi base algorithm. This method computes two scalar multiplications simultaneously using multi bases in the chain. The joint-scalar is important in applications related to digital signature verification, such as elliptic curve digital signature algorithm and El Gamal signature scheme. The method is evaluated over different coordinate systems. The results show clear improvement compared to some previous methods proposed for the same purpose. The efficiency of pairing-based cryptosystems depends on the elliptic curves scalar multiplication efficiency. Miller’s algorithm for computing the Tate pairing, originally used the binary chains with corresponding point doubling operation in evaluating the rational function. Multi-bases number representation is used to construct new versions of Miller’s algorithm. These algorithms are formulated for computing Tate and ate pairing. The theoretical calculations and analyses are focused on the Tate pairing. The results show a speeding up. All the above developments are aimed at reducing the running cost of the pairing computation in pairing-based cryptosystems. Scalar field theory Curves, Elliptic Number theory 2011-04 Thesis http://psasir.upm.edu.my/id/eprint/26781/ http://psasir.upm.edu.my/id/eprint/26781/1/IPM%202011%2018R.pdf application/pdf en public doctoral Universiti Putra Malaysia Scalar field theory Curves, Elliptic Number theory Institute for Mathematical Research English
institution	Universiti Putra Malaysia
collection	PSAS Institutional Repository
language	English English
topic	Scalar field theory Scalar field theory Number theory
spellingShingle	Scalar field theory Scalar field theory Number theory Mohammed Ismail, Abdelwahed Multi-base number representation in application to scalar multiplication and pairing computation
description	Elliptic curves scalar multiplication over finite fields has become a highly active research area. The efficiency of elliptic curves scalar multiplication is about keeping the memory and running time to be as low as possible. Providing new methods using chains beyond the binary chain will increase the efficiency and speed of elliptic based curve cryptosystems. In this work, an extension of Greedy algorithm called xGreedy, is proposed. It finds the best approximated powers of each base to be used to convert large integers to new addition chains. Then multi-bases number representation is applied to produce new elliptic curve single-scalar multiplication algorithm. Multi-base chains are provided with and without doubling operation. Due to the efficiency of point halving and its low costs,for ordinary curves defined over binary finite fields, the results show fewer arithmetic operations. The multi-bases number representation is also applied to construct another new elliptic curve joint-scalar multiplication algorithm, called the joint-multi base algorithm. This method computes two scalar multiplications simultaneously using multi bases in the chain. The joint-scalar is important in applications related to digital signature verification, such as elliptic curve digital signature algorithm and El Gamal signature scheme. The method is evaluated over different coordinate systems. The results show clear improvement compared to some previous methods proposed for the same purpose. The efficiency of pairing-based cryptosystems depends on the elliptic curves scalar multiplication efficiency. Miller’s algorithm for computing the Tate pairing, originally used the binary chains with corresponding point doubling operation in evaluating the rational function. Multi-bases number representation is used to construct new versions of Miller’s algorithm. These algorithms are formulated for computing Tate and ate pairing. The theoretical calculations and analyses are focused on the Tate pairing. The results show a speeding up. All the above developments are aimed at reducing the running cost of the pairing computation in pairing-based cryptosystems.
format	Thesis
qualification_level	Doctorate
author	Mohammed Ismail, Abdelwahed
author_facet	Mohammed Ismail, Abdelwahed
author_sort	Mohammed Ismail, Abdelwahed
title	Multi-base number representation in application to scalar multiplication and pairing computation
title_short	Multi-base number representation in application to scalar multiplication and pairing computation
title_full	Multi-base number representation in application to scalar multiplication and pairing computation
title_fullStr	Multi-base number representation in application to scalar multiplication and pairing computation
title_full_unstemmed	Multi-base number representation in application to scalar multiplication and pairing computation
title_sort	multi-base number representation in application to scalar multiplication and pairing computation
granting_institution	Universiti Putra Malaysia
granting_department	Institute for Mathematical Research
publishDate	2011
url	http://psasir.upm.edu.my/id/eprint/26781/1/IPM%202011%2018R.pdf
_version_	1747811560978382848

Multi-base number representation in application to scalar multiplication and pairing computation

Similar Items