## CryptoDB

### Paper: Indifferentiability of Truncated Random Permutations

Authors: Wonseok Choi Byeonghak Lee Jooyoung Lee DOI: 10.1007/978-3-030-34578-5_7 Search ePrint Search Google One of natural ways of constructing a pseudorandom function from a pseudorandom permutation is to simply truncate the output of the permutation. When n is the permutation size and m is the number of truncated bits, the resulting construction is known to be indistinguishable from a random function up to $2^{{n+m}\over 2}$ queries, which is tight.In this paper, we study the indifferentiability of a truncated random permutation where a fixed prefix is prepended to the inputs. We prove that this construction is (regularly) indifferentiable from a public random function up to $\min \{2^{{n+m}\over 3}, 2^{m}, 2^\ell \}$ queries, while it is publicly indifferentiable up to $\min \{ \max \{2^{{n+m}\over 3}, 2^{n \over 2}\}, 2^\ell \}$ queries, where $\ell$ is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when $m+\ell \ll n$.Our results significantly improve upon the previous bound of $\min \{ 2^{m \over 2}, 2^\ell \}$ given by Dodis et al. (FSE 2009), allowing us to construct, for instance, an $\frac{n}{2}$-to-$\frac{n}{2}$ bit random function that makes a single call to an n-bit permutation, achieving $\frac{n}{2}$-bit security.
##### BibTeX
@article{asiacrypt-2019-30014,
title={Indifferentiability of Truncated Random Permutations},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11921},
pages={175-195},
doi={10.1007/978-3-030-34578-5_7},
author={Wonseok Choi and Byeonghak Lee and Jooyoung Lee},
year=2019
}