I was reviewing the most recent version of the Catena paper and they made some claims that I find questionable in their reduction of the pseudorandomness of the output of Catena (p. 32). First I will mention that they say they are modeling $H$ as a random oracle (that their Catena oracle calls), but it seems like they ignore the fact that $flap$ calls $H$ in their analysis. Instead they treat $flap$ more like a black box. If we let this slide and assume that $H$ is only modeled as a random oracle in lines 1 and 5 of Algorithm 1 (p. 24), then the we can follow their claim on the upper bound of $q(g_{high} + 1)$ calls to $H$ (continuing with this assumption, a tighter upper bound on the number of calls to $H$ not presented by the authors is $q(g_{high} - g_{low} + 2)$).

The next statement they make is that the probability of a collision in one of the calls to $H$ values is upper bounded by $(q\cdot g_{high} + q)^{2}/2^{n}$. This value is slightly larger approximation (often used as a simplification) of the probability that evaluating $H$ on $q(g_{high} + 1)$ values produces a collision: $\binom{q(g_{high} + 1)}{2}/2^{n}$. So it's clear enough to see where the authors were going with this, but that seems flawed because we're not calling simply making a call to just $H$ on $q(g_{high} + 1)$ values. We're, for example, calling $H(flap(flap(H(\cdot))))$ on $q$ values when $g_{high} = g_{low}$ and $x = |H(\cdot)|$.

Let's ignore the complexity of intermediate calls to $flap$ for a moment and just model our Catena oracle as $H(H(H(\cdot))$. It seems like the logical leap in their analysis is that they are claiming $q$ queries to this oracle will produce a collision with the same probability as $3q$ evaluations of $H(\cdot)$. Let's examine this oracle. For each distinct pair of queries $a^{i} \neq a^{j}$, they will be equal after the first evaluation of $H$ with probability $1/2^{n}$, after the second with probability $1/2^{n}(1 - 1/2^{n}) + 1/2^{n} < 2/2^{n}$, and after the third with probability less than $1/2^{n}(1 - 2/2^{n}) + 2/2^{n} < 3/2^{n}$. Then our probability of a collision is less than $3\cdot \binom{q}{2}/2^{n} < 3q^{2}/2^{n}$. Contrast this with the probability of a collision in $H(\cdot)$ after $3q$ queries: $\binom{3q}{2}/2^{n} < 9q^{2}/2^{n}$. In their result for the upper bound of the collision probability, the number of invocations of $H$ is a squared factor, when it should be a linear factor. I guess technically it's still an upper bound.

So I believe at this point I've shown some serious flaws in the reduction here (though there are more), and will attempt to provide my own. In the previous paragraph we saw how for a given chain of functions the probability of a collision can be upper bounded by the sum of the probabilities of a collision between two arbitrary inputs when we consider each function in isolation. With this in mind we take another look at Algorithm 1. For simplicity, we will assume $x = |H(\cdot)|$.

Algorithm 1 invokes $g_{high} - g_{low} + 2$ times each $H$ and $flac$. Thus the probability of a collision is upper bounded by

$$\binom{q}{2} \big(g_{high} - g_{low} + 2\big)\big(1/2^{n} + Coll_{flap}(\cdot, \cdot)\big)$$

$$ < \big(g_{high} - g_{low} + 2\big)\big(q^{2}/2^{n} + q^2 Coll_{flap}(\cdot, \cdot)\big)$$

Another big error I'll point out here is that they used the advantage of an adversary playing the collision game in their reduction (not to mention somehow they went from this being played against $flac$ to simply against $F$). Since all queries are passed through a random oracle before $flap$ in the function chain, we should instead consider the generic collision probability for two inputs chosen uniformly at random: $Coll_{flap}(\cdot, \cdot)$.

The implicit assumption that is never stated in the proof is that the distinguisher outputs 1 if it finds a collision and 0 otherwise. The last thing the authors forget to take into account is the $\binom{q}{2} / 2^{n}$ chance that when interacting with a random oracle there will be a collision. Simply subtract this term from the last equation and I believe you have an actual upper bound on the pseudorandomness of Catena in the "semi-random oracle" model, and assuming $x = |H(\cdot)|$.

Was I right in my analysis of the errors in their proof? Did I correctly produce an upper bound for the pseudorandomness of Catena?

Edit: I also believe it could also be stated that if $flap$ is computationally almost universal and $x = |H(\cdot)|$, then Catena is a PRF in the "semi-random oracle model."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.