Paper 2020/898

Rapidly Verifiable XMSS Signatures

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Post-quantum cryptographyXMSSRFC 8391embedded devicessignature generationverification trade-offexact securityoptimized implementation
Contact author(s)
authors-rapidxmss @ huelsing net
History
2020-07-16: received
Short URL
https://ia.cr/2020/898
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/898,
      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{https://eprint.iacr.org/2020/898}},
      url = {https://eprint.iacr.org/2020/898}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.