Scientific Paper: Constant Time Algorithms for ROLLO-I-128
Authors: Carlos Aguilar-Melchor, Nicolas Aragon, Emanuele Bellini, Florian Caullery, Rusydi H. Makarim and Chiara Marcolla
Cryptographers have long recognized that quantum computers could break existing cryptographic systems to secure data, financial systems, and the Internet. This has invigorated a wide-ranging effort to discover, analyze, and test various alternative cryptographic systems resistant to quantum computing attacks.
Researchers at the Technology Innovation Institute’s Cryptography Research Centre in the UAE have spearheaded research into several promising post-quantum cryptography (PQC) alternative systems, including ROLLO-I-128. This is a promising type of Rank Metric algorithm, which can be seen as part of the code-based cryptographic family of PQC.
One implementation of the ROLLO-I-128 algorithm was previously submitted to the US National Institute of Standards and Technology (NIST) PQC standardization process. “However, it was eliminated because there has not been enough scrutiny by the research community since it is based on a relatively new technique,” said Emanuele Bellini, a principal cryptographer at CRC. “One of the things that was missing was a complete side-channel resistant implementation of this scheme.”
To address these concerns, researchers at TII, in collaboration with researchers from ISAE-SUPAERO, Université de Toulouse (Toulouse, France) and Université de Limoges (Limoges Cedex, France), found a way to harden ROLLO-I-128 against time-based side-channel attacks. In general, side-channel attacks look for weaknesses in how cryptographic algorithms are implemented to allow an attacker to analyze or break cryptographic systems. One type of side-channel attack looks for minor variations in the amount of time to run calculations. The new ROLLO-I-128 implementation ensures that calculations run in constant time, protecting the algorithm from timing-based attacks.
Although NIST rejected a prior ROLLO-I-128 implementation proposal, there is a possibility they will consider new rank-based implementations exploiting similar techniques as in ROLLO-I-128 as part of a future call for proposals for new cryptographic signature schemes. And even if it does not become part of the official NIST standard, a robust implementation could still provide value for commercial security tools.
For example, one of the potential advantages of ROLLO-I-128 is that it is relatively fast at key encapsulation, which is one important step of key encapsulation schemes. The two other steps are key generation and key decapsulation. This could demonstrate benefits in applications where a larger number of low-powered devices need to share secrets, by “encapsulating” them, with a more powerful server who will then decapsulate the secrets that will be used to establish a secure symmetric encryption.
Bellini hopes that this research will inspire further investigation of the ROLLO-I-128 by the global research community to identify additional opportunities for improvement.