### 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. As a positive answer to this question, we propose two PRF constructions based on tweakable permutations, dubbed $\mathsf{XoTP1}_c$ and $\mathsf{XoTP2}_c$, respectively. Both constructions are parameterized by $c$, giving a $(t+n-c)$-to-$n$ bit PRF. When $t<2n$, $\mathsf{XoTP1}_{\frac{t}{2}}$ becomes an $(n+\frac{t}{2})$-to-$n$ bit pseudorandom function, which is secure up to $2^{n+\frac{t}{2}}$ queries. $\mathsf{XoTP2}_{\frac{t}{3}}$ is even better, giving an $(n+\frac{2t}{3})$-to-$n$ bit pseudorandom function, which is secure up to $2^{n+\frac{2t}{3}}$ queries, when $t<3n$. These PRFs provide 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{XoTP1}$ and $\mathsf{XoTP2}$, we firstly extend Mirror theory to $q \gg 2^n$, where $q$ is the number of equations. From a practical point of view, our constructions can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Mirror theory pseudorandom function tweakable block cipher sum of permutations
Contact author(s)
krwioh @ kaist ac kr
hicalf @ kaist ac kr
dudals4780 @ kaist ac kr
History
2022-07-15: revised
See all versions
Short URL
https://ia.cr/2022/918

CC BY

BibTeX

@misc{cryptoeprint:2022/918,
author = {Wonseok Choi and Jooyoung Lee and Yeongmin Lee},
title = {Building PRFs from TPRPs: Beyond the Block and the Tweak Length Bounds},
howpublished = {Cryptology ePrint Archive, Paper 2022/918},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/918}},
url = {https://eprint.iacr.org/2022/918}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.