Paper 2010/300 Original: eprint.iacr.org/2010/300 ↗

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

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.