Delta-XMSS: Incremental State Optimization for Post-Quantum Hash-Based Signatures

• Antônio Augusto Tavares Ribeiro André Inteli https://orcid.org/0009-0007-5468-5964
• Routo Terada USP https://orcid.org/0000-0001-9242-2806
• Victor Takashi Hayashi USP https://orcid.org/0000-0001-6672-4296
• Bryan Kano Ferreira Inteli https://orcid.org/0009-0003-3343-661X

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

Resumo

EXtended Merkle Signature Scheme (XMSS) is a hash-based digital signature scheme whose security relies on its underlying hash function and is therefore unaffected by Shor’s algorithm. However, one of the challenges faced by XMSS is the size of its signatures: an authentication path is transmitted along each signature to reconstruct the Merkle tree and a Winternitz One-Time Signature Plus (WOTS+) signature. To solve this problem, approaches like Buchmann, Dahmen, Schneider (BDS) optimize the generation of the authentication path along the signatures of the WOTS+ leaf but they still transmit the entire path. For this, we propose a technique to reduce the authentication path by delta-encoding two consecutive paths and transmitting only the nodes that change between them. We show that our solution reduces the authentication path size from h′ · n to (ν(idx)+1) ·n bytes per signature, achieving reductions of up to 90% in the path, corresponding to up to 11.5% of the complete signature (21.6% for h′ = 20). Encoding and decoding overhead remain under 80 CPU cycles for the most frequent signing indices (ν ≤ 5), negligible relative to the XMSS signing operation itself (median of 5,711,700 cycles).

Palavras-chave: XMSS, Delta encoding, Authentication path, Post-quantum cryptography

Referências

Buchmann, J., Dahmen, E., and Hülsing, A. (2011). XMSS – a practical forward secure signature scheme based on minimal security assumptions. In Post-Quantum Cryptography (PQCrypto 2011), volume 7071 of Lecture Notes in Computer Science, pages 117–129. Springer. DOI: 10.1007/978-3-642-25405-5_8.

Buchmann, J., Dahmen, E., and Schneider, M. (2008). Merkle tree traversal revisited. In Post-Quantum Cryptography (PQCrypto 2008), volume 5299 of Lecture Notes in Computer Science, pages 63–78. Springer. DOI: 10.1007/978-3-540-88403-3_5.

Goldwasser, S., Micali, S., and Rivest, R. L. (1988). A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308. DOI: 10.1137/0217017.

Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. (2018). XMSS: eXtended Merkle Signature Scheme. RFC 8391, IETF. DOI: 10.17487/RFC8391.

Hülsing, A. and Rijneveld, J. (2018). XMSS reference implementation. Available: [link].

Hunt, J. W. and McIlroy, M. D. (1976). An algorithm for differential file comparison. Technical Report Computing Science Technical Report 41, Bell Laboratories.

Jindal, R., Kumar, N., and Patidar, S. (2022). IoT streamed data handling model using delta encoding. International Journal of Communication Systems, 35(13). DOI: 10.1002/dac.5243.

Jobst, M., Liu, C., Partzsch, J., Yan, Y., Kappel, D., Gonzalez, H. A., Ji, Y., Vogginger, B., and Mayr, C. (2020). Event-based neural network for ecg classification with delta encoding and early stopping. In 6th International Conference on Event-Based Control, Communication, and Signal Processing (EBCCSP), pages 1–4. IEEE. DOI: 10.1109/EBCCSP51266.2020.9291357.

Merkle, R. C. (1990). A certified digital signature. In Advances in Cryptology – CRYPTO 1989, volume 435, pages 218–238. Springer. DOI: 10.1007/0-387-34805-0_21.

National Institute of Standards and Technology (2020). Recommendation for stateful hash-based signature schemes. Technical Report SP 800-208, NIST. DOI: 10.6028/NIST.SP.800-208.

National Institute of Standards and Technology (2024). Stateless hash-based digital signature standard (SLH-DSA). Technical Report FIPS 205, NIST. DOI: 10.6028/NIST.FIPS.205.

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

Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 124–134. IEEE. DOI: 10.1109/SFCS.1994.365700.