Random small Hamming weight products with applications to cryptography

AbstractThere are many cryptographic constructions in which one uses a random power or multiple of an element in a group or a ring. We describe a fast method to compute random powers and multiples in certain important situations including powers in the Galois field F2n, multiples on Koblitz elliptic curves, and multiples in NTRU convolution polynomial rings. The underlying idea is to form a random exponent or multiplier as a product of factors, each of which has low Hamming weight when expanded as a sum of powers of some fast operation