Secure and efficient software implementation of QC-MDPC code-based cryptography
Resumo
The emergence of quantum computers is pushing an unprecedented transition in the public key cryptography field. Algorithms in the current standard are vulnerable to attacks using quantum computers and need, therefore, to be replaced. Cryptosystems based on error-correcting codes are considered some of the most promising candidates to replace them for encryption schemes. Among the code families, QC-MDPC codes achieve the smallest key sizes while maintaining the desired security properties. Their performance, however, still needs to be greatly improved to reach a competitive level. In this work, we optimize the performance of QC-MDPC code-based cryptosystems through improvements concerning both their implementations and algorithms. We first present a new enhanced version of QcBits’ key encapsulation mechanism, which is a constant time implementation of the Niederreiter cryptosystem using QCMDPC codes. Comparing with the current state-of-the-art, the BIKE implementation, our code performs 1.9 times faster when decrypting messages. We then optimize the performance of QC-MDPC code-based cryptosystems through the insertion of a configurable failure rate in their arithmetic procedures. Using a failure rate negligible compared to the security level (2128), we achieve speedups of 1.6 to 2 times in some arithmetic algorithms. By inserting these algorithms in our enhanced version of QcBits, we were able to achieve a speedup of 1.9 on the key generation and up to 1.4 on the decryption time. Comparing with BIKE, our final version of QcBits performs the uniform decryption 2.7 times faster. Moreover, the techniques presented in this work can also be applied to BIKE, opening new possibilities for further improvements.
Referências
Chou, T. (2016). QcBits: Constant-Time Small-Key Code-Based Cryptography. In Gierlichs, B. and Poschmann, A. Y., editors, Cryptographic Hardware and Embedded Systems – CHES 2016, pages 280–300, Berlin, Heidelberg. Springer Berlin Heidelberg.
Guimarães, A., Aranha, D. F., and Borin, E. (2017). Optimizing the decoding process of a post-quantum cryptographic algorithm. XVIII Simpósio em Sistemas Computacionais de Alto Desempenho-WSCAD, 18(1/2017):160–171.
Guimarães, A., Borin, E., and Aranha, D. F. (2019). Introducing Arithmetic Failures to Accelerate QC-MDPC Code-Based Cryptography. In Baldi, M., Persichetti, E., and Santini, P., editors, Code-Based Cryptography, pages 44–68, Cham. Springer International Publishing.
Guimarães, A., Aranha, D. F., and Borin, E. (2018). Optimized implementation of QCMDPC code-based cryptography. Concurrency and Computation: Practice and Experience.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–209.
McEliece, R. J. (1978). A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114–116.
Misoczki, R., Tillich, J. P., Sendrier, N., and Barreto, P. S. L. M. (2013). MDPCMcEliece: New McEliece variants from Moderate Density Parity-Check codes. 2013 IEEE International Symposium on Information Theory, pages 2069–2073.
Moody, D. (2016). Post-quantum cryptography: NIST’s plan for the future. Talk given at PQCrypto. https://pqcrypto2016.jp/data/pqc2016_nist_announcement.pdf.
NIST (2016). Submission requirements and evaluation criteria for the postquantum cryptography standardization process. NIST web page. [link].
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126.
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.
Shoup, V. (2003). Number Theory C++ Library (NTL).
