Cryptology ePrint Archive: Report 2020/1066

Constant time algorithms for ROLLO-I-128

Carlos Aguilar-Melchor and Nicolas Aragon and Emanuele Bellini and Florian Caullery and Rusydi H. Makarim and Chiara Marcolla

Abstract: In this work, we propose different techniques that can be used to implement the ROLLO, and partially RQC, family of algorithms in a standalone, efficient and constant time library. For simplicity, we focus our attention on one specific instance of this family, ROLLO-I-128. For each of these techniques, we present explicit code (with intrinsics when required), or pseudo-code and performance measures to show their impact. More precisely, we use a combination of original and known results and describe procedures for Gaussian reduction of binary matrices, generation of vectors of given rank, multiplication with lazy reduction and inversion of polynomials in a composite Galois field. We also carry out a global performance analysis to show the impact of these improvements on ROLLO-I-128. Through the SUPERCOP framework, we compare it to other 128-bit secure KEMs in the NIST competition. To our knowledge, this is the first optimized full constant time implementation of ROLLO-I-128.

Category / Keywords: implementation / code-based cryptography, KEM, post-quantum cryptography, rank metric, constant time

Date: received 3 Sep 2020

Contact author: eemanuele bellini at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200903:082942 (All versions of this report)

Short URL: ia.cr/2020/1066


[ Cryptology ePrint archive ]