Generating, uniformly at random, a binary or a ternary string with a fixed lengthLand a prescribed weightW, is a step in several quantum safe cryptosystems (e. g., BIKE, NTRUEncrypt, NTRU LPrime, Lizard, McEliece). This fixed-weight-vector selection generation is often implemented via a shuffling method or a rejection method, but not always in “constant time” side channel protected flow. A recently suggested constant time algorithm for this problem, uses Network Sorting and turns out to be quite efficient. This paper proposes a new method for this computation, with a side channel protected implementation. We compare it to the other methods for different combinations of L and W values. Our method turns out to be the fastest approach for the cases where L is (relatively) short and 0.1 < W/L ≤ 0.5. For example, this range falls within the parameters of NTRU LPrime, where our method achieves a 3× speedup in the string generation. This leads to an overall 1.14× speedup for the NTRU LPrime key generation.
Research areas
