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.

  • $\begingroup$ 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.) $\endgroup$ – fkraiem Jul 24 '19 at 5:24
  • $\begingroup$ @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. $\endgroup$ – Nima Jul 24 '19 at 17:58
  • $\begingroup$ "Section 3.6 (Vol. 1) only discusses the length-preserving case" No, it does not (see Sec. 3.6.4). $\endgroup$ – fkraiem Jul 24 '19 at 22:45

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.