Root finding in code-based cryptography

Abstract

O criptossistema de McEliece foi o primeiro criptossistema de chave pública baseado em código de correção de erros. O esquema se mantém resistente a ataques feitos nos últimos 40 anos e, por isso, é utilizado como base para criptossistemas propostos em processos de padronização em criptografia pós-quântica. Mas, apesar do criptossistema de McEliece ser considerado seguro contra ataques de adversários com computadores quânticos, ele ainda pode sofrer outros tipos de ataques. Um exemplo são ataques de efeito colateral de temporização, como um ataque que explora a variação no tempo de execução do processo de encontrar as raízes de um polinômio durante a decodificação. Portanto, é importante que os algoritmos de encontrar raízes utilizados em criptossistemas não apresentem diferenças no tempo de execução que possam ser exploradas, como diferenças influenciadas por valores que façam parte do segredo do criptossistema. Algoritmos probabilísticos de encontrar raízes de polinômios ainda não foram aplicados em criptossistemas baseados em códigos. Um obstáculo se deve ao seu tempo de execução não constante, já que variações no tempo de execução podem ser exploradas por técnicas de ataques de efeito colateral. Este trabalho tem o objetivo de criar uma abordagem de tempo constante para algoritmos probabilísticos para que criptossistemas possam se beneficiar de sua eficiência, principalmente no caso de parâmetros maiores do que os utilizados hoje. A contramedida proposta neste trabalho previne que o tempo de execução de um algoritmo probabilístico de encontrar raízes de polinômios seja dependente do grau do polinômio, tornando-o dependente apenas no valor dos parâmetros do criptossistema. O desempenho da nossa proposta é comparada com a de outros algoritmos de encontrar raízes de polinômios utilizados em criptossistemas baseados em códigos e em trabalhos correlatos. Além disso, também é avaliado que a contramedida proposta pode ser aplicada de forma eficaz em outros algoritmos de encontrar raízes. Em geral, nosso método é mais rápido que o algoritmo exaustivo utilizado no Classic McEliece, uma variante do Berlekamp Trace Algorithm, e o algoritmo additive Fast Fourier Transform para parâmetros plausíveis em corpos finitos grandes.

Abstract: The McEliece cryptosystem was the first asymmetric cryptosystem based on error-correcting codes. It has resisted attacks for more than 40 years, which lead to it being the basis of some cryptosystem proposals in post-quantum cryptography standardization processes. Although the McEliece cryptosystem is believed to be secure against quantum attacks, it can still be subject to other types of attacks, such as side-channel attacks. One example is a timing side-channel attack that exploits the variations in execution time of the root-finding step during decoding. Thus, it is important that the root-finding algorithms used in a cryptosystem should not present differences in running time that could be exploited, that is, differences that can be tied to secret elements of the cryptosystem. Probabilistic algorithms for finding roots of polynomials have not been applied to code-based cryptography before. One obstacle is their non-constant execution time, since runtime variations can be exploited by side channel attack techniques. We aim to create a constant-time approach to probabilistic algorithms so cryptosystems can benefit from these algorithms' efficiency, especially when considering larger parameters. Our countermeasure prevents that the execution time of a probabilistic root-finding algorithm be dependent on the degree of the input polynomial and makes it dependent only on the cryptosystem parameters. We compare the performance of our proposal to other root-finding algorithms already used in code-based cryptography and related works. We also show that our countermeasure can be applied to other root-finding algorithms successfully. In general, our method is faster than a variant of the Berlekamp Trace Algorithm, the exhaustive algorithm in Classic McEliece and the additive Fast Fourier Transform algorithm for plausible parameters with larger finite fields.