Cryptography Reference
In-Depth Information
XMSS - A Practical Forward Secure Signature
Scheme Based on Minimal Security Assumptions
Johannes Buchmann, Erik Dahmen, and Andreas Hulsing
Cryptography and Computeralgebra
Department of Computer Science
TU Darmstadt
{
buchmann,dahmen,huelsing
}
@cdc.informatik.tu-darmstadt.de
Abstract.
We present the hash-based signature scheme XMSS. It is
the first provably (forward) secure and practical signature scheme with
minimal security requirements: a pseudorandom and a second preimage
resistant (hash) function family. Its signature size is reduced to less than
25% compared to the best provably secure hash based signature scheme.
Keywords:
digital signature, practical, minimal security assumptions,
hash-based signatures, forward security, provable security.
1
Introduction
Digital signatures are a very important cryptographic tool. The signature schemes
currently used in practice are RSA, DSA, and ECDSA. Their security depends
on the security of certain trapdoor one-way functions which, in turn, relies on the
hardness of factoring integers and computing discrete logarithms, respectively.
However, it is unclear whether those computational problems remain hard in the
future. In fact, it has been shown by Shor [28] that quantum computers can solve
them in polynomial time. Other algorithmic breakthroughs are always possible in
the future. In view of the importance of digital signatures it is necessary to come
up with alternative practical signature schemes that deliver maximum security.
In particular, quantum computers must not be able to break them. They are
called post-quantum signature schemes.
In this paper we propose the hash-based signature scheme XMSS (eXtended
Merkle Signature Scheme). It is based on the Merkle Signature Scheme [24] and
the Generalized Merkle Signature Scheme (GMSS) [10]. We show that XMSS is
an ecient post-quantum signature scheme with minimal security assumptions.
This is done as follows. XMSS requires a hash function family
H
and another
function family
F
.Weprove:
(Security)
XMSS is existentially unforgeable under adaptively chosen mes-
sage attacks in the standard model, provided
H
is second preimage resistant
and
F
is pseudorandom.
Supported by grant no. BU 630/19-1 of the German Research Foundation
(
www.dfg.de
).
