Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation

Yukio TSURUOKA; Kenji KOYAMA

Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation

Yukio TSURUOKA, Kenji KOYAMA

Full Text Views

0

Cite this

Summary :

To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {g^x1, g^x2, , g^xs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.1 pp.34-39

Publication Date: 1997/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Yukio TSURUOKA, Kenji KOYAMA, "Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 1, pp. 34-39, January 1997, doi: .
Abstract: To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {g^x1, g^x2, , g^xs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_1_34/_p

Copy

@ARTICLE{e80-a_1_34,
author={Yukio TSURUOKA, Kenji KOYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation},
year={1997},
volume={E80-A},
number={1},
pages={34-39},
abstract={To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {g^x1, g^x2, , g^xs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Fast Exponentiation Algorithms Based on Batch-Processing and Precomputation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 34
EP - 39
AU - Yukio TSURUOKA
AU - Kenji KOYAMA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1997
AB - To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {g^x1, g^x2, , g^xs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.
ER -