Abstract
SPHINCS is a recently proposed stateless hash-based signature scheme and promising candidate for a post-quantum secure digital signature scheme. In this work we provide a comparison of the performance when instantiating SPHINCS with different cryptographic hash functions on both recent Intel and AMD platforms found in personal computers and the ARMv8-A platform which is prevalent in mobile phones.
In particular, we provide a broad comparison of the performance of cryptographic hash functions utilizing the cryptographic extensions and vector instruction set extensions available on modern microprocessors. This comes with several new implementations optimized towards the specific use case of hash-based signature schemes.
Further, we instantiate SPHINCS with these primitives and provide benchmarks for the costs of generating keys, signing messages and verifying signatures with SPHINCS on Intel Haswell, Intel Skylake, AMD Ryzen, ARM Cortex A57 and Cortex A72.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
To separate the domains of the two functions one could use a different IV or round constants.
- 2.
AVX2 is available since Intel Haswell, for older platforms the predecessor AVX can be used which supports 128-bit vectors.
- 3.
AVX-512 can already be found in Xeon Phi (Knights Landing) and Skylake-X processors.
- 4.
- 5.
see ARM Cortex A57 Software Optimization Guide, Page 35.
- 6.
- 7.
The main difference is that SPHINCS has a security proof in the standard model and Picnic in the quantum random-oracle model (QROM).
- 8.
- 9.
References
Amy, M., Matteo, O.D., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.: Estimating the cost of generic quantum pre-image attacks on sha-2 and sha-3. Cryptology ePrint Archive, Report 2016/992 (2016). http://eprint.iacr.org/2016/992
Aumasson, J.-P., Fischer, S., Khazaei, S., Meier, W., Rechberger, C.: New features of Latin dances: analysis of salsa, chacha, and rumba. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 470–488. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_30
Aumasson, J., Meier, W., Phan, R.C., Henzen, L.: The Hash Function BLAKE. Information Security and Cryptography. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44757-4
Bernstein, D.J.: Chacha, a variant of salsa20 (2008). http://cr.yp.to/papers.html#chacha
Bernstein, D.J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., Wilcox-O’Hearn, Z.: SPHINCS: practical stateless hash-based signatures. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 368–397. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_15
Bernstein, D.J., Lange, T.: eBACS: Ecrypt benchmarking of cryptographic systems. https://bench.cr.yp.to. Accessed 11 May 2017
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V., Keer, R.V.: Keccak code package. https://github.com/gvanas/KeccakCodePackage. Accessed 02 May 2017
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V., Keer, R.V.: Kangarootwelve: fast hashing based on keccak-p. Cryptology ePrint Archive, Report 2016/770 (2016). http://eprint.iacr.org/2016/770
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://doi.org/10.1007/978-3-642-25405-5_8
Chang, D., Kumar, A., Morawiecki, P., Sanadhya, S.K.: 1st and 2nd preimage attacks on 7, 8 and 9 rounds of keccak-224,256,384,512. In: SHA-3 Workshop, August 2014
Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D., Zaverucha, G.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, 30 October–03 November 2017, pp. 1825–1842. ACM (2017). https://doi.org/10.1145/3133956.3133997
Chen, M.-S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: From 5-Pass \(\cal{MQ}\)-based identification to \(\cal{MQ}\)-based signatures. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 135–165. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_5
Dahmen, E., Okeya, K., Takagi, T., Vuillaume, C.: Digital signatures out of second-preimage resistant hash functions. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 109–123. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88403-3_8
McGrew, D., Curcio, M., Fluhrer, S.: Hash-based signatures. https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/. Accessed 22 May 2017
Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: CRYSTALS - dilithium: Digital signatures from module lattices. IACR Cryptology ePrint Archive 2017, 633 (2017). http://eprint.iacr.org/2017/633
Espitau, T., Fouque, P.-A., Karpman, P.: Higher-order differential meet-in-the-middle preimage attacks on SHA-1 and BLAKE. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 683–701. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_33
Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: Falcon: fast-Fourier, lattice-based, compact signatures over NTRU. Submission to NIST Post-Quantum Competition (2017)
Goldreich, O.: The Foundations of Cryptography - Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 212–219 (1996)
Gueron, S., Mouha, N.: Simpira v2: a family of efficient permutations using the AES round function. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 95–125. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_4
Gueron, S., Mouha, N.: Sphincs-simpira: Fast stateless hash-based signatures with post-quantum security. Cryptology ePrint Archive, Report 2017/645 (2017). http://eprint.iacr.org/2017/645
Guo, J., Ling, S., Rechberger, C., Wang, H.: Advanced meet-in-the-middle preimage attacks: first results on full tiger, and improved results on MD4 and SHA-2. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 56–75. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_4
Guo, J., Liu, M., Song, L.: Linear structures: applications to cryptanalysis of round-reduced Keccak. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 249–274. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_9
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). https://doi.org/10.1007/978-3-642-38553-7_10
Hülsing, A., Rijneveld, J., Schwabe, P.: ARMed SPHINCS. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016. LNCS, vol. 9614, pp. 446–470. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_17
Jean, J.: Cryptanalysis of haraka. IACR Trans. Symmetric Cryptol. 2016(1), 1–12 (2016)
Jean, J., Nikolić, I.: Efficient design strategies based on the AES round function. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 334–353. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_17
Khovratovich, D., Rechberger, C., Savelieva, A.: Bicliques for Preimages: attacks on Skein-512 and the SHA-2 family. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 244–263. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34047-5_15
Kölbl, S., Lauridsen, M.M., Mendel, F., Rechberger, C.: Haraka v2 - efficient short-input hashing for post-quantum applications. IACR Trans. Symmetric Cryptol. 2016(2), 1–29 (2016)
Leurent, G.: MD4 is not one-way. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 412–428. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_26
Reyzin, L., Reyzin, N.: Better than BIBA: short one-time signatures with fast signing and verifying. In: Batten, L., Seberry, J. (eds.) ACISP 2002. LNCS, vol. 2384, pp. 144–153. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45450-0_11
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Ortiz, H. (ed.) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 387–394. ACM (1990)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Stephens, N., Biles, S., Boettcher, M., Eapen, J., Eyole, M., Gabrielli, G., Horsnell, M., Magklis, G., Martinez, A., Premillieu, N., et al.: The arm scalable vector extension. IEEE Micro 37(2), 26–39 (2017)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 1–18. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_1
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_2
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_2
Acknowledgments
We would like to thank Christoffer Brøndum for providing a first version of the ARM implementation of Haraka and Jacob Appelbaum for running the benchmarks on the Cortex A72.
This work was supported by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Instructions
A Instructions
In Table 3 we give an overview of the performance characteristicsFootnote 8\(^{,}\)Footnote 9 of the instructions on the different platforms. Note that on the ARM Cortex A57/A73 a pair of aese and aesmc will have a latency of 3 and inverse throughput of 1.
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Kölbl, S. (2018). Putting Wings on SPHINCS. In: Lange, T., Steinwandt, R. (eds) Post-Quantum Cryptography. PQCrypto 2018. Lecture Notes in Computer Science(), vol 10786. Springer, Cham. https://doi.org/10.1007/978-3-319-79063-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-79063-3_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-79062-6
Online ISBN: 978-3-319-79063-3
eBook Packages: Computer ScienceComputer Science (R0)