Deterministic Rand function for Winternitz One Time Signatures

Suppose you are implementing a Generalized Merkle Signature Scheme, using the Winternitz One-Time Signature Scheme for the node signatures. Furthermore, suppose the implementation is to be stateless (i.e. you don't keep track of which signatures have already been generated), meaning that you use a deterministic $Rand$ function for generating all private keys, so that any path through the tree might be re-generated on the fly.

Also suppose that the path is selected as a (public) function of the digest to be signed.

The question is, would choosing a $Rand$ function that is not a $PRF$ significantly weaken the GMSS scheme if it is attacked by a quantum computing capable adversary?

For instance, suppose you are using SHA-256/250 for the Message Digest and SHA-256 as the iterated One Way Function. Would choosing the $Rand$ function below be a bad idea? The input value is the binary representation of the path of the private key in the tree.

Let $k_0, k_1$ be two 256-bit AES-256 keys. These keys are the private key for GMSS.

Define function $Rand_{k_0,k_1}:\{0,1\}^{128\times2}\to\{0,1\}^{128\times2}$ as:

1. $INPUT: x_0,x_1$ (two 128-bit blocks)
2. $c_0 = E_{k_0}(x_1) \oplus x_0$
3. $c_1 = E_{k_1}(c_0) \oplus x_1$
4. $OUTPUT: c_0,c_1$ (two 128-bit blocks)

This $Rand$ function is not a $PRF$ in the random oracle model, because it might be distinguished from a random function with only two selected inputs. But is it good enough to prevent existential forgeries (or other attacks) against GMSS?

The security claim is 250 bit security against classical adversaries and 125 bit security against quantum computing capable adversaries (presuming the adversary can't choose the input message digest to be signed).

Conjecture: An existential forgery against GMSS is possible iff,

1. The adversary is able to recreate the Merkle tree(s) above some W-OTS public key $Y_{i,j}$, either because an authentic W-OTS $\sigma_{i,j}$ is part of a GMSS signature that has already been published, or because the adversary has knowledge of a sufficient number of other W-OTS private keys except the one at position $i,j$, and
2. The adversary either knows the entire W-OTS private key $X_{i,j}$, or the authentic digest signed by the authentic W-OTS $\sigma_{i,j}$ contains at least one zero bit and the adversary knows some of the (at least two) last elements of the private key $X_{i,j}$, corresponding to the checksum part of $\sigma_{i,j}$.

The most probable scenario (in which an existential forgery is possible) seems to be when the adversary knows some part of the W-OTS private key $X_{i,j}$ used for encoding the checksum part of $\sigma_{i,j}$.

Clearly, if the adversary knows one half of $(c_0,c_1) = Rand_{k_0,k_1}(x_0,x_1)$, the other half might be guessed with probability $2^{-128}$. The adversary will know one half of $(c_0,c_1)$ if there exists at least one known W-OTS signature $\sigma^{\prime}$ that signs a digest that contains at least one $b^{\prime}=0$ at a position for which $x_1=x_1^{\prime}$. In such case $c_0 = c_0^{\prime}\oplus x_0^{\prime}\oplus x_0$. Presumably, this will happen with a probability equal to the collision rate $Pr[\exists(x_1,x_1^{\prime})(x_1=x_1^{\prime})] = 2^{-64}$ times $Pr[b^{\prime}=0]=2^{-w}$.

This appears to indicate a security bound that is significantly less than the claim (presuming $w \ll 250-128-64$), but perhaps I am missing something. Or, is it even worse?

• I need (at least) 256 bit outputs because the Winternitz OWF has a 256 bit output. I need (at least) a 256 bit key, because the risk of collisions in the leaf keys must nut exceed the risk of collisions in the message digest function. I need a 256 bit seed because the number of leafs is $2^{250}$ and the total number of independent leaf keys is $2^{256}$. – Henrick Hellström Aug 12 '14 at 10:26