Rapidly Verifiable XMSS Signatures

Joppe W. Bos, Andreas Hülsing (Corresponding author), Joost Renes, Christine van Vredendaal

Research output: Contribution to journalArticleAcademicpeer-review

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, Custódio, and Martina (PZMCM) at ISCC 2018, that changes the XMSS signing algorithm to search for rapidly 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 compatible 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 well-known 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.
Original languageEnglish
Pages (from-to)137-168
Number of pages32
JournalIACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
Volume2021
Issue number1
Early online date3 Dec 2020
DOIs
Publication statusPublished - Jan 2021

Fingerprint Dive into the research topics of 'Rapidly Verifiable XMSS Signatures'. Together they form a unique fingerprint.

Cite this