A Constant-time AVX2 Implementation of a Variant of ROLLO

Abstract

This paper introduces a key encapsulation mechanism ROLLO⁺ and presents a constant-time AVX2 implementation of it. ROLLO⁺ is a variant of ROLLO-I targeting IND-CPA security. The main difference between ROLLO+ and ROLLO-I is that the decoding algorithm of ROLLO⁺ is adapted from the decoding algorithm of ROLLO-I. Our implementation of ROLLO⁺-I-128, one of the level-1 parameter sets of ROLLO⁺, takes 851823 Skylake cycles for key generation, 30361 Skylake cycles for encapsulation, and 673666 Skylake cycles for decapsulation. Compared to the state-of-the-art implementation of ROLLO-I-128 by Aguilar-Melchor et al., which is claimed to be constant-time but actually is not, our implementation achieves a 12.9x speedup for key generation, a 10.6x speedup for encapsulation, and a 14.5x speedup for decapsulation. Compared to the state-of-the-art implementation of the level-1 parameter set of BIKE by Chen, Chou, and Krausz, our key generation time is 1.4x as slow, but our encapsulation time is 3.8x as fast, and our decapsulation time is 2.4x as fast.