Optimizing Elliptic Curve Scalar Multiplication with Near-Factorization

Pratik Poddar, Achin Bansal, Bernard Menezes

2014

Abstract

Elliptic curve scalar multiplication ( [k]P where k is an integer and P is a point on the elliptic curve) is widely used in encryption and signature generation. In this paper, we explore a factorization-based approach called Near-Factorization that can be used in conjunction with existing optimization techniques such as Window NAF (Non Adjacent Form). We present a performance model of Near-Factorization and validate model results with those from a simulation. We compare Near-Factorization with wNAF for a range of scalar sizes, window sizes, divisor lengths and Hamming weights of divisor. The use of Near-Factorization with wNAF results in a considerable reduction in the effective Hamming weight of the scalar and a reduction in overall computation cost for Koblitz curves.

Paper Citation

in Harvard Style

Poddar P., Bansal A. and Menezes B. (2014). Optimizing Elliptic Curve Scalar Multiplication with Near-Factorization . In Proceedings of the 11th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2014) ISBN 978-989-758-045-1, pages 361-370. DOI: 10.5220/0005058703610370

in Bibtex Style

@conference{secrypt14,
author={Pratik Poddar and Achin Bansal and Bernard Menezes},
title={Optimizing Elliptic Curve Scalar Multiplication with Near-Factorization},
booktitle={Proceedings of the 11th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2014)},
year={2014},
pages={361-370},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005058703610370},
isbn={978-989-758-045-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2014)
TI - Optimizing Elliptic Curve Scalar Multiplication with Near-Factorization
SN - 978-989-758-045-1
AU - Poddar P.
AU - Bansal A.
AU - Menezes B.
PY - 2014
SP - 361
EP - 370
DO - 10.5220/0005058703610370