A clipping technique for shorter hash-based signatures

• Amos Y. C. L. Zheng USP
• Leonardo T. D. Ferraz USP
• Marcos A. Simplicio Jr. USP

DOI: https://doi.org/10.5753/sbseg.2018.4251

Resumo

Hash-based signature schemes are a class of post-quantum algorithms that usually consist of hash-trees built upon One-Time Signature (OTS) solutions. These schemes have small key sizes, efficient processing and are simple to implement, while their security properties rely basically on the pre-image or collision resistance of the their underlying hash function. Despite such advantages, however, they have relatively large signature sizes compared to traditional signature algorithms. One way of tackling this issue is to reduce the sizes of their underlying OTS algorithms. In this article, we describe a probabilistic technique that, with negligible processing overhead, allows such reductions. Namely, up to 12.5% average size reduction can be achieved depending on the signature's parameters.

Referências

Anthony, S. (2017). IBM will sell 50-qubit universal quantum computer “in the next few years”. [link]. Accessed: 2017-09-28.

Bernstein, D. J., Buchmann, J., and Dahmen, E. (2008). Post-Quantum Cryptography. Springer, Heidelberg, Deutschland.

Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schwabe, P., and WilcoxO’Hearn, Z. SPHINCS: practical stateless hash-based signatures. LNCS.

Bernstein, D. J. and Lange, T. (2017). Post-quantum cryptography – dealing with the fallout of physics success. Cryptology ePrint Archive, Report 2017/314. [link].

Buchmann, J., Dahmen, E., and Hülsing, A. (2011). XMSS – A practical forward secure signature scheme based on minimal security assumptions. Post-Quantum Cryptography, 7071.

Buchmann, J., García, L. C. C., Dahmen, E., Döring, M., and Klintsevich, E. (2006). Cmss – an improved merkle signature scheme. In Progress in Cryptology - IN-DOCRYPT 2006, pages 349–363, Berlin, Heidelberg. Springer.

Ding, J. and Schmidt, D. (2005). Rainbow, a new multivariable polynomial signature scheme. Int. Conf. on Applied Cryptography and Network Security (ACNS’05), 3531 of LNCS:164–175.

Dods, C., Smart, N. P., and Stam, M. (2005). Hash based digital signature schemes. Cryptography and Coding, 3796 of LNCS:96–115.

Goldreich, O., Goldwasser, S., and Halevi, S. (1997). Public-key cryptosystems from lattice reduction problems. Advances in Cryptology – CRYPTO’97, 1294:112–131.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proc. of the 28th annual ACM symposium on Theory of computing, pages 212–219. ACM.

Hülsing, A. (2013). W-OTS+ – shorter signatures for hash-based signature schemes. In Progress in Cryptology – AFRICACRYPT 2013, pages 173–188, Berlin, Heidelberg. Springer.

Hülsing, A., Rausch, L., and Buchmann, J. (2013). Optimal parameters for xmss mt. In Security Engineering and Intelligence Informatics, pages 194–208, Berlin, Heidelberg. Springer.

Jao, D. and De Feo, L. (2011). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography, pages 19–34. Springer.

Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177):203–209.

Lamport, L. (1979). Constructing digital signatures from a one way function. Technical report, SRI International.

McEliece, R. J. (1978). A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 42:114–116.

Merkle, R. C. (1990). A certified digital signature. Advances in Cryptology — CRYPTO’89, pages 218–238.

Miller, V. S. (1986). Use of elliptic curves in cryptography. In Advances in Cryptology — CRYPTO ’85, pages 417–426, Berlin, Heidelberg. Springer.

NIST (2001). Federal Information Processing Standard (FIPS 197) – Advanced Encryption Standard (AES). National Institute of Standards and Technology.

NIST (2015). Federal Information Processing Standard (FIPS 202) – SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Standards and Technology. DOI: 10.6028/NIST.FIPS.202.

Perrig, A. (2001). The biba one-time signature and broadcast authentication protocol. In Proc. of the 8th Conf. on Computer and Communications Security, CCS ’01, pages 28–37, New York, NY, USA. ACM.

Reyzin, L. and Reyzin, N. (2002). Better than biba: Short one-time signatures with fast signing and verifying. In Information Security and Privacy, pages 144–153, Berlin, Heidelberg. Springer.

Rivest, R., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126.

Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev., 41(2):303–332.

Steinwandt, R. and Villányi, V. I. (2008). A one-time signature using run-length encoding. Information Processing Letters, 108(4):179–185.