Say if I have a Pseudo Random Function PRF E: {0,1}^k x {0,1}^l -> {0,1}^l.

Hence it takes a key of length k and outputs text of length l bits. Is it possible to use this PRF E to construct another PRF H (with same inputs) that outputs t bits instead l bits, where t < l.

Also, is it possible to construct a different PRF G (using E) such that on inputs: (k-bit key and (l-n) bit plain text) G outputs t-bit string such that t = 2 x l

I can't seem to figure out how to construct H so that it outputs a string that has less bits than the input string's length. Because to my understanding, it is impossible to do this yet maintain the one-to-one function property.

As for G, I was thinking of taking the output from E and feed it back to E again as an input, then concatenate everything together. Basically the output will be E{input} + E{E{input}}. But is this Pseudo Random and secure?


1 Answer 1


I don't understand why you are talking about a 1-1 property; a pseudorandom function is not 1-1. As such, you can always just truncate in order to reduce the output size, and you can just truncate by taking the first $t$ bits that you want (you don't need to apply any other function). In order to extend, if $\ell$ is long enough to be the length of a seed in a pseudorandom generator, then you can apply the PRG to the output of the PRF to get a longer output.

If you really are talking about a 1-1 function, then you want to change the output length of a pseudorandom permutation. This is much more difficult, and can be done. A place to look is at the whole body of work on "format preserving encryption", which is problematic in name (it's deterministic so not secure encryption). However, what they really do is construct permutations over domains of arbitrary size.


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.