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. 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+nc)$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 TBCbased MAC finalization functions and CTRtype encryption modes with stronger provable security compared to existing schemes.
Metadata
 Available format(s)
 Category
 Secretkey 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
 20220715: revised
 20220714: received
 See all versions
 Short URL
 https://ia.cr/2022/918
 License

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} }