Optimizing the Decoding Process of a Post-Quantum Cryptographic Algorithm
Resumo
QcBits is a state-of-the-art constant-time implementation of a code-based encryption scheme for post-quantum public key cryptography. This paper presents an optimized version of its decoding process, which is used for message decryption. Our implementation leverages SSE and AVX instructions extensions and performs 3.6 to 4.8 times faster than the original version, while preserving the 80-bit security level and constant time execution. We also provide experimental data that indicates a further 1.4-factor speedup supposing the existence of instructions for vectorial conditional moves and 256-bit register shifts. Finally, we implemented countermeasures for side-channel security and showed that they do not affect the overall performance.
Referências
Bernstein, D. J., Lange, T., and Peters, C. (2008). Attacking and defending the mceliece cryptosystem. Cryptology ePrint Archive, Report 2008/318. http://eprint. iacr.org/2008/318.
Chang, C., Yao, S., and Yu, D. (2015). Vectorized big integer operations for cryptosystems In High Performance Computing (HiPC), 2015 IEEE on the intel mic architecture. 22nd International Conference on, pages 194–203. IEEE.
Chou, T. (2016). Qcbits: constant-time small-key code-based cryptography. In International Conference on Cryptographic Hardware and Embedded Systems, pages 280– 300. Springer.
Faugere, J.-C., Otmani, A., Perret, L., and Tillich, J.-P. (2010). Algebraic cryptanalysis of mceliece variants with compact keys. In Eurocrypt, pages 279–298. Springer.
Fog, A. (2011). Instruction tables: Lists of instruction latencies, throughputs and microoperation breakdowns for intel, amd and via cpus. Copenhagen University College of Engineering.
Gueron, S. and Kounavis, M. E. (2010). Intel® carry-less multiplication instruction and its usage for computing the gcm mode. White Paper.
Guo, Q., Johansson, T., and Stankovski, P. (2016). A key recovery attack on mdpc with In Advances in Cryptology–ASIACRYPT 2016, cca security using decoding errors. pages 789–815. Springer.
Hamburg, M. (2012). Fast and compact elliptic-curve cryptography. IACR Cryptology ePrint Archive.
Hu, J. and Cheung, R. C. (2017). Area-time efcient computation of niederreiter encryption on qc-mdpc codes for embedded hardware. IEEE Transactions on Computers.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation.
Lomont, C. (2011). Introduction to intel advanced vector extensions. Intel White Paper.
Maurich, I. V., Oder, T., and Güneysu, T. (2015). Implementing qc-mdpc mceliece encryption. ACM Transactions on Embedded Computing Systems (TECS).
McEliece, R. J. (1978). A public-key cryptosystem based on algebraic. Coding Thv.
Misoczki, R. and Barreto, P. S. (2009). Compact mceliece keys from goppa codes. In Selected Areas in Cryptography, pages 376–392. Springer.
Misoczki, R., Tillich, J.-P., Sendrier, N., and Barreto, P. S. (2013). Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 2069–2073. IEEE.
Nascimento, E., Chmielewski, L., Oswald, D., and Schwabe, P. (2016). Attacking emIACR Cryptology ePrint bedded ecc implementations through cmov side channels. Archive.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.
Rossi, M., Hamburg, M., Hutter, M., and Marson, M. E. (2017). A side-channel assisted cryptanalytic attack against qcbits. Cryptology ePrint Archive, Report 2017/596. http://eprint.iacr.org/2017/596.
Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review.
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.
Chang, C., Yao, S., and Yu, D. (2015). Vectorized big integer operations for cryptosystems In High Performance Computing (HiPC), 2015 IEEE on the intel mic architecture. 22nd International Conference on, pages 194–203. IEEE.
Chou, T. (2016). Qcbits: constant-time small-key code-based cryptography. In International Conference on Cryptographic Hardware and Embedded Systems, pages 280– 300. Springer.
Faugere, J.-C., Otmani, A., Perret, L., and Tillich, J.-P. (2010). Algebraic cryptanalysis of mceliece variants with compact keys. In Eurocrypt, pages 279–298. Springer.
Fog, A. (2011). Instruction tables: Lists of instruction latencies, throughputs and microoperation breakdowns for intel, amd and via cpus. Copenhagen University College of Engineering.
Gueron, S. and Kounavis, M. E. (2010). Intel® carry-less multiplication instruction and its usage for computing the gcm mode. White Paper.
Guo, Q., Johansson, T., and Stankovski, P. (2016). A key recovery attack on mdpc with In Advances in Cryptology–ASIACRYPT 2016, cca security using decoding errors. pages 789–815. Springer.
Hamburg, M. (2012). Fast and compact elliptic-curve cryptography. IACR Cryptology ePrint Archive.
Hu, J. and Cheung, R. C. (2017). Area-time efcient computation of niederreiter encryption on qc-mdpc codes for embedded hardware. IEEE Transactions on Computers.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation.
Lomont, C. (2011). Introduction to intel advanced vector extensions. Intel White Paper.
Maurich, I. V., Oder, T., and Güneysu, T. (2015). Implementing qc-mdpc mceliece encryption. ACM Transactions on Embedded Computing Systems (TECS).
McEliece, R. J. (1978). A public-key cryptosystem based on algebraic. Coding Thv.
Misoczki, R. and Barreto, P. S. (2009). Compact mceliece keys from goppa codes. In Selected Areas in Cryptography, pages 376–392. Springer.
Misoczki, R., Tillich, J.-P., Sendrier, N., and Barreto, P. S. (2013). Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 2069–2073. IEEE.
Nascimento, E., Chmielewski, L., Oswald, D., and Schwabe, P. (2016). Attacking emIACR Cryptology ePrint bedded ecc implementations through cmov side channels. Archive.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.
Rossi, M., Hamburg, M., Hutter, M., and Marson, M. E. (2017). A side-channel assisted cryptanalytic attack against qcbits. Cryptology ePrint Archive, Report 2017/596. http://eprint.iacr.org/2017/596.
Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review.
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.
Publicado
17/10/2017
Como Citar
GUIMARÃES, Antonio; F. ARANHA, Diego; BORIN, Edson.
Optimizing the Decoding Process of a Post-Quantum Cryptographic Algorithm. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 18. , 2017, Campinas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 160-171.
DOI: https://doi.org/10.5753/wscad.2017.247.
