Open AccessTowards constant-time probabilistic root finding for code-based cryptography
Author(s) -
Dúnia Marchiori,
Ricardo Felipe Custódio,
Daniel Panario,
Lucia Moura
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/sbseg.2021.17313
Subject(s) - probabilistic logic , computer science , cryptography , mceliece cryptosystem , cryptosystem , timing attack , algorithm , theoretical computer science , probabilistic analysis of algorithms , deterministic algorithm , code (set theory) , root (linguistics) , time complexity , side channel attack , artificial intelligence , set (abstract data type) , programming language , linguistics , philosophy
In code-based cryptography, deterministic algorithms are used in the root-finding step of the decryption process. However, probabilistic algorithms are more time efficient than deterministic ones for large fields. These algorithms can be useful for long-term security where larger parameters are relevant. Still, current probabilistic root-finding algorithms suffer from time variations making them susceptible to timing side-channel attacks. To prevent these attacks, we propose a countermeasure to a probabilistic root-finding algorithm so that its execution time does not depend on the degree of the input polynomial but on the cryptosystem parameters. We compare the performance of our proposed algorithm to other root-finding algorithms already used in code-based cryptography. In general, our method is faster than the straightforward algorithm in Classic McEliece. The results also show the range of degrees in larger finite fields where our proposed algorithm is faster than the Additive Fast Fourier Transform algorithm.