Implementação Paralela do Algoritmo de Geração de Chaves do Esquema de Assinatura Digital XMSS (eXtended Merkle Signature Scheme)
Abstract
Hash Based Signature Schemes are gaining attention due to their believed quantum resistance. Their signing and verification times are comparable to those of algorithms in use today, but their key's generation time is much greater. To speed-up the execution time of key generation algorithms, this paper introduces and analises two parallel MIMD implementations of the hash based signature scheme XMSS (eXtended Merkle Signature Scheme).References
Bellare, M. (2002). A note on negligible functions. J. Cryptology, 15(4):271–284.
Bellare, M. and Rogaway, P. (1997). Collision-resistant hashing: Towards making uowhfs practical. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 470–484.
Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Wilcox-O'Hearn, Z. (2015). SPHINCS: practical stateless hash-based signatures. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 368–397.
Brassard, G., Høyer, P., and Tapp, A. (1998). Quantum cryptanalysis of hash and clawfree functions. In LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, pages 163–169.
Buchmann, J. A., Dahmen, E., and Hülsing, A. (2011). XMSS - A practical forward IACR Cryptology
secure signature scheme based on minimal security assumptions. ePrint Archive, 2011:484.
Butin, D. (2017). Hash-based signatures: State of play. IEEE Security & Privacy, 15(4):37–43.
Butin, D., Walde, J., and Buchmann, J. A. (2017). Post-quantum authentication in openssl with hash-based signatures. In Tenth International Conference on Mobile Computing and Ubiquitous Network, ICMU 2017, Toyama, Japan, October 3-5, 2017, pages 1–6.
Daniel, H. W. and Steele, Jr., G. L. (1986). Data parallel algorithms. Commun. ACM, 29(12):1170–1183.
de Oliveira, A. K. D. S. and López, J. (2015). An efcient software implementation of the hash-based signature scheme MSS and its variants. In Progress in Cryptology - LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings, pages 366–383.
de Oliveira, A. K. D. S., Lopez, J., and Cabral, R. (2017). High performance of hash- based signature schemes. International Journal of Advanced Computer Science and Applications, 8:421–432.
Dods, C., Smart, N. P., and Stam, M. (2005). Hash based digital signature schemes. In Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings, pages 96–115.
Gorbenko, Y. I., Melnik, T. V., and Gorbenko, I. D. (2018). Analysis of potential postquantum schemes of hash-based digital signatures. Telecommunications and Radio Engineering, 77:603–626.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219.
Hevia, A. and Micciancio, D. (2002). The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings, pages 379–396.
Hülsing, A. (2017). WOTS+ - shorter signatures for hash-based signature schemes. IACR Cryptology ePrint Archive, 2017:965.
Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. (2018). XMSS: extended merkle signature scheme. RFC, 8391:1–74.
Hülsing, A., Gazdag, S.-L., Butin, D., and Buchmann, J. (2015a). Hash-based signatures: In Workshop on Cybersecurity in a Post-Quantum An outline for a new standard. World, NIST.
Hülsing, A., Rausch, L., and Buchmann, J. A. (2017). Optimal parameters for XMSSM T . IACR Cryptology ePrint Archive, 2017:966.
Hülsing, A., Rijneveld, J., and Schwabe, P. (2015b). Armed SPHINCS - computing a 41kb signature in 16kb of RAM. IACR Cryptology ePrint Archive, 2015:1042.
Lamport, L. (1979). Constructing digital signatures from a one-way function. Technical report, SRI International Computer Science Laboratory.
Merkle, R. (1979). Secrecy, authentication and public key systems / A certied digital signature. PhD thesis, Dept. of Electrical Engineering, Stanford University.
Naor, M. and Yung, M. (1989). Universal one-way hash functions and their cryptographic applications. In Proceedings of the Twenty-rst Annual ACM Symposium on Theory of Computing, STOC '89, pages 33–43, New York, NY, USA. ACM.
NIST (2016). Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Announcement.
Pereira, G. C. C. F. (2015). Assinaturas Digitais Pós Quanticas Multivariadas e Baseadas em Hash. PhD thesis, Departamento de Engenharia de Computação e Sistemas Digitais, Escola Politécnica da Universidade de São Paulo.
Pereira, G. C. C. F., Puodzius, C., and Barreto, P. S. L. M. (2016). Shorter hash-based signatures. Journal of Systems and Software, 116:95–100.
Rompel, J. (1990). One-way functions are necessary and sufcient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387–394.
Stallings, W. (2014). Criptograa e Segurança de Redes - Princípios e Práticas (6. ed. Pearson Education.
Stevens, M., Bursztein, E., Karpman, P., Albertini, A., and Markov, Y. (2017). The rst collision for full SHA-1. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 570–596.
Wang, W., Jungk, B., Wí'alde, J., Deng, S., Gupta, N., Szefer, J., and Niederhagen, R. (2018). XMSS and embedded systems - XMSS hardware accelerators for RISC-V. IACR Cryptology ePrint Archive, 2018:1225.
Wang, X., Feng, D., Lai, X., and Yu, H. (2004). Collisions for hash functions md4, md5, HAVAL-128 and RIPEMD. IACR Cryptology ePrint Archive, 2004:199.
Yuval, G. (1979). How to swindle rabin. Cryptologia, 3(3):187–191.
Zheng, A. Y. C. L., Ferraz, L. T. D., and Jr., M. A. S. (2018). A clipping technique for shorter hash-based signatures. In Anais do XVIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 167–180.
Bellare, M. and Rogaway, P. (1997). Collision-resistant hashing: Towards making uowhfs practical. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 470–484.
Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Wilcox-O'Hearn, Z. (2015). SPHINCS: practical stateless hash-based signatures. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 368–397.
Brassard, G., Høyer, P., and Tapp, A. (1998). Quantum cryptanalysis of hash and clawfree functions. In LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, pages 163–169.
Buchmann, J. A., Dahmen, E., and Hülsing, A. (2011). XMSS - A practical forward IACR Cryptology
secure signature scheme based on minimal security assumptions. ePrint Archive, 2011:484.
Butin, D. (2017). Hash-based signatures: State of play. IEEE Security & Privacy, 15(4):37–43.
Butin, D., Walde, J., and Buchmann, J. A. (2017). Post-quantum authentication in openssl with hash-based signatures. In Tenth International Conference on Mobile Computing and Ubiquitous Network, ICMU 2017, Toyama, Japan, October 3-5, 2017, pages 1–6.
Daniel, H. W. and Steele, Jr., G. L. (1986). Data parallel algorithms. Commun. ACM, 29(12):1170–1183.
de Oliveira, A. K. D. S. and López, J. (2015). An efcient software implementation of the hash-based signature scheme MSS and its variants. In Progress in Cryptology - LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings, pages 366–383.
de Oliveira, A. K. D. S., Lopez, J., and Cabral, R. (2017). High performance of hash- based signature schemes. International Journal of Advanced Computer Science and Applications, 8:421–432.
Dods, C., Smart, N. P., and Stam, M. (2005). Hash based digital signature schemes. In Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings, pages 96–115.
Gorbenko, Y. I., Melnik, T. V., and Gorbenko, I. D. (2018). Analysis of potential postquantum schemes of hash-based digital signatures. Telecommunications and Radio Engineering, 77:603–626.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219.
Hevia, A. and Micciancio, D. (2002). The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings, pages 379–396.
Hülsing, A. (2017). WOTS+ - shorter signatures for hash-based signature schemes. IACR Cryptology ePrint Archive, 2017:965.
Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. (2018). XMSS: extended merkle signature scheme. RFC, 8391:1–74.
Hülsing, A., Gazdag, S.-L., Butin, D., and Buchmann, J. (2015a). Hash-based signatures: In Workshop on Cybersecurity in a Post-Quantum An outline for a new standard. World, NIST.
Hülsing, A., Rausch, L., and Buchmann, J. A. (2017). Optimal parameters for XMSSM T . IACR Cryptology ePrint Archive, 2017:966.
Hülsing, A., Rijneveld, J., and Schwabe, P. (2015b). Armed SPHINCS - computing a 41kb signature in 16kb of RAM. IACR Cryptology ePrint Archive, 2015:1042.
Lamport, L. (1979). Constructing digital signatures from a one-way function. Technical report, SRI International Computer Science Laboratory.
Merkle, R. (1979). Secrecy, authentication and public key systems / A certied digital signature. PhD thesis, Dept. of Electrical Engineering, Stanford University.
Naor, M. and Yung, M. (1989). Universal one-way hash functions and their cryptographic applications. In Proceedings of the Twenty-rst Annual ACM Symposium on Theory of Computing, STOC '89, pages 33–43, New York, NY, USA. ACM.
NIST (2016). Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Announcement.
Pereira, G. C. C. F. (2015). Assinaturas Digitais Pós Quanticas Multivariadas e Baseadas em Hash. PhD thesis, Departamento de Engenharia de Computação e Sistemas Digitais, Escola Politécnica da Universidade de São Paulo.
Pereira, G. C. C. F., Puodzius, C., and Barreto, P. S. L. M. (2016). Shorter hash-based signatures. Journal of Systems and Software, 116:95–100.
Rompel, J. (1990). One-way functions are necessary and sufcient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387–394.
Stallings, W. (2014). Criptograa e Segurança de Redes - Princípios e Práticas (6. ed. Pearson Education.
Stevens, M., Bursztein, E., Karpman, P., Albertini, A., and Markov, Y. (2017). The rst collision for full SHA-1. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 570–596.
Wang, W., Jungk, B., Wí'alde, J., Deng, S., Gupta, N., Szefer, J., and Niederhagen, R. (2018). XMSS and embedded systems - XMSS hardware accelerators for RISC-V. IACR Cryptology ePrint Archive, 2018:1225.
Wang, X., Feng, D., Lai, X., and Yu, H. (2004). Collisions for hash functions md4, md5, HAVAL-128 and RIPEMD. IACR Cryptology ePrint Archive, 2004:199.
Yuval, G. (1979). How to swindle rabin. Cryptologia, 3(3):187–191.
Zheng, A. Y. C. L., Ferraz, L. T. D., and Jr., M. A. S. (2018). A clipping technique for shorter hash-based signatures. In Anais do XVIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 167–180.
Published
2019-09-02
How to Cite
ARAÚJO, Thales; PANETTA, Jairo.
Implementação Paralela do Algoritmo de Geração de Chaves do Esquema de Assinatura Digital XMSS (eXtended Merkle Signature Scheme). In: BRAZILIAN SYMPOSIUM ON CYBERSECURITY (SBSEG), 19. , 2019, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 15-28.
DOI: https://doi.org/10.5753/sbseg.2019.13959.
