Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Suppose we need a PRF whose output space is 255bit.
Then, what I can do with AES with 128-bit security is producing 2 AES blocks that are of 256-bit.
Then, I will remove the most significant bit of one block so that I have 255-bit output.
Is it secure if I remove the top-bit of the one block to make it 127-bit?
Is it secure if I remove the top-bit of the one block to make it 127-bit?
Yes truncating the output of a PRF produces a new PRF, which can be easily seen by a simple reduction. Assume you had an adversary that could break the truncated PRF, then you would forward all queries to the untruncated PRF and truncate the result (which is a perfect simulation) and output whatever your truncated adversary outputs. This constructed adversary wins whenever the truncated adversary wins.
AES with 128-bit security is producing 2 AES blocks
This is the tricky part. To compose two PRFs - and AES is assumed to be a PRP which can be used as a PRF if you do less than ~$2^{64}$ invocations - you'll need to ensure that for all possible queries the inputs to both calls are unique. Standard ways to achieve this are to use two different, independent keys for the sub-PRFs or to prepend a unique value, e.g. a single fixed bit which is always 0 for the left and always 1 for the right one.
