Paper 2020/1066

Constant time algorithms for ROLLO-I-128

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
code-based cryptographyKEMpost-quantum cryptographyrank metricconstant time
Contact author(s)
eemanuele bellini @ gmail com
2020-09-03: received
Short URL
Creative Commons Attribution


      author = {Carlos Aguilar-Melchor and Nicolas Aragon and Emanuele Bellini and Florian Caullery and Rusydi H.  Makarim and Chiara Marcolla},
      title = {Constant time algorithms for ROLLO-I-128},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1066},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.