Indifferentiability of Truncated Random Permutations

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/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/3), 2(m), 2(l)} queries, while it is publicly indifferentiable up to min{max{2(n+m/3), 2(n2)}, 2(l)} queries, where l is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when m + l << n. Our results significantly improve upon the previous bound of min{2(m/2), 2(l)} given by Dodis et al. (FSE 2009), allowing us to construct, for instance, an n/2-to-n/2 bit random function that makes a single call to an n-bit permutation, achieving n/2-bit security.