1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ AES is supposed to be a PRP. $\endgroup$ – kelalaka Mar 27 at 13:44
  • $\begingroup$ What is the common practice to implement PRF of arbitrary length output? $\endgroup$ – user9414424 Mar 27 at 13:45
  • $\begingroup$ Use a good Cryptographic hash function? $\endgroup$ – kelalaka Mar 27 at 13:46
  • $\begingroup$ @kelalaka a PRP can als be used as a PRF (that's the infamous "PRP-PRF-Switching Lemma") $\endgroup$ – SEJPM Mar 27 at 13:53
  • $\begingroup$ does my implementation work? $\endgroup$ – user9414424 Mar 27 at 13:56
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ The success of the adversary in the truncate game isn't related to the size of the output and the size of the truncation? $\endgroup$ – kelalaka Mar 27 at 14:45
  • $\begingroup$ @kelalaka hmm, I think $\mathbf{Adv}^{\text{PRF}}_{F}\geq \mathbf{Adv}^{\text{PRF}}_{F'}$ (with $F'$ being the truncated PRF) holds (because the truncated adversary naturally has a lower chance to win (?)) $\endgroup$ – SEJPM Mar 27 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.