Merkle Signatures with Virtually Unlimited Signature Capacity Johannes Buchmann1 , Erik Dahmen1 , Elena Klintsevich1 , Katsuyuki Okeya2, and Camille Vuillaume2 1 Technische Universität Darmstadt Department of Computer Science Hochschulstraße 10, 64289 Darmstadt, Germany {buchmann,dahmen,klintsev}@cdc.informatik.tu-darmstadt.de 2 Hitachi, Ltd., Systems Development Laboratory, 1099, Ohzenji, Asao-ku, Kawasaki-shi, Kanagawa-ken, 215-0013, Japan {katsuyuki.okeya.ue,camille.vuillaume.ch}@hitachi.com Abstract. We propose GMSS, a new variant of the Merkle signature scheme. GMSS is the first Merkle-type signature scheme that allows a cryptographically unlimited (280 ) number of documents to be signed with one key pair. Compared to recent improvements of the Merkle signature scheme, GMSS reduces the signature size as well as the signature generation cost. Keywords: Merkle signatures, post-quantum cryptography, SSL. 1 Introduction Digital signatures are one of the most important applications of public key cryptography. For example, they are an essential part of the SSL/TLS protocol for authenticating websites. If large scale quantum computers are built, all popular digital signature schemes like RSA, DSA and ECDSA will become insecure [12]. In addition, significant progresses have been made for solving the underlying number theoretic problems for RSA or DSA, and therefore, the key lengths required to provide sufficient security have been steadily increasing [10]. As a consequence, it is urgent to look for alternative signature schemes, thoroughly analyze and understand their security, and see how they behave in real-life applications. A promising alternative to common digital signature schemes is the Merkle signature scheme (MSS) proposed by Merkle in [11]. The security of MSS solely relies on the existence of cryptographic hash functions. According to [7], the required properties of the hash function are one-wayness and collision resistance. Using MSS, it is possible to remove the requirement for number theoretic assumptions from digital signatures. In recent years, many improvements to the original MSS were proposed. The inefficient key generation and the resulting limited signature capacity of MSS is addressed in [3]. The authors proposed CMSS, a variant of MSS that increases the signature capacity from 220 to 240 and provides competitive timings compared to common signature schemes. Other important contributions are efficient tree traversal algorithms [8, 13, 14], which play a crucial role for fast signature generation. First of all, it is unclear whether a signature capacity of 240 is sufficient for practical applications. Consider for example webservers using SSL/TLS or electronic archives. Second, the original MSS as well as CMSS suffer from quite large signature sizes. Further, there may be time and space requirements in specific application environments, such as smart cards, that are not satisfied by current constructions. In this paper we present the generalized Merkle signature scheme (GMSS). GMSS is a highly flexible variant of CMSS that can be adjusted to the requirements and constraints of a particular environment. GMSS drastically reduces the signing time by distributing the costs for one signature generation across several previous signatures and the key generation. This in turn makes it possible to choose parameters that provide smaller signatures. Using GMSS, it is possible to achieve a signature capacity of 280 with competitive timings and reasonable signature sizes, i.e. 26.1 ms for signing, 18.1 ms for verifying, and 3,620 bytes for the signature. In case of a signature capacity of 240 it is possible to achieve 26 ms for signing, 19.6 ms for verifying, and only 1,860 bytes for the signature. For both signature capacities, it is also possible to achieve signing and verification times of only 10 ms at the expense of larger signatures, i.e. 2,340 bytes for 2 40 and 4,240 bytes for 280 . We also propose a client-server protocol for webservers using SSL/TLS that minimizes the latency and improves resistance to denial of service attacks. This paper is organized as follows: Section 2 introduces GMSS. Section 3 shows how to choose appropriate parameters and how to exchange signatures in the SSL/TLS protocol. Finally, Section 4 states our conclusion. 2 GMSS in Theory This section at first shows the general construction of GMSS. Then the key generation, signature generation and verification are explained in detail and the costs and memory requirements are estimated. 2.1 General Construction The basic construction of GMSS consists of a tree with T layers. The nodes of this tree are in turn Merkle trees [11]. A brief description of Merkle trees can be found in Appendix A. The height of all Merkle trees in a certain layer i is denoted by hi . Trees in different layers may have different heights. Each Merkle tree in layer i = 1, . . . , T − 1 is parent to 2hi Merkle trees. T1,0 denotes the single Merkle tree in layer 1. The 2h1 +...+hi−1 Merkle trees in layers i = 2, . . . , T are denoted by Ti,j , j = 0, . . . , 2h1 +...+hi−1 − 1 according to their position from left to right. Parents and children Merkle trees have the following relationship: the root of a child tree is signed with the one-time signature key corresponding to a certain leaf of his parent tree. In the following, when talking about leaves in the context of signing, we mean the corresponding one-time signature key. RootT denotes the root of tree T . SigT denotes the one-time signature of RootT , which is generated using leaf l of T ’s parent. Message digests d are signed using the leaves of the Merkle trees on the deepest layer T and we call their one-time signature Sigd . Thanks to the layer hierarchy, the number of message digests that can be signed using one GMSS key pair is S = 2h1 +...+hT . The general construction of GMSS is depicted in Figure 1. T1,0 PSfrag replacements SigT RootT T2,1 T2,0 ... T TT,0 TT,1 ... ... l Fig. 1. General construction of GMSS For any given signature s ∈ {0, . . . , 2h1 +...+hT − 1}, there is a unique path p from the Merkle tree on the lowest layer T , which is used to sign the digest, to the single Merkle tree on the top layer 1 (T1,0 ). This path involves one Merkle tree at each layer i = 1, . . . , T . A GMSS signature of a message digest d contains the one-time signature Sigd of d and the one-time signatures SigT of the roots of all Merkle trees on path p, except for T1,0 . For all trees T on path p, a GMSS signature also contains the authentication path AuthT ,l of the leaf l that is used to sign either the child of T , or the digest d. An authentication path is defined as the sequence of the siblings of all nodes on the path from leaf l to the root of T . GMSS uses the Winternitz one-time signature scheme [4, 11] for signing digests d and RootT (see Appendix B for for a brief introduction to the Winternitz one-time signature scheme). wi denotes the Winternitz parameter used in layer i = 1, . . . , T . Different layers are allowed to use different Winternitz parameters. GMSS is specified by a GMSS parameter set  P = T, (h1 , . . . , hT ), (w1 , . . . , wT ) . Remark 1. The Merkle variant CMSS proposed in [3] is a special case of GMSS. CMSS uses only two layers, where both layers use the same Winternitz parameter  and all trees in both layers have the same height, i.e. P = 2, (h, h), (w, w) . During the key generation, GMSS computes SigT and AuthT ,l for the Merkle trees on the path p used by the first signature (Section 2.3). SigT and AuthT ,l required by succeeding signatures are precomputed (Section 2.4). Since those values change less frequently for upper layers, the precomputation can be distributed over many steps. On the one hand, this results in a significant improvement of the signing speed. On the other hand, this enables us to choose large Winternitz parameters wi , which results in smaller signatures. In Section 3.1, we formulate this trade-off as an optimization problem to find an optimal parameter set. 2.2 Winternitz One-Time Signature Key Generation First of all, we describe our strategy for generating random data required by onetime signature keys. Let H : {0, 1}∗ → {0, 1}n be a cryptographic hash function with output length n bits. We adopt the approach for the generation of the Winternitz OTS signature keys proposed in [3] and use a pseudo random number generator (PRNG) f : {0, 1}n → {0, 1}n × {0, 1}n , Seedin 7→ (Seedout , Rand) for generating secrets. In the following, we call cHash the cost evaluating one hash (in our case, the input size is small and fixed) and cPrng the cost for calling the PRNG. To assure interoperability we selected the PRNG described in [6], Appendix 3.1, which requires one single call to the hash function H. Rand ← H(Seedin ), Seedout ← (1 + Seedin + Rand) mod 2n We use an initial seed SeedTi,j ,l to generate the seed for the lth Winternitz OTS signature key of Merkle tree Ti,j , i.e. (SeedTi,j ,l+1 , SeedOTS ) ← f (SeedTi,j ,l ) (SeedOTS , xk ) ← f (SeedOTS ), k = 1, . . . , twi and twi = dn/wi e + d(blog2 (dn/wi e)c + 1 + wi ) /wi e. The lth one-time signature key and the lth leaf of Merkle tree Ti,j are given as X = (x1 , . . . , xtwi )  wi wi and Y = H H 2 −1 (x1 )k . . . kH 2 −1 (xtw ) , respectively. Note that Y is also the Winternitz one-time verification key that corresponds to X. H k (x) denotes the hash function applied k times and k the concatenation of two strings. The updated seed SeedTi,j ,l+1 is stored and used to generate the (l + 1)th signature key. If the current signature key is associated with the last leaf of tree Ti,j , i.e. l = 2hi − 1, the updated seed is used as initial seed for the next Merkle tree Ti,j+1 , i.e. (SeedTi,j+1 ,0 , SeedOTS ) ← f (SeedTi,j ,2hi −1 ). 2.3 GMSS Key Generation Next, we explain how to generate a GMSS keypair, establish the size of the public and private keys and the cost for computing them. From the parameter set P and initial seeds SeedT1,0 ,0 , . . . , SeedTT,0 ,0 , the key generation step computes the GMSS public key RootT1,0 and the GMSS private key which consists of the following entries.  SeedTi,2 ,0 , i = 2, . . . , T  SeedTi,0 ,0 , i = 1, . . . , T , SigTi,0 , i = 2, . . . , T , RootTi,1 , i = 2, . . . , T  AuthTi,0 ,0 , i = 1, . . . , T , AuthTi,1 ,0 , i = 2, . . . , T At first, the key generation computes the root of the first tree in each layer RootTi,0 , i = 1, . . . , T . This can be done efficiently using a classical algorithm also referred to as treehash [13], shown in Algorithm 1. This algorithm uses a stack S of nodes, where each node knows its height in the tree. In this paper, we use a slightly modified version of treehash, which allows us to easily distribute costs by incrementally computing the root. In Algorithm 1, the leaf l is the lth verification key, computed using SeedTi,j ,l as described above. For a tree of height hi , Algorithm 1 must be called 2hi times, where the 2hi leaves are supplied in sequential order, from left to right. For each call of Algorithm 1, the inner while loop might compute from 0 to hi iterations, but in total, the 2hi calls will result in exactly 2hi − 1 iterations. After the 2hi calls, the stack S contains a single node, the root of the tree. Note that during the computation of the root RootTi,0 , the authentication path for the 0th leaf of tree Ti,0 , i.e. AuthTi,0 ,0 is generated for free, since all nodes of the tree are parsed by the algorithm. Algorithm 1 Treehash Input: Leaf l, stack S Output: updated stack S 1. push l to S 2. while top two nodes of S have the same height do 2.1. pop n1 from S; pop n2 from S 2.2. push H(n2 ||n1 ) to S 3. return S Next, the roots RootTi,1 and authentication paths AuthTi,1 ,0 of of the succeeding trees Ti,1 , i = 2, . . . , T are computed with Algorithm 1. As explained above, the initial seeds SeedTi,1 ,0 related to the trees Ti,1 are now available. Finally, after generating the second tree in each layer, the seeds SeedTi,2 ,0 are available, which are stored as part of the private key to allow an efficient generation of trees Ti,2 during the signing process. Note that SigTi,0 , i = 2, . . . , T does not have to be computed explicitly. It is an intermediate value during the computation of the 0th leaf of tree Ti−1,0 , i = 2, . . . , T . Lemma 1 (Key Generation). The total cost for the key generation is ckeygen = T P i=1 ctree (i) + T P i=2 ctree (i) (1)  where ctree (i) = 2hi (twi (2wi −1)+1) + 2hi −1 cHash + 2hi (twi +1) cPrng . The memory requirements for the keys are mpubkey = n   bits T T P P (hi + twi−1 + 2) n bits. (hi + 1) + mprivkey = (2) i=2 i=1 Proof. A tree on layer i requires the computation of 2hi leaves. Each leaf computation requires (2wi −1)·twi +1 hash function evaluations and twi +1 calls to the PRNG: one PRNG to obtain the seed and twi to obtain the signature key. The 2hi applications of treehash require 2hi −1cHash. Therefore, the total cost  for one tree on layer i is given as ctree (i) = 2hi ((2wi − 1) · twi + 1) + 2hi − 1 cHash + 2hi (twi + 1) cPrng . Since we construct two trees on layers i = 2, . . . T and one on layer i = 1, the total cost for the key generation is given by Equation (1). The memory requirements of the keys depend on the output size of the hash function n. A root RootTi,j is a single hash value and requires n bits, which explains mpubkey = n bits. A seed SeedTi,j ,l requires n bits. A one-time signature SigTi,j requires n · twi−1 bits. An authentication path requires hi · n bits. For each layer i = 2, . . . , T , we store two seeds, two authentication paths, one root and one one-time signature. For layer i = 1, we store one seed and one authentication path. Hence, the size of the pivate key is mprivkey as in Equation (2). 2.4 Signature Generation In the following, we discuss the signature generation stage. We introduce the components of a GMSS signature and estimate formulas for the signature size and costs. We also explain how the signature generation costs are distributed. For the sth GMSS signature (s ∈ {0, . . . , 2h1 +...+hT − 1}), let  jT = bs/2hT c, lT = s mod 2hT ji = bji+1 /2hi c, li = ji+1 mod 2hi , i = 1, . . . , T − 1. The path from the lowest tree TT,jT to the top tree T1,0 used by the sth signature is given as (TT,jT , TT −1,jT −1 , . . . , T2,j2 , T1,0 ). The one-time signature Sigd of the message digest d is generated using the lT th leaf of tree TT,jT . The one-time signature SigTi,ji of the root of tree Ti,ji is generated using the li−1 th leaf of tree Ti−1,ji−1 , i = 2, . . . , T . The sth GMSS signature consists of 1. 2. 3. 4. The The The The index s one-time signature Sigd one-time signatures SigTi,ji , i = 2, . . . , T authentication paths AuthTi,ji ,li , i = 1, . . . , T Lemma 2 (Signature Size). The size of a signature is msignature = T P i=1 (hi + twi ) · n bits. (3) Proof. A signature consists of T authentication paths (hi · n bits) and T onetime signatures (twi · n bits), one for each layer i = 1, . . . , T . Adding up yields msignature as shown by Equation (3) as the size of a signature. Following the framework of [5], we split the signature generation into two parts. The first part is the online part which computes Sig d and outputs the signature. The second part is the offline part that precomputes the authentication paths and one-time signatures of the roots required for upcoming signatures. In fact, the offline part performs an update of the private key and GMSS is therefore a key-evolving signature scheme [2]. Note that for the first signature s = 0 the offline part was done during the key generation. Lemma 3 (Online Signature Cost). The average cost for the online signing part is conline = (2wT − 1)twT /2 · cHash + (twT + 1)cPrng . (4) Proof. The generation of the one-time signature key requires one call to the PRNG to obtain the seed and twT are necessary to obtain the secrets. The wT average  signing costs of the Winternitz one-time signature scheme are (2 − 1)twT /2 · cHash . This leads to Equation (4). Next, we explain how to efficiently compute the offline signature part by distributing its cost. Our idea is based on the observation that trees in upper layers do not change frequently from one signature to the other. In the following, the values li , ji correspond to the current signature s. We begin with the precomputation of SigTi,ji +1 , i = 2, . . . , T , which must be ready when the next signature uses tree Ti,ji +1 . SigTi,ji +1 is generated using the one-time signature key that corresponds to either the (li−1 + 1)th leaf of tree Ti−1,ji−1 or the 0th leaf of tree Ti−1,ji−1 +1 . The latter case appears if (li−1 +1) = 0 mod 2hi−1 , i.e. we have to use the next tree in the next upper layer i − 1. For now we assume that RootTi,ji +1 is known when tree Ti,ji is used for the first time, i.e. li = 0. This certainly holds if ji = 0, since RootTi,1 was computed during the key generation. We distribute the computation of SigTi,ji +1 over the 2hi leaves (or steps) of tree Ti,ji . If li = 0 we use RootTi,ji +1 and perform the initialization steps of the Winternitz one-time signature scheme. Then we compute SigTi,ji +1 step-by-step each time we advance one leaf in tree Ti,ji . The generation of SigTi,ji +1 is completed if li = 2hi − 1. Lemma 4. On average, we require l (2wi−1 −1)t m lt m wi−1 wi−1 +1 csig (i) = cHash + cPrng 2hi +1 2 hi (5) operations each time we advance one leaf in Ti,ji to compute SigTi,ji +1 . Proof. The one-time signature SigTi,ji +1 is generated using the Winternitz parameter of layer i − 1 (wi−1 ), and on average requires (2wi−1 − 1)twi−1 /2 hash evaluations and twi−1 + 1 calls to the PRNG, see Lemma 3. Since there are 2hi leaves in the tree on layer i, the computation of SigTi,ji +1 can be distributed over 2hi steps which yields Equation (5) as costs per step. SigTi,j RootTi,j SigTi,j Ti−1,ji−1 i i +1 RootTi,j i i +1 li−1 +1 li−1 PSfrag replacements Ti,ji Ti,ji +1 Fig. 2. SigTi,ji +1 is precomputed from RootTi,ji +1 while using tree Ti,ji Above, we assumed that RootTi,ji +1 is known when we first use tree Ti,ji . Hence we must precompute RootTi,ji +2 while using tree Ti,ji , such that it is l0 switch to tree T ready when we i,ji +1 and want to start generating SigTi,ji +2 . l2hi −1 This is done by successively computing the leaves of tree Ti,ji +2 and passing them to Algorithm 1. While using the li th leaf of Ti,ji we compute the li th leaf of Ti,ji +2 . Its computation is distributed over the 2hi+1 leaves (or steps) of Ti+1,ji+1 , the current tree on the next lower layer i + 1. Once the leaf is generated, it is passed to treehash which partially constructs RootTi,ji +2 . Since treehash must be called 2hi times to construct the root of a tree of height hi , the construction of RootTi,ji +2 is completed once we switch from tree Ti,ji to tree Ti,ji +1 . Note that SeedTi,ji +2 ,0 , the seed required to compute the 0th leaf Ti,ji +2 was obtained during the generation of RootTi,ji +1 and is part of the private key. If ji = 0 the seed was computed during the key generation. For the lowest layer i = T the computation of the leaves has to be done at once. We also store AuthTi,ji +2 ,0 during the preparation of RootTi,ji +2 . RootTi,j RootTi,j i RootTi+1,j i +2 Ti,ji +2 Ti,ji i+1 li SigTi+1,j i+1 Ti+1,ji+1 Fig. 3. Leaf li of tree Ti,ji +2 is precomputed while using tree Ti+1,ji+1 PSfrag replacements Lemma 5. We require ( l wi m l m (2 −1)twi +1 t +1 c1leaf (i) = cHash + 2whii+1 cPrng 2hi+1 c2leaf (i) = hi · cHash (at most) (6) operations each time we advance one leaf in Ti+1,ji+1 and Ti,ji , respectively, to compute RootTi,ji +2 . Proof. The generation of the li th leaf of tree Ti,ji +2 requires ((2wi −1)twi +1)cHash and (twi + 1)cPrng . Since there are 2hi+1 leaves in the tree on layer i + 1, the computation of the li th leaf can be distributed over 2hi+1 steps which yields c1leaf (i). The while-loop of treehash requires at most hi hash function evaluations which yields c2leaf (i). Next, we describe the precomputation of AuthTi,ji ,li +1 , the authentication path of the next leaf of tree Ti,ji . We use an algorithm proposed by Szydlo in [13]. This algorithm uses hi − 1 instances of treehash to compute the upcoming authentication nodes. Given a leaf index li , Szydlo’s algorithm firstly checks if a new instance of treehash must be generated. Then it spends at most hi computational units, which are either hash function evaluations for the whileloop of treehash or leaf calculations. Again, the computation of the required leaves is distributed over the 2hi+1 leaves of Ti+1,ji+1 . When using the leaf li+1 = 0 of tree Ti+1,ji+1 , we perform the initialization steps of Szyldo’s algorithm and decide (1) if a new instance of treehash must be generated and (2) how many new leaves are required by the active treehash instances. Those leaves are computed step-by-step as explained above. If li+1 = 2hi+1 −1 the calculation of the required leaves is completed and we pass them to Szydlo’s algorithm which updates the treehash instances and outputs AuthTi,ji ,li +1 . Note that AuthTi,ji ,0 is stored during the construction of RootTi,ji and therefore already available if li = 0. Also, AuthTT,jT ,lT +1 must be computed at once. RootTi,j RootTi+1,j i Ti,ji i+1 li SigTi+1,j li +1 i+1 Ti+1,ji+1 Fig. 4. Leaves required for AuthTi,ji ,li +1 are precomputed while using tree Ti+1,ji+1 PSfrag replacements Lemma 6. We require at most ( l h −2 m i c1auth (i) = hi · c1leaf (i) + 22hi+1 cPrng c2auth (i) = hi · cHash (7) operations each time we advance one leaf in Ti+1,ji+1 and Ti,ji , respectively, to compute AuthTi,ji ,li +1 . Proof. Szydlo’s algorithm initializes at most one instance of treehash in each iteration. We need at most 2hi −2 calls to the PRNG to obtain the initial seed for the leaf required by this instance from the current seed. In the worst case, the active treehash instances require the computation of hi leaves. The computation of those hi leaves and the 2hi −2 calls to the PRNG are distributed over the 2hi+1 steps in the tree on layer i + 1. This yields c1auth (i). At most hi − 1 hash evaluations are spend on the while-loops of the active treehash instances. One hash evaluation is required by the initialization steps of Szydlo’s algorithm. This yields c2auth (i). The following lemma considers the worst case costs of the offline part. It assumes that for the next signature, we have to advance one leaf in each tree Ti,ji , i = 1, . . . , T − 1. Note that this is equivalent to advancing from tree Ti,ji to Ti,ji +1 in all layers i = 2, . . . , T . Lemma 7 (Offline Signature Cost and Memory). The worst case costs and the memory for the offline part are moffline T P T  P  csig (i)+c1leaf(i)+c2leaf(i) + c1auth (i)+c2auth (i) i=2 i=1   T P = (twi−1 + 4hi ) + 3h1 · n bits. coffline = (8) i=2 Proof. In the worst case, we have to advance one leaf in the current tree on all layers i = 1, . . . , T − 1. The cost for this case are obtained by adding the costs for the precomputation of SigTi,ji +1 and RootTi,ji +2 for all layers i = 2, . . . , T and AuthTi,ji ,li +1 for all layers i = 1, . . . , T . This yields coffline . During the offline part, we have to store SigTi,ji +1 which requires twi−1 · n bits and the stack required by treehash to construct RootTi,ji +2 which requires hi · n bits, i = 2, . . . , T . Further, we have to store AuthTi,ji ,li +1 and some temporary nodes required by Szydlo’s algorithm which require 3hi ·n bits, i = 1, . . . , T . This yields moffline . 2.5 Verification The verification process of GMSS is essentially the same as for MSS and CMSS. The verifier knows the public key RootT1,0 and the parameter set P used by the signer. At first, he verifies the one-time signature Sigd of the digest d using the Winternitz parameter wT . Doing so, he obtains the verification key for this signature, i.e. leaf lT of tree TT,jT . Then, the verifier repeats the following steps for i = T, . . . , 2. (1) use li and AuthTi,ji ,li to compute RootTi,ji . (2) use RootTi,ji and verify SigTi,ji and obtain li−1 . Finally, the verifier uses l1 and AuthT1,j1 ,l1 to obtain RootT1,0 . If RootT1,0 matches the signers public key, the signature is accepted. Lemma 8 (Verification Cost). The average cost for the verification is cverify = T P ((2wi − 1)twi /2 + hi ) cHash . (9) i=1  Proof. On average, (2wi − 1)twi /2 hash evaluations are required to verify an one-time signature. Using a leaf and an authentication path to construct a root requires hi hash evaluations. Since there is a one-time signature and an authentication path for each layer the average costs for the verification are c verify . 3 GMSS in Practice In this section, we give practical GMSS parameters that simultaneously allow for a large signature capacity, good efficiency and small bandwidth, and describe how to integrate GMSS in a protocol such as SSL with a client/server architecture. 3.1 Choosing P To find an optimal parameter set, we consider following optimization problem: given certain bounds on the signature capacity as well as the key generation, signature generation and verification time, find the parameter set which provides the smallest signatures. We formulated this optimization problem as mixed integer program (MIP) using Zimpl [9]. The constraints of this MIP are the equations for the key generation (1), signature generation (4),(8) and verification (9) time and the signature size (3). Note that the worst cast cost of Szydlo’s algorithm for the authentication path computation shown in Equation (7) occurs only once per tree. To compute the parameter sets, we use the average costs of Szydlo’s algorithm, which are      hi /2 · (2wi − 1)twi + 1 + hi /2 − 1 cHash + hi + twi cPrng for a tree on layer i. To solve the MIP, we used the free solver SCIP [1]. Using different bounds for the signature generation and verification time,  we obtained the following parameter sets Pk = T, (h1 , . . . , hT ), (w1 , . . . , wT ) that allow up to 2k signatures.   P40 = 2, (20, 20), (10, 5) P80 = 4, (20, 20, 20, 20), (8, 8, 8, 5) 0 0 P40 = 2, (20, 20), (9, 3) P80 = 4, (20, 20, 20, 20), (7, 7, 7, 3) Table 1 shows timings (t) and memory requirements (m) for the parameter sets when using a 160 bit hash function. The size of the public key is mpubkey = 20 bytes for all parameter sets. To get timings, we use the ratio cHash = cPrng = 0.002 ms, which we obtained using a Java implementation of SHA1 on a Pentium dualcore 1.8GHz. Table 1. Timings and memory requirements moffline P40 0 P40 P80 0 P80 3160 3200 7320 7500 bytes bytes bytes bytes mprivkey 1640 1680 4320 4500 bytes bytes bytes bytes msignature 1860 2340 3620 4240 tkeygen bytes 723 min bytes 390 min bytes 1063 min bytes 592 min tsign 26.0 10.7 26.1 10.1 ms ms ms ms tverify 19.6 10.7 18.1 10.1 ms ms ms ms This table clarifies the flexibility of GMSS. P40 and P80 provide the shortest possible signatures. In case of P40 , the signature size is reduced more that 26% 0 0 compared to what was stated in [3]. P40 and P80 provide very fast signature generation and verification times, at the expense of larger signatures. Note that a large portion of the signature cost is required for the precomputation of the upcoming authentication paths. One possibility to circumvent this is to use a tree of small height (≤ 5) in the lowest layer and to store it completely in memory. Then the authentication paths can be obtained for free. In case of a 160 bit hash function, storing a tree of height five requires 1,260 bytes. 3.2 Message Flow and Application to SSL/TLS Finally, we describe how signatures should be transmitted when the signer and the verifier are connected during the signing process as in case of the SSL/TLS protocol. Thanks to the online/offline strategy [5], the server has all signature parts ready from the beginning of the transaction, except for the one-time signature of the message digest Sigd . The server delays the generation of the online signature Sigd and sends only the first offline signature part SigTT,jT and RootTT,jT to the client. Then, the client demonstrates his honesty by sending leaf lT −1 (the verification key of SigTT,jT ) back to the server. The client has to spend some computational effort to obtain lT −1 , namely he has to verify SigTT,jT , while the server does not have to do anything. While the server is waiting for the client to send lT −1 , he can also start with next the offline part of the signing process. When the server receives the correct leaf lT −1 , he sends the remaining parts of the signature and starts to compute Sigd . In the same time, the client can verify the remaining one-time signatures SigTi,ji , i = 2, . . . , T − 1 that he receives from the server, and compares the root of the top tree to the server’s public key. In the final step, the server sends Sigd to the client who verifies its correctness. PSfrag replacements abort update Sigi and Authi , i ≤ T for next signature false Signer (server) sign lT −1 true digest correct? RootT AuthT −1 SigT compute lT −1 SigT −1 lT −1 compute RootT −1 Verifier (client) compute lT −2 compute Root1 Root1 correct? false AuthT Sigd Auth1 compute lT true continue reject compute RootT RootT correct? false true accept reject Fig. 5. Message Flow for SSL/TLS The overhead of our protocol for the server is just 2n bits memory to store RootTT,jT and lT −1 . The benefits are as follows: it minimizes bandwidth and server-side calculations in case of DoS attacks, and optimizes the latency of the transaction. Indeed, the protocol can be stopped early in case of DoS. In addition, the signature generation, transmission and verification stages are performed concurrently. 4 Conclusion We presented the generalized Merkle signature scheme (GMSS). GMSS is parameterized by the parameter set P, that allows a great degree of freedom in choosing the signature capacity, the signature generation and verification timings, and the signature size. GMSS uses a scheduling strategy to precompute upcoming signatures. This drastically reduces the signature generation time and in turn allows to choose parameters that provide smaller signatures. For a signature capacity of 240 , the signature size is 1,860 bytes, where signature generation and verification requires 26 ms and 19.6 ms, respectively. GMSS is the first Merkle-type signature scheme that maintains its efficiency even if the signature capacity cryptographically unlimited, i.e. 280 . In that case, the signature size is 3,620 bytes, where signature generation and verification requires 26.1 ms and 18.1 ms, respectively. For both signature capacities (240 , 280 ), it is also possible to find parameter sets such that the signature generation and verification time is only 10 ms. This makes GMSS a serious competitor to commonly used signature schemes such as RSA or ECDSA. Furthermore, GMSS does not rely on number theoretic problems and is not vulnerable to quantum computer attacks. Finally, we proposed a DoS-resilient protocol for SSL/TTL that minimizes the total latency of a signature exchange. References 1. Tobias Achterberg. SCIP - a framework to integrate constraint and mixed integer programming. Technical Report 04-19, Zuse Institute Berlin, 2004. 2. Mihir Bellare and Sara K. Miner. A forward-secure digital signature scheme. In Proc. Advances in Cryptology (Crypto’99), volume 1666 of Lecture Notes in Computer Science, pages 431–238. Springer-Verlag, 1999. 3. Johannes Buchmann, Luis Carlos Coronado Garcia, Erik Dahmen, Martin Döring, and Elena Klintsevich. CMSS – an improved Merkle signature scheme. In Proc. Progress in Cryptology (Indocrypt’06), volume 4329 of Lecture Notes in Computer Science, pages 349–363. Springer-Verlag, 2006. 4. Chris Dods, Nigel Smart, and Martijn Stam. Hash based digital signature schemes. In Proc. Cryptography and Coding, volume 3796 of Lecture Notes in Computer Science, pages 96–115. Springer-Verlag, 2005. 5. Shimon Even, Oded Goldreich, and Silvio Micali. On-line/off-line digital signatures. In Proc. Advances in Cryptology (Crypto’89), volume 435 of Lecture Notes in Computer Science, pages 263–277. Springer-Verlag, 1990. 6. Digital signature standard (DSS). FIPS PUB 186-2, 2007. Available at http://csrc.nist.gov/publications/fips/. 7. Luis Carlos Coronado Garcı́a. On the security and the efficiency of the Merkle signature scheme. Cryptology ePrint Archive, Report 2005/192, 2005. http:// eprint.iacr.org/. 8. Markus Jakobsson, Tom Leighton, Silvio Micali, and Michael Szydlo. Fractal Merkle tree representation and traversal. In Proc. Cryptographer’s Track at RSA Conference (CT-RSA’03), volume 2612 of Lecture Notes in Computer Science, pages 314–326. Springer-Verlag, 2003. 9. Thorsten Koch. Rapid mathematical programming. Technical Report 04-58, Zuse Institute Berlin, 2004. 10. Arjen K. Lenstra and Eric R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology, 14(4):255–293, 2001. 11. Ralph C. Merkle. A certified digital signature. In Proc. Advances in Cryptology (Crypto’89), volume 435 of Lecture Notes in Computer Science, pages 218–238. Springer-Verlag, 1989. 12. Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. 35th Annual Symposium on Foundations of Computer Science, pages 124–134. IEEE Comput. Soc. Press, 1994. 13. Michael Szydlo. Merkle tree traversal in log space and time (preprint). Available at http://www.szydlo.com/. 14. Michael Szydlo. Merkle tree traversal in log space and time. In Proc. Advances in Cryptology (Eurocrypt’04), volume 3027 of Lecture Notes in Computer Science, pages 541–554. Springer-Verlag, 2004. A Merkle’s Tree Authentication Scheme The tree authentication scheme was proposed by Merkle in [11] for using multiple one-time signature instances with a single “master” public key. Merkle’s tree authentication scheme in conjunction with a one-time signature scheme is referred to as the Merkle signature scheme (MSS). Keypair Generation: The signer first generates 2h one-time key pairs. The one-time verification keys form the leaves of a binary hash tree of height h, a so-called Merkle tree. The value of an inner node is obtained by hashing the concatenation of the values of its two children. Iterating yields the root of the tree which is the MSS public key, and the private key consists of the 2h one-time signature keys. Signature Generation: To authenticate the s-th leaf, i.e. the s-th verification key, the s-th authentication path is required. This authentication path consists of the h−1 siblings of the h−1 nodes on the path from the sth leaf to the root. The sth Merkle signature consists of four parts: first the index s ∈ {0, . . . , 2h −1} of the selected one-time signature; second, the one-time signature of data d generated with the s-th signature key; third, the s-th verification key; and fourth, the authentication path for the s-th verification key. Verification: After verifying the one-time signature of d, the verifier has to validate the authenticity of the supplied verification key. Using the index s and the authentication path of the s-th leaf, he re-computes the path from the sth leaf to the root. To do so, he hashes the concatenation of the s-th leaf and first node in the authentication path to obtain the first node on the path to the root (the order for concatenating is decided according to the index s). By successively concatenating the hashed nodes and authentication nodes, the verifier can eventually recover the root itself. If the root matches the signer’s public key, the signature is valid. B The Winternitz one-time Signature Scheme The Winternitz OTS [11], described in detail in [4], is parameterized by w, which allows a trade-off between the signature cost and size. Keypair Generation: The keypair generation produces tw random values x1 , x2 , . . . , xtw , where tw = dn/we + d(blog2 (dn/we)c + 1 + w)/we. Then, the one-time signature key is X = (x1 , . . . , xtw ), and the one-time verification key w w Y = H H 2 −1 (x1 )k . . . kH 2 −1 (xtw ) , where H k (x) denotes the hash function applied k times and k the concatenation of two strings. The cost for the key pair generation is cOTSkeygen = (2w − 1)tw + 1 cHash + tw · cPrng . Signature Generation: For an n-bit message digest d, the OTS is computed as follows. The binary representation of d (possibly padded) is divided into dn/we Pdn/we blocks of length w: b1 , . . . ,bdn/we . Next, the checksum C = k=1 2w − bk is calculated. The binary representation of C (possibly padded) is again divided into blocks of length w: bdn/we+1 , . . . , btw . Finally, the signature of d is Sig = (σ1 , . . . , σtw ), where σk = H bk (xk ), k = 1, . . . , tw . The signature size is tw · n bits and the average cost for signing is cOTSsign = (2w − 1)tw /2 · cHash . Verification: Given the digest d, the signature Sig = (σ1 , . . . , σtw ), and the verification key Y , the verifier computes b1 , . . . , btw just like the signer and w then calculates yk = H 2 −1−bk (σk ), k = 1, . . . , tw . The signature is accepted if cost is exH(y1 k . . . kytw ) equals the verification key Y . The average verification  actly the same as the signature cost. cOTverify = (2w −1)tw +1 cHash +tw ·cPrng .