International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Indifferentiability of Truncated Random Permutations

Wonseok Choi
Byeonghak Lee
Jooyoung Lee
DOI: 10.1007/978-3-030-34578-5_7
Search ePrint
Search Google
Abstract: 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.
  title={Indifferentiability of Truncated Random Permutations},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  author={Wonseok Choi and Byeonghak Lee and Jooyoung Lee},