key: cord-0046993-xcba98f2
authors: Yehia, Mahmoud; AlTawy, Riham; Aaron Gulliver, T.
title: Hash-Based Signatures Revisited: A Dynamic FORS with Adaptive Chosen Message Security
date: 2020-06-06
journal: Progress in Cryptology - AFRICACRYPT 2020
DOI: 10.1007/978-3-030-51938-4_12
sha: e1987886acdc2cb6cd2a76aa83acd8ef104ac815
doc_id: 46993
cord_uid: xcba98f2

FORS is the underlying hash-based few-time signing scheme in SPHINCS[Formula: see text], one of the nine signature schemes which advanced to round 2 of the NIST Post-Quantum Cryptography standardization competition. In this paper, we analyze the security of FORS with respect to adaptive chosen message attacks. We show that in such a setting, the security of FORS decreases significantly with each signed message when compared to its security against non-adaptive chosen message attacks. We propose a chaining mechanism that with slightly more computation, dynamically binds the Obtain Random Subset (ORS) generation with signing, hence, eliminating the offline advantage of adaptive chosen message adversaries. We apply our chaining mechanism to FORS and present DFORS whose security against adaptive chosen message attacks is equal to the non-adaptive security of FORS. In a nutshell, using SPHINCS[Formula: see text]-128s parameters, FORS provides 75-bit security and DFORS achieves 150-bit security with respect to adaptive chosen message attacks after signing one message. We note that our analysis does not affect the claimed security of SPHINCS[Formula: see text]. Nevertheless, this work provides a better understanding of FORS and other HORS variants, and furnishes a solution if new adaptive cryptanalytic techniques on SPHINCS[Formula: see text] emerge.

The current digital signature infrastructure adopts schemes that rely on the hardness of factoring or finding discrete logarithms in finite groups [12, 18, 24] . Given recent advances in physics which point towards the eventual construction of large scale quantum computers [1] , these hard problems will be solved in polynomial time using Shor's algorithm [25] . Lattice-based, coding-based, and multivariate signatures are considered quantum resilient schemes in the Q1 model [7] . However, either their exact security with respect to quantum attacks is still not clear [5, 11] or their communication/storage complexity is impractical to a multitude of applications, e.g., megabyte keys for the matrices of McEliece-based cryptosystems [27] . On the other hand, hash-based digital signatures have moderately sized keys (order of kilobytes), and their quantum security relies solely on that of hash functions based on Grover's algorithm. They have been proven to offer simple quantum resilient security properties [26] . Note that the proofs in [26] follow the Q1 model where no superposition queries to quantum oracles are allowed [7] .

Hash-based signature algorithms are comprised of two schemes, an underlying signing scheme and an extension algorithm. The former algorithm defines the main signing procedure where a key pair can be used to sign one (Lamport [19] , Winternitz one time signature scheme (WOTS), WOTS++ [8, 14] ) or a few messages (e.g., Biba [21] , HORS [23] , HORS++ [22] , PORS [2] , and FORS [4] ), after which a new key pair should be generated to maintain security against forgery attacks. More precisely, the security of hash-based few time (HBFT) signature schemes decreases after revealing each signature, and hence their bitsecurity is given under the condition that re-keying is required after r signatures. Accordingly, translating this constraint to acceptable attack models implies that a maximum of r queries are allowed to the signing oracle.

The extension algorithm is a top level construction that employs several instances of underlying signing schemes (OTS and HBFT) in a Merkle tree structure. Such an algorithm enables signing multiple messages where signatures are verified with one public key (Merkle root) . Extension algorithms can be stateful such as Merkle Signature Scheme MSS [20] , eXtended Merkle Signature Scheme (XMSS) [9] , XMSS+ [15] , Multi Tree XMSS (XMSS MT ) [16] , and XMSS with tightened security (XMSS-T) [17] , or stateless such as SPHINCS [5] , SPHINCS + [4, 6] , and Gravity SPHINCS [3] . Stateless signature algorithms conform to the basic definition of digital signatures where no state updates are required to guarantee security, and only keys are needed to securely generate valid signatures at any time.

