Paper 2010/300

Optimal Average Joint Hamming Weight and Minimal Weight Conversion of d Integers

Vorapong Suppakitpaisarn, Masato Edahiro, and Hiroshi Imai

Abstract

In this paper, we propose the minimal joint Hamming weight conversion for any binary expansions of $d$ integers. With redundant representations, we may represent a number by many expansions, and the minimal joint Hamming weight conversion is the algorithm to select the expansion that has the least joint Hamming weight. As the computation time of the cryptosystem strongly depends on the joint Hamming weight, the conversion can make the cryptosystem faster. Most of existing conversions are limited to some specific representations, and are difficult to apply to other representations. On the other hand, our conversion is applicable to any binary expansions. The proposed can explore the minimal average weights in a class of representation that have not been found. One of the most interesting results is that, for the expansion of integer pairs when the digit set is $\{0, \pm 1, \pm 3\}$, we show that the minimal average joint Hamming weight is $0.3575$. This improves the upper bound value, $0.3616$, proposed by Dahmen, Okeya, and Takagi.

Metadata
Available format(s)
PDF PS
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptosystem
Contact author(s)
mr_t_dtone @ is s u-tokyo ac jp
History
2010-05-25: received
Short URL
https://ia.cr/2010/300
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/300,
      author = {Vorapong Suppakitpaisarn and Masato Edahiro and Hiroshi Imai},
      title = {Optimal Average Joint Hamming Weight and Minimal Weight Conversion of d Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2010/300},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/300}},
      url = {https://eprint.iacr.org/2010/300}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.