Avaliação dos requisitos de tempo e espaço de assinaturas digitais stateful baseadas em funções hash para blockchains

• José Augusto A. G. de M. Braga UNICAMP
• Marco A. A. Henriques UNICAMP

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

Abstract

Blockchains have their security based, among other factors, on digital signatures. This security is threatened by the emergence of a large quantum computer capable of breaking current asymmetric encryption algorithms. One solution to this problem is to use digital signature schemes based on hash functions, since they are robust to attacks from a quantum computer. This work evaluated execution time and space requirements of four signature algorithms (XMSS, LMS, XMSS MT, HSS) with two versions each (normal and FAST) in several configurations and we concluded that LMS and HSS, both using the FAST version, are the most suitable for use in blockchains due to signature sizes and verification time.

References

Arute, F., Arya, K., Babbush, R. et al. (2019) “Quantum supremacy using a programmable superconducting processor". Nature 574, 505–510

Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Z. Wilcox-O'Hearn, (2015), "SPHINCS: Practical Stateless Hash-Based Signatures", Lecture Notes in Computer Science, Volume 9056, Advances in Cryptology - EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15.

Bernstein, D., Lange, T., (2017), “Post-quantum cryptography”. Nature 549, 188–194

Chen, L., Chen, L., Jordan, S., Liu, Y. K., Moody, D., Peralta, R., ... & Smith-Tone, D. (2016). Report on post-quantum cryptography (Vol. 12). US Department of Commerce, National Institute of Standards and Technology.

Johnson, Don & Menezes, Alfred & Vanstone, Scott. (2001). The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Sec.. 1. 36-63. 10.1007/s102070100002.

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21 (2), 120-126.

Shor, P. W., (1994) "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 124-134.

Huelsing, A., Rausch, L., and J. Buchmann, (2013) "Optimal Parameters for XMSS^MT", Lecture Notes in Computer Science, Volume 8128, CD-ARES, DOI 10.1007/978-3-642-40588-4_14.

Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, (2018), "XMSS: eXtended Merkle Signature Scheme", RFC 8391

Hülsing, Andreas, (2013),"W-OTS+–shorter signatures for hash-based signature schemes. "International Conference on Cryptology in Africa. Springer, Berlin, Heidelberg

Hülsing, Andreas, et al. (2015), "XMSS: Extended hash-based signatures." Crypto Forum Research Group Internet-Draft.(2015). Draft-irtf-cfrg-xmss-hash-based-signatures-01 Lamport, Leslie. (1979) Constructing digital signatures from a one-way function. Vol. 238. Technical Report CSL-98, SRI International

Leighton, F., Micali, S. (1995): “Large probably fast and secure digital signature schemes based on secure hash functions”, https://www.google.com/patents/US5432852, US Patent 5,432,852

McGrew, D., Curcio, M., and S. Fluhrer, (2019), "Leighton-Micali Hash-Based Signatures", RFC 8554 Ralph Charles Merkle. 1979. Secrecy, authentication, and public key systems. Ph.D. Dissertation. Stanford University, Stanford, CA, USA. Order Number: AAI8001972.

Merkle, R. C., (1989) “A certified digital signature,” in Proceedings on Advances in Cryptology, ser. CRYPTO ’89. Springer-Verlag New York, Inc., Nakamoto, Satoshi, (2008), "Bitcoin: A peer-to-peer electronic cash system.".

National Institute of Standards and Technology (2015-1), "Secure Hash Standard (SHS)", FIPS PUB 180-4,DOI 10.6028/NIST.FIPS.180-4.

National Institute of Standards and Technology, (2015-2) "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, 2015.

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21 (2), 120-126.

Wood, G. (2014). Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151 (2014), 1-32.