The security of hash-based signature algorithms relies on the security of the underlying basic signing schemes. SPHINCS is a hyper-tree construction that uses WOTS and HORS trees for signing. In [2] , Aumasson and Endignoux investigated the subset-resilience problem [23] and showed that HORS is vulnerable to weak-message attacks where an adaptive adversary looks for messages that produce smaller Obtain Random Subsets (ORSs). Consequently, they reported a 7-bit decrease in the expected security of SPHINCS against classical attacks. Moreover, they proposed PORS, a variant of HORS which employs a pseudorandom bit generator (PRNG) instead of a hash function to obtain random subsets with distinct elements, thus avoiding the effect of weak messages. However, PORS is not secure against adaptive chosen message attacks where an adversary is able to generate random subsets for as many messages as they want, and select a set of r message for online queries. Finally, FORS, another HORS variant, was proposed and is currently adopted in SPHINCS + , a round 2 candidate in the NIST Post-Quantum Cryptography standardization competition [4, 10] . Compared to PORS, FORS mitigates weak-message attacks by increasing the size of the keys by a factor of κ where κ is the number of random subsets, and the overall signature size is also increased when it is integrated in a hyper-tree structure. On its own, the security of FORS against adaptive chosen message attacks decreases significantly with each signed message, which currently has no known effect on the security of SPHINCS + because it employs a pseudorandomly generated randomizer that is publicly sent along with the signature, and is used as a key for the hash function in FORS to obtain the random subsets. However, if cryptanalytic techniques are devised which can annihilate how this public randomizer is utilized or can break its generation procedure, then SPHINCS + will be vulnerable to adaptive chosen message attacks. Hence, given the significance of SPHINCS + as a candidate for standardization, we believe our analysis of its underlying signature scheme, FORS, is important, along with DFORS which offers a drop-in strengthened candidate.

In what follows, we summarize the contributions of this paper.

-We analyze the security of FORS against adaptive chosen message adversaries. We show that its bit security with respect to adaptive chosen message attacks decreases significantly when compared to its security in a nonadaptive setting. We adopt the adaptive chosen message attack model defined by Reyzin and Reyzin [23] and used in the analysis of HORS and PORS. -We propose a hash chaining mechanism that binds the process of generating a message ORS with signing it, which eliminates the offline adversarial advantage and makes ORS generation feasible only for the signing entity. We apply the chaining scheme to FORS and present Dynamic Forest Of Random Subsets (DFORS), a new HORS variant that resists adaptive chosen message attacks. We show that the bit-security of DFORS with respect to adaptive chosen message attacks is more than that of FORS by a factor of r + 1, where r is the number of signed messages per key under a given security level. -We analyze the security of DFORS with respect to adaptive chosen message adversaries, discuss its limitations, and report its theoretical computational and communication performance. Finally, we compare DFORS with FORS and other HORS variants.

In what follows, we provide the notation and definitions used throughout the paper. FORS can be seen as a generalized instance of HORS and it inherits most of the specifications of HORS. Accordingly, for completeness, we provide a brief overview of the HORS signature scheme.

