On the low hamming weight discrete logarithm problem for nonadjacent representations

So-called nonadjacent representations are commonly used in elliptic curve cryptography to facilitate computing a scalar multiple of a point on an elliptic curve. A nonadjacent representation having few non-zero coefficients would further speed up the computations. However, any attempt to use these t...

Full description

Saved in:
Bibliographic Details
Published in:Applicable algebra in engineering, communication and computing communication and computing, 2006-01, Vol.16 (6), p.461-472
Main Authors: Muir, J.A., Stinson, D.R.
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Cryptography
Curves
Representations
Security
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:So-called nonadjacent representations are commonly used in elliptic curve cryptography to facilitate computing a scalar multiple of a point on an elliptic curve. A nonadjacent representation having few non-zero coefficients would further speed up the computations. However, any attempt to use these techniques must also consider the impact on the security of the cryptosystem. The security is studied by examining a related discrete logarithm problem, the topic of this paper. We describe an algorithm to solve the relevant discrete logarithm problem in time that is approximately the square root of the search space. This algorithm is of the familiar ``baby-step giant-step'' type. In developing our algorithm we use two tools of independent interest; namely, a combinatorial set system called a ``splitting system'' and a new type of combinatorial Gray code.
ISSN:0938-1279
1432-0622
DOI:10.1007/s00200-005-0187-7