Paper 2022/918

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

Wonseok Choi, Korea Advanced Institute of Science and Technology
Jooyoung Lee, Korea Advanced Institute of Science and Technology
Yeongmin Lee, Korea Advanced Institute of Science and Technology
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.

Metadata
Available format(s)
PDF
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
2022-07-14: received
See all versions
Short URL
https://ia.cr/2022/918
License
Creative Commons Attribution
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.