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 2ⁿ 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 2^n+c queries.
In this paper, we propose a family of PRF constructions based on tweakable permutations, dubbed XoTP_c, achieving stronger security than the straightforward construction. XoTP_c is parameterized by c, giving a (t + n − c)-to-n bit PRF. When t < 3n and c = t/3 , XoTP_t/3 becomes an (n + 2t/3 )-to-n bit pseudorandom function, which is secure up to 2ⁿ+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 XoTP_c, we extend Mirror theory to q ≫ 2ⁿ, 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.