Building PRFs from TPRPs: Beyond the Block and the Tweak Length Bounds

Abstract

A secure n-bit tweakable block cipher (TBC) using t-bit tweaks can be modeled as a tweakable uniform random permutation, where each tweak defines an independent random n-bit permutation. When an input to this tweakable permutation is fixed, it can be viewed as a perfectly secure t-bit random function. On the other hand, when a tweak is fixed, it can be viewed as a perfectly secure n-bit random permutation, and it is well known that the sum of two random permutations is pseudorandom up to 2n queries. A natural question is whether one can construct a pseudorandom function (PRF) beyond the block and the tweak length bounds using a small number of calls to the underlying tweakable permutations. A straightforward way of constructing a PRF from tweakable permutations is to xor the outputs from two tweakable permutations with c bits of the input to each permutation fixed. Using the multi-user security of the sum of two permutations, one can prove that the (t + n − c)-to-n bit PRF is secure up to 2n+c queries. In this paper, we propose a family of PRF constructions based on tweakable permutations, dubbed XoTPc, achieving stronger security than the straightforward construction. XoTPc is parameterized by c, giving a (t + n − c)-to-n bit PRF. When t < 3n and c = t/3 , XoTPt/3 becomes an (n + 2t/3 )-to-n bit pseudorandom function, which is secure up to 2n+2t/3 queries. It provides security beyond the block and the tweak length bounds, making two calls to the underlying tweakable permutations. In order to prove the security of XoTPc, we extend Mirror theory to q ≫ 2n, where q is the number of equations. From a practical point of view, our construction can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.

Keywords

• Mirror theory
• pseudorandom function
• tweakable block cipher
• sum of permutations