Analysis of Low Hamming Weight Products

Hoffstein and Silverman suggested a use of Low Hamming Weight Product (LHWP) to compute a random power in a group or a multiple of an element in a ring. It reduces the computation of powers in a group with fast endomorphisms such as the Galois field F2nF2n and Koblitz elliptic curves. In this paper, we introduce a reduced representation of LHWP and apply them to attack the relevant cryptosystems.