Score:1

Usage of tweakable hash functions in SPHINCS+

bl flag

In the SPHINCS+ paper(https://sphincs.org/data/sphincs+-paper.pdf) part 3.2, it explains that they are not using l-trees as a direct consequence of the use of tweakable hash functions.

I have read the tweakable hash function part, but the math made me so confused. Can you explain to me the difference between the usual WOTS+ and the WOTS+ used in the current SPHINCS+? Is there a difference in the WOTS+ scheme due to the usage of the tweakable hash function and how do we use tweakable hash functions?

The part where they mention tweakable hash functions in WOTS+:

In contrast to previous definitions of WOTS+, and as a direct consequence of the use of tweakable hash functions to mitigate multi-target attacks, we do not use so-called ℓ-trees to compress the WOTS+ public key. Instead, the public key is compressed to an n-bit value using a single tweakable hash function call to Thlen. We use ‘WOTS+ public key’ to refer to the compressed public key.

Score:1
ru flag

An issue with hash tree signatures is the problem of multi-target attacks. Suppose that a forger generates many instances their own WOTS+ public key/private key pairs and tries to switch this public key for one a WOTS+ key validated by the upper tree. If the leaves of the upper tree all use the same hash function, then the forger will try and use that hash function to match any leaf. If she finds any one, then she can choose to swap out her WOTS+ key with that particular leaf. If there are $N$ leaves, then the forger's chance of success for a 256-bit hash is $N2^{-256}$ rather than just $2^{-256}$. Worse, a forger could target multiple legitimate signers all of whom are using the same hash function.

To avoid this detect-one-of-many (DOOM) situation, rather than use a single hash function SPHINCS+ uses a family of very similar hash functions where the choice of hash function from the family is known as the tweak. By allowing the tweak to depend on a user specific parameter we can sidestep attacks on multiple users, by allowing the tweak to depend on input size, they block length extension attacks and by allowing the tweak to depend on leaf index (or deriving the leaf index from the output) they block multi-targetting on a given tree.

In terms of how WOTS+ signatures are used in previous proposals, the collection of $\ell$ $256$-bit hash values that make up a WOTS+ public key were combined using a binary tree (with some missing nodes) to a single 256-bit value requiring $\ell$ hash evaluations. In SPHINCS+ the $\ell$ public hash value (say, $\mathrm{pub}_1,\mathrm{pub}_2,\ldots,\mathrm{pub}_\ell$) are just combined in a single (tweaked) hash function: $\mathrm{Th}(\mathrm{pub}_1,\mathrm{pub}_2,\ldots,\mathrm{pub}_\ell)$ which removes significant overhead.

Andrew avatar
bl flag
It is very clear now. Thank you so much for the detailed answer!
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.