Let n denote our security parameter. Consider a finite key space K, message space of arbitrary length M, the two hash families H and G where H = {H k :

is an κτ -bit (resp. n-bit) keyed one-way function. Let the κτ -bit message digest of an arbitrary length message m ∈ M be divided into κ elements, each of length τ bits, such that the integer representation of a given element is a subset of {0, 1, . . . , t − 1}, where t = 2 τ . We refer to the set {0, 1, . . . , t − 1} by T , and the subset of κ-elements of the set T is denoted by S κ (T ). Let ORS κ (m) denote an Obtain Random Subset function which returns a κ element subset from the κτ -bit hash value of a message m, formally defined as follows

The notion of ORS functions was introduced by Reyzin and Reyzin when HORS was proposed [23] . It has been shown that the security of the scheme is reduced to the subset resilience problem [23] . More precisely, for a given bit-security level, at most r messages can be signed before re-keying is required, otherwise an adversary can find a message whose ORS is covered by the union of the ORSs of the r messages. 

If finding the above cover relation for a given ORS function is infeasible, then it is said that such a function is r-subset resilient. 

A (1 n ,κ,t) , the probability of finding (m 1 , m 2 , . . . , m r+1 ) such that ORS κ (m r+1 ) is a subset of ORS κ (m 1 ) ∪ ORS κ (m 2 ) ∪ . . . ∪ ORS κ (m r ) is negli- gible, Formally Pr[(m 1 , m 2 , . . . , m r+1 ) ← A (1 n ,κ,t) : C r κ (m 1 , m 2 , . . . , m r+1 )] ≤ negl(n, t).

In HORS [23] , the signer randomly generates t secret keys each of n-bit length, (SK = sk 0 , sk 1 , . . . , sk t−1 ). Using a one-way function f : {0, 1} n → {0, 1} n , the signer computes the public key, P K = (pk 0 = f (sk 0 ), pk 1 = f (sk 1 ), . . . , pk t−1 = f (sk t−1 )). Security. Assuming that f is a one-way function, the security of HORS is reduced to the hardness of the (target) subset-resilience problem [23] . It has been shown that the probability of finding a message (m r+1 ) such that ORS κ (m r+1 ) is covered by the obtained random subsets of the r previously signed messages is (rκ/t) κ which corresponds to the probability of κ randomly chosen elements being a subset of the revealed rκ secret keys. The corresponding bit-security is then

In [2] , it was proven that the security of HORS with respect to adaptive chosen message attacks is

(see Appendix B). A practical example of a weak-message attack was also given where an adaptive adversary finds messages that map to subsets with repeated indices which results in smaller subsets, i.e., number of distinct elements < κ. Such subsets are easier to cover and consequently, a 7-bit decrease in the expected security of SPHINCS against classical attacks was reported.

Variants. HORS++ [22] was introduced to provide security against adaptive attacks. A one-to-one mapping function S(m) that belongs to a cover-free family [13] is utilized to ensure that for any r + 1 messages S(m r+1 ) r i=1 (S(m i ). Three constructions for S(m) based on polynomials over finite fields, error correcting codes, and algebraic curves over finite fields were presented. Consequently, HORS++ increases the signature size and the size of the secret keys to achieve the same security level of HORS against non-adaptive chosen message attacks. Moreover, the computational efficiency is decreased due to the computation of S(m). Later, PORS was suggested to replace HORS in SPHINCS where the idea of having distinct elements in subsets of weak messages was enforced by use of a pseudorandom bit generator to obtain the subsets [2] . However, although PORS mitigates weak-message attacks, it is still vulnerable to adaptive chosen message attacks under the definition given in Appendix B. Lastly, FORS was proposed and used in SPHINCS + [4] , where security against weakmessage attacks is achieved by increasing the key size from t values to κt values such that each index out of the κ indices in the ORS reveals a secret key from a different pool of t secret keys. Accordingly, when integrated in a tree structure the size of the signature also increases.

Unlike HORS which generates t secret keys from which the secret keys that are indexed by ORS(m) are released, FORS generates (κt) secret keys and dedicates t secret keys for each index out of the κ indices. By doing so, FORS mitigates weak message attacks because even if two elements in ORS(m) are equal, they index values from different secret key pools. The n-bit public key of FORS is the hash of the concatenation of κ Merkle tree roots. Each root is associated with a binary hash tree whose leaves are the hashes of t secret key elements in a given pool. Accordingly, one FORS instance has κ trees, each of height log t = τ . Figure 1 depicts the signatures of message 100 011 110 using (a) HORS and (b) FORS, where κ = 3 and t = 8. In FORS, the first 3 bits, i.e., 100, of the message selects sk 4 , the secret key corresponding to the 4-th leaf indexed from the left and starting from 0 in the first tree along with its authentication path to root 0 . Similarly, the second (resp. third) 3 bits of the message selects sk 3 (resp. sk 6 ) from the second (resp. third) tree with the authentication path to root 1 (resp. root 2 ). In HORS, the three 3-bit parts of the message index sk 4 , sk 3 , and sk 6 from the same tree, and with each selected secret key a 3 node authentication path is selected, hence the overlap in the node (colored in pale red and gray) at the pre-root level. More details about hash trees and authentication path calculations are provided in Sect. 4. It can be verified from Fig. 1 that if two 3-bit parts of the message are equal, then the same secret key value is revealed in HORS. This fact is exploited in the weak messages attack where an adversary searches for messages that have as many repeated indices as possible, which lead to ORSs containing fewer distinct elements, and thus can be easily covered with the ORSs of the revealed r messages. However, this problem is mitigated in FORS because repeated indices select secret keys from different pools. In what follows, we investigate the security of FORS with respect to non-adaptive chosen message attacks.

Reyzin and Reyzin introduced clear attack models for analyzing HBFT signature schemes against (non) adaptive chosen message attacks [23] . Such models are used in the analysis of all HORS-variants, i.e., PORS, and FORS. Specifically, in a non-adaptive setting, also referred to by r-target subset resilience problem (see Definition 3), an adversary is required to first choose r messages m 1 , m 2 , . . . , m r , after which they are provided with key k of H k and allowed to select a message m r+1 and evaluate H k (m r+1 ). A successful non-adaptive chosen message attack happens when the adversary is able to find C r κ , i.e., find a message m r+1 that is in an r-subset cover relation with m 1 , m 2 , . . . , m r . This scenario corresponds to an attacker who is trying to forge a signature after observing all r allowed signatures per key, or an adversary who is allowed r queries at a time before being supplied with k to verify any of the returned signatures. Few-time signature schemes are expected to maintain their security against forgery attacks even after releasing all r signatures.

Finding C r κ in FORS. Given an adversary who observed the signatures of r messages, finding a message m r+1 that is in an r−subset cover relation with the other r messages (C r-FORS κ (m 1 , m 2 , . . . , m r+1 )) has probability of success (r/t) κ [6] , which is equal to the probability that each log t-bit element out of the κ elements in ORS(m r+1 ) is covered by an element at the same position of the ORSs of the other r messages, i.e.,

where h i (m j ) denotes the i-th ORS element of the j-th message. Accordingly, the corresponding bit-security against non-adaptive chosen message attacks is given by

In this setting, an adversary is given the hash key k and allowed to evaluate H k for any message of their choice before selecting r + 1 messages. This attack also indicates the r-subset resilience of the signature algorithm (see Definition 2) . The definition of adaptive chosen message attack is given in Appendix B. Applying the same analysis to FORS, given the key k of H k , an adversary A generates the ORSs of q > r messages offline, where H k (m i ) = h 0 ||h 1 ||. . . ||h κ−1 and ORS(m i ) = {h 0 , h 1 , . . . , h κ−1 }, for 0 ≤ i ≤ q − 1 A searches for all possible combinations of (r + 1) message sets from the set of q messages. For any given r + 1 messages combination, the probability that message m r+1 is covered by the remaining r messages (i.e., C r-FORS κ (m 1 , m 2 , . . . , m r+1 )), is (r/t) κ . Accordingly, A obtains q r+1 sets of r + 1 messages and each set gives r+1 r possible choices for m r+1 . Therefore, the probability of A successfully generating C r-FORS κ is bounded from above by

which can be approximated by

Assuming a success probability close to 1, the above equation can be expressed as

Then the bit security of FORS with respect to adaptive chosen message attacks is given by κ r + 1 (log 2 t − log 2 r) + log 2 r! r + 1 .

One may conclude that due to the offline adversarial advantage given to A (i.e., knowledge of k implies the feasibility of evaluating ORSs for more than r messages of their choice), FORS bit security against adaptive chosen message attacks decreases by a factor of (r + 1) when compared to the non-adaptive setting. Note that, currently there is no attack against SPHINCS + that can utilize the offline adversarial privileges and produce r + 1 messages in an r-subset cover relation. This is because SPHINCS + uses a fixed pseudorandom generation of the key k to get the obtained random subset ORS κ (H k (m)). We also note that k is message dependent and is sent in the clear with each signature so verification takes place. Accordingly, in the event of attacks on the process by which k is evaluated from m, a dramatic decrease in the security of SPHINCS + will follow. Consequently, in the following section we present a technique that is robust against adaptive chosen message attacks on FORS. Our mechanism annihilates the adversarial offline advantages associated with knowing the hash key k.

In this section we present Dynamic Forest Of Random Subsets DFORS, a new HORS-variant that mitigates the offline advantage of an adversary which leads to the adaptive chosen message attack on FORS (discussed in Sect. 3). The main feature of DFORS is that the generation of the ORS is performed concurrently with signing such that each signature element is utilized to generate the next element of the ORS. In other words, signing and ORS generation are bound together using a chaining mechanism that utilizes the revealed secret keys. This procedure ensures that given a message, only the signer is able to efficiently generate an ORS. By doing so, even if an adversary has knowledge of k, they are not able to compute ORSs of a given message of their choice unless they have some secret key knowledge. In what follows we give a detailed specification of DFORS.

DFORS uses the following parameters.

n : The security parameter and the bit-length of (i) the secret seed SK.seed, (ii) secret keys sk i,j (0 ≤ i ≤ t − 1, 0 ≤ j ≤ κ − 1), (iii) public key P K.root, and (iv) the output of the used one way function F , and hash function G. κ : The number of (i) sub-strings of the input message, (ii) secret key pools where each contains t secret keys, and (iii) hash trees. τ : The bit length of a sub-string of the input message and the hash tree height. t : the number of secret keys per pool and the number of leaves in each hash tree, t = 2 τ .

The input message for DFORS is of length κ log t = κτ bits. To achieve n-bit security when signing r messages, we have κτ > n (see Sect. 5.1).

In what follows, we give the specifications of the secret and public key generation procedures. Moreover, DFORS is described in Algorithm 2.

Secret Key Generation. Let SK.seed denote an n-bit secret seed that is sampled at random. Given a pseudorandom function, P RF :

where each set of t secret keys belong to one of the κ pools.

the leaf nodes of the κ hash trees are generated, L i,j = F (sk i,j ). Every t leaves, L * ,j , are combined together in a Merkle tree construction to form the j-th (out of κ) tree. Then, the roots of these κ trees, root 0 , root 1 , . . . , root κ−1 , are concatenated to form an input to the hash function to get the n-bit public key expressed as

Binary Hash Tree. DFORS uses the XMSS binary Merkle tree construction [9] . The height of the binary hash tree is τ . It has τ + 1 levels, t = 2 τ leaf nodes (each of size n bits) on level 0, i.e., L i , 0 ≤ i ≤ t − 1, and an n-bit root node on level τ . We denote the nodes in level j by N i,j where 0 ≤ i < 2 τ −j , 0 ≤ j ≤ τ and N i,0 = L i . To construct the tree, the hash function G and a 2n-bit mask, q, per hash evaluation are used. These bit masks are introduced to provide secondpreimage resistance. The rationale for using different bit masks for each hash evaluation is to mitigate multi-target attacks [17] . For details on generating the hash keys K i,j and bit masks q i,j , the reader is referred to [4, 17] . Formally, for 0 < j ≤ τ , a node N i,j is given by Tree Root

A binary hash tree with the nodes in the authentication path (colored in gray) for leaf node L3 (colored in black)

We denote by Z(h) a function that takes as input κτ bits, h, and outputs the j-th τ bits of h, where j = h mod κ. Formally, Z :

The signing algorithm takes as input the message m, the secret seed SK.seed, and the hash key k. It constructs the κ trees as explained above in Sect. 4.2. To compute the κ random subset ORS κ (m) = (b 0 , b 1 , . . . , b κ−1 ) , the algorithm first evaluates H k (m) = h 0 , then computes Z(h 0 ) = b 0 . The first element in the signature, sig 0 , is comprised of i) the secret key of index b 0 in the first pool, σ 0 = sk b0,0 , and ii) the corresponding authentication path Auth 0 , thus sig 0 = σ 0 , Auth 0 . Next, h 0 and sk b0,0 are used to choose the second random element, Z(h 1 ) = b 1 , where h 1 = H sk b 0 ,0 (h 0 ||h 0 ). The second signature element, sig 1 , is the secret key of index b 1 in the second pool, σ 1 = sk b1,1 , and its corresponding authentication path Auth 1 , sig 1 = σ 1 , Auth 1 . In general, the i-th element of the ORS κ (m) is given by

. The i-th signature element, sig i , is the secret key value of index b i in the i-th pool and its corresponding authentication path Auth i , sig i = σ i , Auth i , where σ i = sk bi,i . The above process is repeated until κ elements are generated (b 0 , b 1 , . . . , b κ−1 ) . Finally, the signature is given by Σ = (sig 0 , sig 1 , . . . , sig κ−1 ) = (sk b0 , Auth 0 , sk b1 , Auth 1 , . . . , sk bκ−1 , Auth κ−1 ) = (σ 0 , Auth 0 , σ 1 , Auth 1 , . . . , σ κ−1 , Auth κ−1 ).

The ORS generation and signing process is illustrated in Fig. 3 .

The authentication path of a leaf L i contains all the sibling nodes of the nodes in the path from the leaf L i to the tree root. It is required so that the verifier can successfully generate the root in order to verify the signature element σ i related to the leaf node L i . Figure 2 shows a simple hash tree with the authentication path for leaf L 3 colored in black and the authentication path nodes colored in gray, Auth i = (L 2 , N 0,1 , N 1,2 ) . 

The verification algorithm takes as input the message m, the public key P K.root, the hash key K, and the signature Σ = (σ 0 , Auth 0 , σ 1 , Auth 1 , . . . , σ κ−1 , Auth κ−1 ). It computes H k (m) = h 0 , then Z(h 0 ) = b 0 to get the leaf index of the first hash tree. Then, it applies the one-way function F to the signature element σ 0 of the signature Σ to get the leaf node L b0 in the first tree. The authentication path Auth 0 and the leaf L b0 are used to compute the root of the first tree. The leaf index b 0 is required so that the verifier knows which node is concatenated on the right and on the left. The tree root calculation procedure is described in Algorithm 1. Generally, the verification algorithm computes the i-th tree root by applying Algorithm 1 on σ i , Auth i , and the leaf index b i where b i = Z(h i ), and h i = H σi−1 (h 0 ||h i−1 ). This process is repeated until κ tree roots are computed which are then concatenated to form an input to the hash function G. If the output of G is equal to P K.root, the signature is valid, otherwise verification fails.

