Abstract
In this work, we describe an optimized software implementation of the Merkle digital signature scheme (MSS) and its variants GMSS, XMSS and \(\mathrm{XMSS}^\mathrm{MT}\) using the vector instruction set AVX2 on Intel’s Haswell processor. Our implementation uses the multi-buffer approach for speeding up key generation, signing and verification on these schemes. We selected a set of parameters to maintain a balance among security level, key sizes and signature size. We aligned these parameters with the ones used in the hash-based signature schemes LDWM and XMSS. We report the performance results of our implementation on a modern Intel Core i7 3.4 GHz. In particular, a signing operation in the XMSS scheme can be computed in 2,001,479 cycles (1,694 signatures per second) at the 128-bit security level (against quantum attacks) using the SHA2-256 hash function, a tree of height 60 and 6 layers. Our results indicate that the post-quantum hash-based signature scheme \(\mathrm{XMSS}^\mathrm{MT}\) offers high security and performance for several parameters on modern processors.
J. López—The second author was partially supported by FAPESP Projeto Temático under grant 2013/25.977-7 and research productivity scholarship from CNPq Brazil.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. theory 22, 44–654 (1976)
Bremen, L., Kluge, J., Ziefle, M., Modabber, A., Goloborodko, E., Hölzle, F.: “Two faces and a hand scan”- pre- and postoperative insights of patients undergoing an orthognathic surgery. In: Stephanidis, C. (ed.) HCI 2014, Part II. CCIS, vol. 435, pp. 389–394. Springer, Heidelberg (2014)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Bellare, M., Miner, S.K.: A forward-secure digital signature scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 431–448. Springer, Heidelberg (1999)
Reyzin, L., Reyzin, N.: Better than BiBa: short one-time signatures with fast signing and verifying. In: Batten, L.M., Seberry, J. (eds.) ACISP 2002. LNCS, vol. 2384, pp. 144–153. Springer, Heidelberg (2002)
Lamport, L.: Constructing Digital Signatures from a One Way Function Technical report SRI-CSL-98, SRI International Computer Science Laboratory (1979)
Buchmann, J., García, L.C.C., Dahmen, E., Döring, M., Klintsevich, E.: CMSS – an improved merkle signature scheme. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 349–363. Springer, Heidelberg (2006)
NIST.: Digital Signatures Algorithm (DSA). FIPS-186 (1994). http://www.itl.nist.gov/fipspubs/fip186.htm
eBACS: ECRYPT Benchmarking of Cryptographic Systems SUPERCOP 20140924 (2014). http://hyperelliptic.org/ebats/supercop-20140924.tar.bz2
Gosney, J.: The sse2/xop implementation of sha256 (2013). http://www.openwall.com/lists/john-dev/2013/04/10/6
Johnson, D., Menezes, A., Vanstone, S.: Elliptic curve digital signature algorithm ECDSA. Int. J. Inf. Secur. 1, 36–63 (2001)
Jakobsson, M., Leighton, T., Micali, S., Szydlo, M.: Fractal merkle tree representation and traversal. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 314–326. Springer, Heidelberg (2003)
McGrew, D., Curcio, M.: Hash-Based Signatures draft-mcgrew-hash-sigs-02. Crypto Forum Research Group, Internet Draft, Cisco Systems (2014)
Buchmann, J., Dahmen, E., Szydlo, M.: Hash-based digital signature schemes. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 35–92. Springer, Heidelberg (2008)
Szydlo, M.: Merkle tree traversal in log space and time. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 541–554. Springer, Heidelberg (2004)
Buchmann, J., Dahmen, E., Klintsevich, E., Okeya, K., Vuillaume, C.: Merkle signatures with virtually unlimited signature capacity. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 31–45. Springer, Heidelberg (2007)
Buchmann, J., Dahmen, E., Schneider, M.: Merkle tree traversal revisited. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 63–78. Springer, Heidelberg (2008)
Hülsing, A., Rausch, L., Buchmann, J.: Optimal parameters for XMSS\(^\text{ MT }\). In: Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds.) CD-ARES Workshops 2013. LNCS, vol. 8128, pp. 194–208. Springer, Heidelberg (2013)
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, pp. 124–134. IEEE Computer Society Press (1994)
Practical Forward Secure Signature using Minimal Security Assumptions. Ph.D. thesis. TU Darmstadt, Darmstadt, August 2013
NIST.: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. Computer Security Division - Information Technology Laboratory - NIST Special Publication 800–90A (2012). http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
Bernstein, D., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schwabe, P., O’Hearn, Z.: SPHINCS: practical stateless hash-based signatures. Cryptology ePrint Archive - Report 2014/795 (2014)
Merkle, R.C.: Secrecy, Authentication, and Public Key Systems. Stanford Ph.D. thesis (1979)
Buchmann, J., Dahmen, E., Hülsing, A.: XMSS - a practical forward secure signature scheme based on minimal security assumptions. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 117–129. Springer, Heidelberg (2011). https://huelsing.wordpress.com/publications/
Hülsing, A., Butin, D., Gazdag, S.: XMSS: Extended Hash-Based Signatures draft-xmss-00. Crypto Forum Research Group, Internet Draft (2015)
Hülsing, A.: W-OTS+ – shorter signatures for hash-based signature schemes. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 173–188. Springer, Heidelberg (2013)
Guilfor, J., Yap, K., Gopal, V.: Fast SHA-256 Implementations on Intel Architecture Processors. IA Architects Intel Corporation (2012). http://www.intel.com.br/content/dam/www/public/us/en/documents/white-papers/sha-256-implementations-paper.pdf
Intel to release first Skylake microprocessors in Q2 2015 (2014). http://www.kitguru.net/components/cpu/anton-shilov/intel-to-release-first-skylake-microprocessors-in-q2-2015-says-report
Acknowledgments
The authors would like to thank the anonymous referees for their valuable comments and suggestions to improve the quality of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
de Oliveira, A.K.D.S., López, J. (2015). An Efficient Software Implementation of the Hash-Based Signature Scheme MSS and Its Variants. In: Lauter, K., Rodríguez-Henríquez, F. (eds) Progress in Cryptology -- LATINCRYPT 2015. LATINCRYPT 2015. Lecture Notes in Computer Science(), vol 9230. Springer, Cham. https://doi.org/10.1007/978-3-319-22174-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-22174-8_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22173-1
Online ISBN: 978-3-319-22174-8
eBook Packages: Computer ScienceComputer Science (R0)