Welcome to the resource topic for 2022/918
Title:
Building PRFs from TPRPs: Beyond the Block and the Tweak Length Bounds
Authors: Wonseok Choi, Jooyoung Lee, and Yeongmin Lee
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.
ePrint: https://eprint.iacr.org/2022/918
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .