Digital Signatures in a Quantum World: Evaluating The Trade-off Between Performance and Security for GeMSS
Resumo
With the advent of quantum computing, it urges the definition of a cryptographic standard algorithm that can resist attacks from a quantum computer. Inside this context is GeMSS, a multivariate quadratic signature scheme based on the HFEvconstruct. Schemes of this type have shown great potential throughout the last two decades. This paper traces a comparison of performance and security between GeMSS and other relevant digital signature schemes, showing that despite of its slow signature generation and large key pair, it has a very quick verification process and tiny signatures. It also proposes a method for deriving the size of keys from the security parameter evaluated.Referências
Andrade, E. R. (2013). Proposta de aprimoramento para o protocolo de assinatura digital Quartz. PhD thesis, Universidade de São Paulo.
Bardet, M., Faugére, J., Salvy, B., and Spaenlehauer, P. (2011). On the complexity of solving quadratic boolean systems. CoRR, abs/1112.6263.
Bernstein, D. J. (2009). Introduction to post-quantum cryptography. In Post-quantum cryptography, pages 1–14. Springer.
Bouillaguet, C., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., and Yang, B.-Y. (2010). Fast exhaustive search for polynomial systems in f2. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 203–218. Springer.
Casanova, A., Faugére, J.-C., Macario-Rat, G., Patarin, J., Perret, L., and Ryckeghem, J. (2017). Gemss: A great multivariate short signature. UPMC-Paris 6 Sorbonne Universités.
Faugere, J.-C., Horan, K., Kahrobaei, D., Kaplan, M., Kashe, E., and Perret, L. (2017). Fast quantum algorithm for solving multivariate quadratic equations. arXiv preprint arXiv:1712.07211.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, pages 212–219. ACM.
Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R., and Yu, H. (2017). Beating brute In Proceedings of the force for systems of polynomial equations over nite elds. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2190– 2202. SIAM.
Moody, D., Alagic, G., Alperin-Sheriff, J. M., Apon, D. C., Cooper, D. A., Dang, Q. H., Liu, Y.-K., Miller, C. A., Peralta, R. C., Perlner, R. A., et al. (2019). Status report on the rst round of the nist post-quantum cryptography standardization process. Technical report, National Institute of Standards and Technology.
Nielsen, M. A. and Chuang, I. (2002). Quantum computation and quantum information. AAPT.
Patarin, J. (1995). Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'88. In Annual International Cryptology Conference, pages 248–261. Springer.
Patarin, J. (1996). Hidden elds equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 33–48. Springer.
Patarin, J., Courtois, N., and Goubin, L. (2001). Quartz, 128-bit long digital signatures. In Cryptographers' Track at the RSA Conference, pages 282–297. Springer.
Patarin, J. and Goubin, L. (1997). Trapdoor one-way permutations and multivariate polynomials. In International Conference on Information and Communications Security, pages 356–368. Springer.
Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., and Ding, J. (2015). Design principles for hfevbased multivariate signature schemes. In Iwata, T. and Cheon, J. H., editors, Advances in Cryptology – ASIACRYPT 2015, pages 311–334, Berlin, Heidelberg. Springer Berlin Heidelberg.
Schwabe, P. andWesterbaan, B. (2016). Solving binary mq with grover’s algorithm. In International Conference on Security, Privacy, and Applied Cryptography Engineering, pages 303–322. Springer.
Shamir, A. and Kipnis, A. (1999). Cryptanalysis of the hfe public key cryptosystem. In Advances in Cryptology, Proceedings of Crypto, volume 99.
Shor, P. W. (1995). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509.
von zur Gathen, J. and Gerhard, J. (2003). Modern Computer Algebra. Cambridge University Press.
Bardet, M., Faugére, J., Salvy, B., and Spaenlehauer, P. (2011). On the complexity of solving quadratic boolean systems. CoRR, abs/1112.6263.
Bernstein, D. J. (2009). Introduction to post-quantum cryptography. In Post-quantum cryptography, pages 1–14. Springer.
Bouillaguet, C., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., and Yang, B.-Y. (2010). Fast exhaustive search for polynomial systems in f2. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 203–218. Springer.
Casanova, A., Faugére, J.-C., Macario-Rat, G., Patarin, J., Perret, L., and Ryckeghem, J. (2017). Gemss: A great multivariate short signature. UPMC-Paris 6 Sorbonne Universités.
Faugere, J.-C., Horan, K., Kahrobaei, D., Kaplan, M., Kashe, E., and Perret, L. (2017). Fast quantum algorithm for solving multivariate quadratic equations. arXiv preprint arXiv:1712.07211.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, pages 212–219. ACM.
Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R., and Yu, H. (2017). Beating brute In Proceedings of the force for systems of polynomial equations over nite elds. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2190– 2202. SIAM.
Moody, D., Alagic, G., Alperin-Sheriff, J. M., Apon, D. C., Cooper, D. A., Dang, Q. H., Liu, Y.-K., Miller, C. A., Peralta, R. C., Perlner, R. A., et al. (2019). Status report on the rst round of the nist post-quantum cryptography standardization process. Technical report, National Institute of Standards and Technology.
Nielsen, M. A. and Chuang, I. (2002). Quantum computation and quantum information. AAPT.
Patarin, J. (1995). Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt'88. In Annual International Cryptology Conference, pages 248–261. Springer.
Patarin, J. (1996). Hidden elds equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 33–48. Springer.
Patarin, J., Courtois, N., and Goubin, L. (2001). Quartz, 128-bit long digital signatures. In Cryptographers' Track at the RSA Conference, pages 282–297. Springer.
Patarin, J. and Goubin, L. (1997). Trapdoor one-way permutations and multivariate polynomials. In International Conference on Information and Communications Security, pages 356–368. Springer.
Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C., and Ding, J. (2015). Design principles for hfevbased multivariate signature schemes. In Iwata, T. and Cheon, J. H., editors, Advances in Cryptology – ASIACRYPT 2015, pages 311–334, Berlin, Heidelberg. Springer Berlin Heidelberg.
Schwabe, P. andWesterbaan, B. (2016). Solving binary mq with grover’s algorithm. In International Conference on Security, Privacy, and Applied Cryptography Engineering, pages 303–322. Springer.
Shamir, A. and Kipnis, A. (1999). Cryptanalysis of the hfe public key cryptosystem. In Advances in Cryptology, Proceedings of Crypto, volume 99.
Shor, P. W. (1995). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509.
von zur Gathen, J. and Gerhard, J. (2003). Modern Computer Algebra. Cambridge University Press.
Publicado
02/09/2019
Como Citar
REIS, Paulo Ricardo; BORGES, Fábio.
Digital Signatures in a Quantum World: Evaluating The Trade-off Between Performance and Security for GeMSS. In: WORKSHOP DE REGULAÇÃO, AVALIAÇÃO DA CONFORMIDADE E CERTIFICAÇÃO DE SEGURANÇA, 5. , 2019, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 23-32.
DOI: https://doi.org/10.5753/wrac.2019.14034.
