Paper 2020/898

Rapidly Verifiable XMSS Signatures

Joppe W. Bos, Andreas Hülsing, Joost Renes, and Christine van Vredendaal


This work presents new speed records for XMSS (RFC 8391) signature verification on embedded devices. For this we make use of a probabilistic method recently proposed by Perin, Zambonin, Martins, Custodio, and Martina (PZMCM) at ISCC 2018, that changes the XMSS signing algorithm to search for fast verifiable signatures. We improve the method, ensuring that the added signing cost for the search is independent of the message length. We provide a statistical analysis of the resulting verification speed and support it by experiments. We present a record setting RFC compliant implementation of XMSS verification on the ARM Cortex-M4. At a signing time of about one minute on a general purpose CPU, we create signatures that are verified about $1.44$ times faster than traditionally generated signatures. Adding further implementation optimizations to the verification algorithm we reduce verification time by over a factor two from $13.85$ million to $6.56$ million cycles. In contrast to previous works, we provide a detailed security analysis of the resulting signature scheme under classical and quantum attacks that justifies our selection of parameters. On the way, we fill a gap in the security analysis of XMSS as described in RFC 8391 proving that the modified message hashing in the RFC does indeed mitigate multi-target attacks. This was not shown before and might be of independent interest.

Available format(s)
Publication info
Preprint. MINOR revision.
Post-quantum cryptographyXMSSRFC 8391embedded devicessignature generationverification trade-offexact securityoptimized implementation
Contact author(s)
authors-rapidxmss @ huelsing net
2020-07-16: received
Short URL
Creative Commons Attribution


      author = {Joppe W.  Bos and Andreas Hülsing and Joost Renes and Christine van Vredendaal},
      title = {Rapidly Verifiable XMSS Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/898},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.