Paper 2022/918

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^n$ 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 $\mathsf{XoTP}_c$, achieving stronger security than the straightforward construction. $\mathsf{XoTP}_c$ is parameterized by $c$, giving a $(t+n-c)$-to-$n$ bit PRF. When $t<3n$ and $c=\frac{t}{3}$, $\mathsf{XoTP}_{\frac{t}{3}}$ becomes an $(n+\frac{2t}{3})$-to-$n$ bit pseudorandom function, which is secure up to $2^{n+\frac{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 $\mathsf{XoTP}_c$, we extend Mirror theory to $q \gg 2^n$, 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.