"Near" Pseudorandom Function

Question

I am searching literature on a more general notion of pseudorandom function where the range of the function is not the entire set of all binary strings of a given length, but rather a specified range dependent on the security parameter. Something like this, which I wrote up:

It seems that in some use cases, such a definition should be sufficient, but I'm also curious of any applications where this definition falls short over a PRF.

Answer 1

As suggested by @Maeher's comment, I would also think that restricting the range of a function does not fundamentally change what should be a definition of PRF. After all, PRFs are generally defined as a function from a certain set $\mathcal{X}$ to some other set $\mathcal{Y}$. And the PRF nature of a function $F: \mathcal{K} \times \mathcal{X} \mapsto \mathcal{Y}$ is captured by the behavior of the function(If using the framework of random systems) or via a game as you described.

However, it can be true that depending on the application, not all PRFs are “equal”. An example that come to mind is the randomized counter mode based on a PRF as described in section 5.4.2 of the "Boneh-Shoup" book. Indeed, let $\mathfrak{E} = (\mathrm{KGen, E, D})$ be an encryption scheme where the encryption function $E: \mathcal{K} \times \mathcal{M}\times\mathcal{R} \mapsto \mathcal{C}$ encrypts the message $m$ block-by-block computing the $i$th ciphertext block as $c_i = m_i \oplus F(k, r + i), r \xleftarrow{$} \mathcal{R}$. Then it can be shown that the CPA advantage of a $q$-query adversary $\mathcal{A}_q$ is upper bounded by: $$\frac{q^2\times\mathit{max\_msg\_len}}{|\mathcal{R}|}+\mathrm{Adv}^{\mathrm{cpa}}_{\mathcal{B}}(F).$$

From the above, it is clear that $|\mathcal{R}|$ should not be too small. Indeed, even if $F$ was a truly random function, for a small $|\mathcal{R}|$, the CPA advantage of $\mathcal{A}_q$ is still "too big".