# Dependence of a Pseudorandom Function's Security on its Input/Output Spaces

Let $$n$$ be a security parameter and $$F:\{0,1\}^{\ell_{key}(n)} \times \{0,1\}^{\ell_{in}(n)} \rightarrow \{0,1\}^{\ell_{out}(n)}$$ be a keyed function which forms a family of Pseudorandom Functions (PRF) as Defined in “Introduction to Modern Cryptography” (2nd edition) by Lindell & Katz (Definition 3.25). I am interested in the case that the function is not length-preserving.

1. In particular, what if $$\ell_{in}(n)$$ and $$\ell_{out}(n)$$ are fixed based on the problem at hand, e.g., $$\ell_{in}(n) = 64$$ and $$\ell_{out}(n) = 32$$? The $$\ell_{key}(n)$$ can be anything depending on the required level of security. I am wondering how such restrictions on the input/output spaces $$\ell_{in}(n)$$ and $$\ell_{out}(n)$$ would affect the security of the PRF?
2. If the above results in lack of security: Is it OK to enforce, say $$\ell_{out}(n) \geq 32$$, and then just take 32-bits by somehow reducing the output? Also, assuming that all inputs are 64-bit, what techniques can be used to expand the input size?
3. In an extreme case, is it OK to have $$\ell_{out}(n) = 1$$?

Also, I'd be thankful for any suggestions on references which argue such details about the security analysis of PRFs.

• References: chap. 7 of Katz-Lindell, and then Goldreich. (Chap. 7 of KL only discusses the length-preserving case, but is a good warm-up for Goldreich.) – fkraiem Jul 24 at 5:24
• @fkraiem can you please let me know which part of the Goldreich book you have in mind? Section 3.6 (Vol. 1) only discusses the length-preserving case, and Appendix C.3 (Vol. 2) provides a proposition for obtaining a PRF with variable input length. Neither of them mentions anything about my question above. – Nima Jul 24 at 17:58
• "Section 3.6 (Vol. 1) only discusses the length-preserving case" No, it does not (see Sec. 3.6.4). – fkraiem Jul 24 at 22:45