Let $F(S) = \text{Keccak-}f[1600](S)$.

Assuming that the length of $S$ is equal to $1600 \times k$ and if $k$ is greater than $1$, we define a function $F_{k}(S)$ as follows.

We note that $S$ is a concatenation of $k$ $1600$-bit sequences. We denote these parts by $X_1$, $X_2$, ..., $X_k$.

We choose (arbitrarily or randomly) $k^2$ different $1600$-bit sequences and denote them by $Y_1$, $Y_2$, ..., $Y_{k^2-1}$, $Y_{k^2}$. Note that these sequences are open, not secret.

Then $F_{2}(S) = A_{1} \mathbin\Vert A_{2}$, where $$\begin{array}{l} A_1 = F(F(X_1 \oplus Y_1) \oplus X_2 \oplus Y_2) ,\\ A_2 = F(F(X_1 \oplus Y_3) \oplus X_2 \oplus Y_4).\\ \end{array}$$

Similarly, $F_{3}(S) = A_{1} \mathbin\Vert A_{2} \mathbin\Vert A_{3}$, where $$\begin{array}{l} A_1 = F(F(F(X_1 \oplus Y_1) \oplus X_2 \oplus Y_2) \oplus X_3 \oplus Y_3),\\ A_2 = F(F(F(X_1 \oplus Y_4) \oplus X_2 \oplus Y_5) \oplus X_3 \oplus Y_6),\\ A_3 = F(F(F(X_1 \oplus Y_7) \oplus X_2 \oplus Y_8) \oplus X_3 \oplus Y_9),\\ \end{array}$$ and so on.

Question: if $k$ is greater than or equal to $2$, is $F_{k}(S)$ a PRF or PRP? What is its security parameter (the expected number of security bits)?


1 Answer 1


It is neither, because you're only talking about a fixed function—it's not even the right type of object to be a PRF or PRP. Keccak-f[1600] is not a pseudorandom permutation family itself; it is a single fixed permutation. A PRF or a PRP is a family of functions indexed by a key, such that a uniform distribution on keys induces an apparently uniform distribution on functions or permutations in some space.

  • $\begingroup$ Can I extract the first half of $F_{k}(S)$, output it as the hash of $S$ and expect the security parameter to be equal to $L/2$ (where $L$ is the length of the extracted hash)? $\endgroup$ Nov 5, 2017 at 7:36
  • $\begingroup$ The security parameter for what? What is your goal? $\endgroup$ Nov 5, 2017 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.