Delta-XMSS: Incremental State Optimization for Post-Quantum Hash-Based Signatures - André, Antônio Augusto Tavares Ribeiro; Terada, Routo; Hayashi, Victor Takashi; Ferreira, Bryan Kano (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg); 2026: Anais do XXVI Simpósio Brasileiro de Cibersegurança, 2026)
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).