On the enumeration of double-base chains with applications to elliptic curve cryptography

Christophe Doche*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

7 Citations (Scopus)

Abstract

The Double-Base Number System (DBNS) uses two bases, 2 and 3, in order to represent any integer n. A Double-Base Chain (DBC) is a special case of a DBNS expansion. DBCs have been introduced to speed up the scalar multiplication [n]P on certain families of elliptic curves used in cryptography. In this context, our contributions are twofold. First, given integers n, a, and b, we outline a recursive algorithm to compute the number of different DBCs with a leading factor dividing 2a3b and representing n. A simple modification of the algorithm allows to determine the number of DBCs with a specified length as well as the actual expansions. In turn, this gives rise to a method to compute an optimal DBC representing n, i.e. an expansion with minimal length. Our implementation is able to return an optimal expansion for most integers up to 260 bits in a few minutes. Second, we introduce an original and potentially more efficient approach to compute a random scalar multiplication [n]P, based on the concept of controlled DBC. Instead of generating a random integer n and then trying to find an optimal, or at least a short DBC to represent it, we propose to directly generate n as a random DBC with a chosen leading factor 2a3b and length ℓ. To inform the selection of those parameters, in particular ℓ, which drives the trade-off between the efficiency and the security of the underlying cryptosystem, we enumerate the total number of DBCs having a given leading factor 2a3b and a certain length ℓ. The comparison between this total number of DBCs and the total number of integers that we wish to represent a priori provides some guidance regarding the selection of suitable parameters. Experiments indicate that our new Near Optimal Controlled DBC approach provides a speedup of at least 10% with respect to the NAF for sizes from 192 to 512 bits. Computations involve elliptic curves defined over Fp, using the Inverted Edwards coordinate system and state of the art scalar multiplication techniques.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2014
Subtitle of host publication20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I
EditorsPalash Sarkar, Tetsu Iwata
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages297-316
Number of pages20
ISBN (Electronic)9783662456118
ISBN (Print)9783662456101
DOIs
Publication statusPublished - Dec 2014
Event20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT - 2014 - Kaohsiung, Taiwan, Province of China
Duration: 7 Dec 201411 Dec 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8873
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT - 2014
CountryTaiwan, Province of China
CityKaohsiung
Period7/12/1411/12/14

Fingerprint

Dive into the research topics of 'On the enumeration of double-base chains with applications to elliptic curve cryptography'. Together they form a unique fingerprint.

Cite this