Towards constant-time probabilistic root finding for code-based cryptography

• Dúnia Marchiori UFSC http://orcid.org/0000-0003-0501-8990
• Ricardo Custódio UFSC
• Daniel Panario Carleton University
• Lucia Moura University of Ottawa

DOI: https://doi.org/10.5753/sbseg.2021.17313

Resumo

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.

Palavras-chave: post-quantum cryptography, code-based cryptography, root-finding algorithms, probabilistic root finding

Referências

Berlekamp, E. R. (1967). Factoring polynomials over finite fields. Bell System Tech. J., 46:1853–1859.

Berlekamp, E. R. (1968). Algebraic Coding Theory. McGraw-Hill Book Co., New York.

Berlekamp, E. R. (1970). Factoring polynomials over large finite fields. Mathematics of computation, 24(111):713–735.

Bernstein, D. J. (2019). djbsort library. https://sorting.cr.yp.to/index.html.

Bernstein, D. J., Chou, T., Lange, T., von Maurich, I., Misoczki, R., Niederhagen, R., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., et al. (2020). Classic McEliece: conservative code-based cryptography. NIST PQC Round, 3.

Bernstein, D. J. and Yang, B.-Y. (2019). Fast constant-time GCD computation and modular inversion. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 340–398.

Cantor, D. G. and Zassenhaus, H. (1981). A new algorithm for factoring polynomials over finite fields. Mathematics of Computation, 36(154):587–592.

Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., and Vercauteren, F., editors (2006). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and Its Applications. Chapman & Hall/CRC, Boca Raton, FL.

Flajolet, P., Gourdon, X., and Panario, D. (1996). Random polynomials and polynomial factorization. In Meyer, F. and Monien, B., editors, Automata, Languages and Programming, pages 232–243, Berlin, Heidelberg. Springer Berlin Heidelberg.

Flajolet, P., Gourdon, X., and Panario, D. (2001). The complete analysis of a polynomial factorization algorithm over finite fields. J. Algorithms, 40(1):37–81.

Gao, S. and Mateer, T. (2010). Additive fast Fourier transforms over finite fields. IEEE Transactions on Information Theory, 56(12):6265–6272.

von zur Gathen, J. and Panario, D. (2001). Factoring polynomials over finite fields: a survey. J. Symbolic Comput., 31(1-2):3–17. Computational algebra and number theory (Milwaukee, WI, 1996).

von zur Gathen, J. and Shoup, V. (1992). Computing Frobenius maps and factoring polynomials. Computational complexity, 2(3):187–224.

Goppa, V. D. (1970). A new class of linear correcting codes. Problemy Peredachi Informatsii, 6(3):24–30.

Martins, D., Banegas, G., and Custódio, R. (2019). Don’t forget your roots: Constanttime root finding over F2m. In International Conference on Cryptology and Information Security in Latin America, pages 109–129. Springer.

McEliece, R. J. (1978). A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, 42-44:114–116.

Patterson, N. (1975). The algebraic decoding of goppa codes. IEEE Transactions on Information Theory, 21(2):203–207.

Pornin, T. (2018). Constant-time crypto. https://bearssl.org/constanttime.html.

Rabin, M. (1980). Probabilistic algorithms in finite fields. SIAM Journal on Computing, 9(2):273–280.

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.

Schipani, D. (2012). Efficient decoding of cyclic codes and applications in cryptography. PhD thesis, University of Zurich.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE.

Shoufan, A., Strenzke, F., Molter, H. G., and St¨ottinger, M. (2010). A timing attack against patterson algorithm in the McEliece PKC. In International Conference on Information Security and Cryptology, pages 161–175. Springer.

Strenzke, F., Tews, E., Molter, H. G., Overbeck, R., and Shoufan, A. (2008). Side channels in the McEliece PKC. In International Workshop on Post-Quantum Cryptography, pages 216–229. Springer.

Sumi, T., Morozov, K., and Takagi, T. (2011). Efficient implementation of the McEliece cryptosystem. In Computer Security Symposium 2011.