Input: Leaf node Li, Leaf index i, Auth. Path = (A0, A1, . . . , Aτ−1) .

Li,j ← F (ski,j) end for end for Compute the roots of the κ tree as described in section 4.2 P K.root ← G(root0||root1||. . . ||rootκ−1) Output (SK.seed, P K.root) end procedure procedure Signing(m, SK.seed,k, κ, t)

Generate the κ binary hash trees as in key generation procedure Auth0, σ1, Auth1, . . . , σκ−1, Authκ−1) Output (Σ,m) end procedure procedure Verification(m, P K.root, k, Σ = (σ0, Auth0, σ1, Auth1, . . . , σκ−1, Authκ−1))

In what follows, we analyze the security of DFORS and demonstrate the effect of the dynamic chaining on the security of FORS. Afterwards, the computational cost of the DFORS key generation, signing, and verification algorithms are presented. The bit size of the signature and keys are also given.

In this section, we present a detailed analysis of DFORS with respect to weakmessage attacks and r-target subset resilience adversaries. More precisely, since the proposed chaining technique does not allow an adaptive adversary who has knowledge of k to compute the ORSs of any message of their choice before asking the signing oracle for its signature, DFORS is essentially r-subset resilient. Hence, our analysis focuses on its security when an adversary is given the signatures of r messages.

Weak-Message Attacks. DFORS inherits FORS mitigation to weak-message attacks [6] because it specifies an independent key pool for each index in the ORS. Consequently, even if an ORS element is repeated, the corresponding revealed secret keys will be different.

r-Target Subset Resilience. According to Definition 3, we assume an adversary A when given the ORSs of r messages will return m r+1 where C r κ (m 1 , m 2 , . . . , m r+1 ). In what follows, we show that the success probability of A is bounded from above by (r/t) κ . Note that since ORS generation is secret key dependent, the ORS function of DFORS is intrinsically r-subset resilient. In other words, the value of any random ORS element, b i , depends on the previously revealed signature element σ i−1 = sk bi−1 and the original message m. Accordingly, without any oracle queries, A has no feasible function to evaluate ORSs of messages of their choice. On the other hand, if A is given the signatures of r messages or they queried r messages of their choice, they need to find a message m r+1 such that each element in its obtained random subset, ORS DFORS κ (m r+1 ) = (b 0 , b 1 , . . . , b κ−1 ), is covered by the elements at the same corresponding positions in the ORSs of the other r messages

Due to the chaining process in generating b 0 , b 1 , . . . , b κ−1 , A generates the ORSs sequentially. At any position i,

, then A fails. In addition, they cannot evaluate b i+1 = Z(H sk b i (h 0 ||h i )) when sk bi is not revealed by any of signatures of the r messages, Generally, for the i-th position in

where σ i (m j ) and b i (m j ) denote the i-th signature element and i-th ORS element of the j-th message, respectively. Thus, the probability that A finds C r κ (m 1 , m 2 , . . . , m r+1 ) successfully is equal to their probability of finding a message m r+1 such that ∀i ∈ {0, 1, . . . , κ − 1}, each of the log t-bit b i (m r+1 ) ∈ {b i (m 1 ), b i (m 2 ), . . . , b i (m r )}. Since A is given r messages, the probability of finding a cover for one b i (m r+1 ) is (r/t) i+1 because this implies that ∀j < i; b j (m r+1 ) ∈ {b j (m 1 ), b j (m 2 ), . . . , b j (m r )}. Thus, the probability of finding a cover for all the κ elements in ORS DFORS κ is equal to the probability of finding a cover for the last element, b κ−1 (m r+1 ), which is (r/t) κ . Therefore

so the corresponding DFORS bit-security against adaptive chosen message attacks is log 2 (t/r) κ = κ(log 2 t − log 2 r).

Compared to the adaptive chosen message attack security of FORS (See Sect. 3), the bit security of DFORS is higher by a factor of (r + 1). The extra cost is performing κ−1 more calls to the hash function. Unlike FORS, the signing procedure cannot be parallelized because of the chaining mechanism.

Key Generation. This procedure requires κt PRF function computations to generate the t secret values for κ pools, κt one-way function F computations to compute the leaf nodes of the hash trees, and κ(t − 1) + 1 hash function G evaluations to evaluate the κ hash trees and get the public key P K.root.

Signing. This procedure requires κt PRF function computations, κt one-way function F computations, κt hash function (H and G) to compute the κ hash trees (κ(t − 1) hash G calls), and κ hash H calls to get ORS κ (m). Note that the whole tree structure is computed with each signature, otherwise, the scheme storage requirements will be huge. Verification. This procedure requires κ one-way function F computations that compute the trees leaves, κ(τ +1) hash function (H and G) evaluations to reconstruct the κ trees roots from the revealed secret values and the authentication paths (κτ calls to G), and κ calls H to get ORS κ (m). Signature Size. The signature contains κ secret key elements and κτ tree node for the associated authentication paths. Thus, the signature size is κn(τ + 1) bits, where n is the bit size of each secret keys and hash tree node. Length of Keys. The size of the secret key, SK.root, is equal to that of the public key, P K.root, and it is n bits.

The computational complexities of the above procedures are given in Table 2 .

DFORS inherits all the advantageous security properties of FORS. Additionally, it is secure against adaptive chosen message attacks. In fact, for the same parameters the bit-security of DFORS with respect to adaptive chosen message adversaries is equal to that of FORS under non-adaptive chosen message attacks. Table 1 gives a comparison between the bit security level of FORS and DFORS in an adaptive adversarial setting. We use the recommended parameters (i.e., n, τ , and κ) for all six instances of SPHINCS + . 

Hash † OWF denotes one-way function. ‡ Size is given as a factor of n bits. † † x = log κ for optimal signature size in case of HORST and for the upper bound on the signature size in PORS.

‡ ‡ Verification cost and signature size are the upper bound values. Table 1 shows the significant effect of increasing the number of signed messages, r, on the bit security of FORS. On the other hand, this effect is very reasonable with DFORS. For instance, when r = 1, an adaptive attack on FORS is equivalent to a collision attack on the underlying κτ -bit hash function H which has a complexity of 2 κτ /2 evaluations. However, due to the r-subset resilience of DFORS where finding a covered ORS requires successive dependency on the signature elements, an adversary must find a second preimage of the ORS in the revealed secret keys, hence the complexity is 2 κτ evaluations. Table 2 presents a comparison between DFORSand other HORS variants with respect to their computational efficiency, signature and key sizes, and security against adaptive chosen message attacks.

We analyzed the security of FORS, the underlying hash-based few-time signing scheme of SPHINCS + , with respect to adaptive chosen message attacks. We showed that as the number of signed messages, r, increases, its bit-security with respect to adaptive chosen message adversaries decreases significantly compared to its non-adaptive counterpart. As a solution, we proposed DFORS, which builds on FORS but utilizes a secret key dependent ORS function. Such a function binds the process of generating the ORS with signing which makes it feasible only for the signer. Accordingly, we showed that the bit security of DFORS against adaptive chosen message attacks is more than that of FORS by a factor of r + 1. Note that our analysis does not affect the claimed security of SPHINCS + but rather provides a better understanding of the security of its underlying signing scheme and offers a mechanism that can be adopted by most HORS variants to provide security against adaptive chosen message attacks. 

In [23] , the following adaptive chosen message attack against HORS was defined. Let A be an adaptive chosen message adversary against HORS such that given the key k, A can compute the hash of any message m and ORS κ (m) offline. Given a security parameter, n, under the birthday paradox, A can find r + 1 messages in a cover relation C r κ with which to query the signing oracle, formally Pr[k ← K, (m 1 , m 2 , . . . , m r+1 ) ← A(k) : C r κ (m 1 , m 2 , . . . , m r+1 )] ≤ negl(n).

Aumasson and Endignoux [2] subsequently presented an adaptive chosen message attack against HORS and proved that the security level decreases by a factor of r + 1 when compared to non adaptive chosen message attacks. Their attack is as follows. Given an adversary A and a key k, the hash value H k (m) for any message of their choice can be computed, and say there are q > r messages. For all possible combinations of (r +1) messages from the q messages, For any given subset, the probability of being an r-subset-cover relation is (rκ/t) κ . The number of (r + 1)-message combinations which A can construct from the q messages are q r+1 and each combination can form r+1 r choices. Accordingly, their probability of success in defeating the r-subset resilience (SR) is given by

Assuming a success probability close to 1, the security level of HORS against an adaptive chosen message attack is κ r + 1 (log 2 t − log 2 κ − log 2 r) + log 2 r! r + 1 .

Quantum supremacy using a programmable superconducting processor

Clarifying the subset-resilience problem. IACR Cryptology ePrint Archive

Improving stateless hash-based signatures

SPHINCS+-submission to the NIST post-quantum project

SPHINCS: practical stateless hash-based signatures

The SPHINCS+ signature framework

Quantum attacks without superposition queries: the offline simon's algorithm

On the security of the Winternitz one-time signature scheme

XMSS -a practical forward secure signature scheme based on minimal security assumptions

Round 2 submissions -Post-quantum cryptography

Lattice signatures and bimodal Gaussians

A public key cryptosystem and a signature scheme based on discrete logarithms

Families of finite sets in which no set is covered by the union of r others

W-OTS+ -shorter signatures for hash-based signature schemes

Forward secure signatures on smart cards

Optimal parameters for XMSS MT

Mitigating multi-target attacks in hash-based signatures

The elliptic curve digital signature algorithm (ECDSA)

Constructing digital signatures from a one-way function

A certified digital signature

The BiBa one-time signature and broadcast authentication protocol

Multiple-time signature schemes against adaptive chosen message attacks

Better than BiBa: short one-time signatures with fast signing and verifying

A method for obtaining digital signatures and public-key cryptosystems

Algorithms for quantum computation: discrete logarithms and factoring

A note on quantum security for post-quantum cryptography

On the equivalence of McEliece's and Niederreiter's public-key cryptosystems

The authors would like to thank the reviewers for their valuable comments that helped improve the quality of the paper.

The HORS key generation, signing, and verification procedures are given in Algorithm 3.