Cryptography Reference
In-Depth Information
(E
ciency)
XMSS is ecient, provided that
H
and
F
are ecient. This
claim is supported by experimental results.
The first assertion shows that the security requirements for XMSS are minimal.
This follows from [27], [26], [19] and [17] where the existence of a secure signature
scheme is proved to imply the existence of a second preimage resistant hash
function family and a pseudorandom function family (see Section 3).
The second assertion shows that XMSS is practical as there are many ways to
construct very ecient (hash) function families that are believed to be second
preimage resistant or pseudorandom, respectively, even in the presence of quan-
tum computers. For example, cryptographic hash functions and block ciphers
can be used to construct such families. In particular, there are such construc-
tions based on hard problems in algebra or coding theory. The huge number
of instantiations of XMSS guarantees the long-term availability of secure and
ecient signature schemes.
The idea of hash-based signatures was introduced by Merkle [24]. The results
in [8,9,10,11,12,13,14,15,16,20,21,29] improve the Merkle idea in many respects
by providing new algorithmic ideas and security proofs. XMSS incorporates
many of those ideas and goes one step further. It is the first practical (for-
ward) secure signature scheme with minimal security requirements in the above
sense. All other constructions, but MSS-SPR [14], require a collision resistant
hash function family whose existence is not known to follow from the existence of
a secure digital signature scheme. Compared to MSS-SPR, which is the currently
best hash-based signature scheme that carries a proof of security, we can reduce
the signature size by more than 25 % for the same level of security. Furthermore
MSS-SPR is not forward-secure. The improved signatur size is very important
as the signature size is considered the main drawback of hash-based signatures.
In this paper we show only how to sign fixed length messages. The scheme
can easily be extended to sign messages of arbitrary length using TCR hash and
sign as proposed in [14]. This requires a target collision resistant hash function
family. Target collision resistant hash function families are known to exist if
any one-way function exists [27]. Therefore this preserves the minimal security
assumptions property.
The paper is organized as follows. In Section 2 we describe the construction
of XMSS. Its security and forward security is discussed in Sections 3 and 4. The
XMSS-eciency is shown in Section 5. Section 6 contains a description of our
implementation and a presentation of the performance results.
2
The eXtended Merkle Signature Scheme XMSS
In this section we describe XMSS. Like the Merkle signature scheme [24] it uses
a one-time signature scheme (OTS) that can only sign one message with one
key. To overcome the limitation to one message per key, a hash tree is used to
reduce the authenticity of many OTS verification keys to one public XMSS key.
To minimize storage requirements, pseudorandom generators (PRG) are used.
They generate the OTS signature keys as needed.
