# How does FORS: Forest of Random Subsets work?

I saw a post named "How does signing with FORS work in SPHINCS+?" but in the post it seems like no one had explain how does the FORS works.

SK: Secret Key, PRF: Pseudo-Random Function

I'm know a bit how the key generation works. Just in case, I'll say what I know just to ensure it isn't misinterpret by me. Using a PRF to generate all the SK and hash it all one by one and the hash of each secret key will be the leave node of the tree. Construct a Merkle Tree base on those $$H(SK_i)$$. I also know that the size of the SK need to determine by the size of the $$H(M)$$ hash of the message and split the $$H(M)$$ into $$a$$ bits chunks.

$$H(M)=\{m_1,.....m_k\}$$. Each $$m_i$$ will be use as an index to search in? This is where i got very confuse. So, there will be K binary hash tree? And how to verify if there is K different trees? The verify key for each a-bit chunk will be the root node of the selected SK's tree? or all those root node combine together to contruct a Merkle tree? How the verification and key generation works? If anything I miss or wrong please correct me. Thanks for Answering.

• COSIC seminar "Introduction to Hash Based Signatures" (John Kelsey, KU Leuven & NIST) youtu.be/jiU0ICoiPI0?t=3310 Nov 15 at 20:54

How FORS works is fairly simple.

The signer selects $$k$$ lists of $$2^a$$ values each. For each such value $$x_{c, d}$$ (the $$d$$th item from the $$c$$th list), he computes the 'public' value $$H(x_{c,d})$$ (this is public not in the sense that we always tell the verifier about this, but instead we don't mind if the adversary hears it.

Then, to sign a message, we hash it into $$k$$ different $$a$$-bit values $$m_i$$. Then, we expose the private values $$x{i, m_i}$$, along with a proof that those private values were used to generate the public key.

If we sign $$2^\lambda$$ messages, then we expose a maximum of $$2^\lambda$$ private values for each list. Then, if someone picked his own message, he can generate a forgery if that message hashes to $$k$$ values which have all been exposed; the probability of this would be a maximum of $$2^{k \cdot (\lambda - a))}$$; that is, against this attack, FORS has $$k(a - \lambda)$$ bits of security (and the other attack is one against the hash function itself).

Everything else (including the Merkle tree) are details to make this work.

The Merkle tree is there because it gives an efficient way of proving that an intermediate value was used to generate the public key (without exposing any other private value). We have all the $$H(x_{c,d})$$ values for list $$c$$ be the leaves of the Merkle tree, and hash them pairwise together until we obtain the Merkle tree root. Then, to prove that a specific $$x_{c,d}$$ value is, in fact, the one we originally used, we expose that value, along with the authentication path, allowing a verifier to reconstruct the Merkle tree root.

And, we hash all $$k$$ Merkle tree root values together, to form the final private key (so we don't have to publish $$k$$ separate hashes)

So, there will be K binary hash tree?

Yes, as explained about, there are $$k$$ Merkle trees involved.

And how to verify if there is K different trees?

I don't quite understand what you're asking. If you're asking how we know the signer didn't pick two of the trees (or lists in the above description) to be the same, well, actually we don't care (as long as the probability of the key generation process selecting two lists being identical is no more than expected).

The verify key for each a-bit chunk will be the root node of the selected SK's tree?

Yes (or, as I explained, in practice the verify key for the entire FORS will be the hash of all the root nodes).

or all those root node combine together to contruct a Merkle tree?

We could make a Merkle tree to combine the root nodes together. However, just performing a larger hash does the same job, and is cheaper (fewer hash compression or permutation operations involved).

How the verification and key generation works?

Key generation works by selecting the base values, hashing them, computing the Merkle trees, and hashing the root values.

Verification works by hashing the message, extracting the $$x_{c, d}$$ values from the signature, hashing through the authentication paths to get the Merkle tree roots, hashing those $$k$$ values together, and seeing if you get the expected final hash in the public key.