Algoritmos de Assinatura Digital Baseada em Reticulados Candidatos a Padrão Pós-Quântico

• Guilherme Belarmino UFABC
• Denise Goya UFABC

DOI: https://doi.org/10.5753/sbseg_estendido.2019.14010

Resumo

Avanços na construção de computadores quânticos e o fato de vários dos atuais padrões criptográficos serem inseguros na presença de um eventual computador quântico de maior porte levaram o NIST a promover um concurso de padronização de algoritmos pós-quânticos, caracterizados pela segurança em computadores convencionais e quânticos. Neste trabalho são comparados esquemas de assinatura digital baseada em reticulados que participam da segunda fase do concurso, com base nas propriedades, segurança e desempenho dos algoritmos.

Referências

Ajtai, M. (1996). Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 99–108. ACM.

Barreto, P., Biasi, F. P., Dahab, R., César, J., Pereira, G., and Ricardini, J. E. (2013). Introdução à criptograa pós-quântica. Minicursos do XIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais-SBSeg.

Bindel, N., Alkim, E., Barreto, P. S. L. M., Akleylek, S., Buchmann, J., , Eaton, E., Gutoski, G., Kramer, J., Longa, P., Polat, H., Ricardini, J. E., and Zanon, G. (2019). Submission to nist's post-quantum project (2nd round): lattice-based digital signature scheme qtesla. Disponível em: https://qtesla.org/wp-content/uploads/2019/04/qTESLA_round2_04.2019.pdf.

Blazy, O., Kakvi, S. A., Kiltz, E., and Pan, J. (2014). Tightly-secure signatures from chameleon hash functions. Cryptology ePrint Archive, Report 2014/1021. Disponível em: https://eprint.iacr.org/2014/1021.

Canetti, R. (2008). Lecture 8: Digital signatures. Último acesso em 22 ago 2018. Disponível em: https://www.cs.tau.ac.il/˜canetti/f08-materials/scribe8.pdf.

Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., and Smith-Tone, D. (2016). Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report 8105. Disponível em: https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf.

Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehlé, D. (2019). Crystals-dilithium algorithm specications and supporting docu- mentation. Disponível em: https://pq-crystals.org/dilithium/data/dilithium-specification-round2.pdf.

Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., and Zhang, Z. (2018). Falcon: Fast-fourier lattice-based compact signatures over ntru. Specications v1.1.

Gentry, C., Peikert, C., and Vaikuntanathan, V. (2007). Trapdoors for hard lattices and new cryptographic constructions. Cryptology ePrint Archive, Report 2007/432. Disponível em: https://eprint.iacr.org/2007/432.

Gérard, F. and Rossi, M. (2019). An efcient and provable masked implementation of qtesla. Cryptology ePrint Archive, Report 2019/606. https://eprint.iacr.org/2019/606.

Karmakar, A., Roy, S. S., Vercauteren, F., and Verbauwhede, I. (2019). Pushing the speed limit of constant-time discrete gaussian sampling. a case study on falcon. Cryptology ePrint Archive, Report 2019/267. Disponível em: https://eprint.iacr.org/2019/267.

Lu, X., Au, M. H., and Zhang, Z. (2018). Raptor: A practical lattice-based (linkable) ring signature. Cryptology ePrint Archive, Report 2018/857. Disponível em: https://eprint.iacr.org/2018/857.

Lyubashevsky, V. (2009). Fiat-shamir with aborts: Applications to lattice and factoring- based signatures. In Matsui, M., editor, Advances in Cryptology – ASIACRYPT 2009, pages 598–616, Berlin, Heidelberg. Springer Berlin Heidelberg.

Menezes, A. J., Vanstone, S. A., and Oorschot, P. C. V. (1996). Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition.

Migliore, V., Gérard, B., Tibouchi, M., and Fouque, P.-A. (2019). Masking dilithium: Efcient implementation and side-channel evaluation. Cryptology ePrint Archive, Report 2019/394. Disponível em: https://eprint.iacr.org/2019/394.

NIST (2016). Submission requirements and evaluation criteria for the postquantum cryptography standardization process. Último acesso em em 02 jun 2019. Disponível em: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

NIST (2019). Pqc standardization process: Second round candidate announcement. Último acesso em em 11 mar 2019. Disponível em: https://csrc.nist.gov/news/2019/pqc-standardization-process-2nd-round-candidates.

NIST, C. S. R. C. (2018). Post-quantum cryptography. Último acesso em 08 jul 2018. Disponível em https://csrc.nist.gov/Projects/Post-Quantum-Cryptography.

Prasanna Ravi, Mahabir Prasad Jhanwar, J. H. A. C. and Bhasin, S. (2018). Side-channel assisted existential forgery attack on dilithium - a nist pqc candidate. Cryptology ePrint Archive, Report 2018/821. Disponível em: https://eprint.iacr.org/2018/821.

Ravi, P., Jhanwar, M. P., Howe, J., Chattopadhyay, A., and Bhasin, S. (2019). Exploiting determinism in lattice-based signatures - practical fault attacks on pqm4 implementations of nist candidates. Cryptology ePrint Archive, Report 2019/769. https://eprint.iacr.org/2019/769.

Ravi, P., Roy, D. B., Bhasin, S., Chattopadhyay, A., and Mukhopadhyay, D. (2018). Number "not used"once - practical fault attack on pqm4 implementations of nist can- didates. Cryptology ePrint Archive, Report 2018/211. Disponível em: https: //eprint.iacr.org/2018/211.

Regev, O. (2006). Lattice-based cryptography. In Annual International Cryptology Con- ference, pages 131–141. Springer.

Regev, O. (2009). On lattices, learning with errors, random linear codes, and crypto- graphy. Journal of the ACM, 56(6):34. Preliminary version in STOC'05.

Regev, O. (2010). The learning with errors problem. In Proc. of 25th IEEE Annual Conference on Computational Complexity (CCC), pages 191–204.

Shor, P. (1997). Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer.