1
$\begingroup$

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:

defn

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.

$\endgroup$
2
  • 1
    $\begingroup$ What you have there is not a weaker definition. It's a generalization. $\endgroup$
    – Maeher
    Sep 15, 2022 at 8:32
  • $\begingroup$ Agreed, I've edited my question to reflect this. It is a generalisation. But what might hold in the special case of a PRF, might not hold in this general case, which I am curious about. $\endgroup$
    – Lev
    Sep 15, 2022 at 22:25

1 Answer 1

1
$\begingroup$

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".

$\endgroup$

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.