Indifferentiability of Truncated Random Permutations

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.

Jooyoung Lee was supported by a National Research Foundation of Korea (NRF) grant funded by the Korean government (Ministry of Science and ICT), No. NRF-2017R1E1A1A03070248.

A Indistinguishability of \( \mathsf {TRP} \)

A hypergeometric random distribution $\mathsf {HG}_{N,M,q}$, parameterized by N, M, and q, is a probability distribution that describes the probability that exactly k elements are selected from a subset of M “good” elements when q elements are selected from the universe of N elements without replacement; this probability is precisely $\left( {\begin{array}{c}M\\ k\end{array}}\right) \left( {\begin{array}{c}N-M\\ n-k\end{array}}\right) /\left( {\begin{array}{c}N\\ n\end{array}}\right)$.

If a distinguisher makes no simulator query (namely, $q_S=0$) when it interacts with $\mathcal {S}_1$ in the regular indifferentiability setting, then $V_y$ would follow the hypergeometric distribution with $N=2^n$, $M=2^m$ and $q=i-1(=V)$. In this case, it is well known that

$$\begin{aligned} \mathbf {Ex}[V_y]&= \frac{V}{2^{n-m}}, \\ \mathbf {Var} [V_y]&= \frac{2^m(2^n-2^m)(2^n-V)V}{2^{2n}(2^n-1)}. \end{aligned}$$

Since

$$ \mathbf {Var} [V_y]=\mathbf {Ex}[V_y^2]-\mathbf {Ex}[V_y]^2,$$

and

$$\begin{aligned} \sum _{y\in \{0,1\} ^{n-m}} \mathbf {Var} [V_y]&\le 2^{n-m} \left( \frac{2^m(2^n-2^m)(2^n-V)V}{2^{2n}(2^n-1)} \right) \\&\le \frac{2^m(2^n-2^m)V}{2^{n+m}}\\&\le V \le q_F, \end{aligned}$$

we have

$$\begin{aligned} \mathbf {Ex} \left[ \sum _y \frac{(2^{n-m}V_y - V)^2}{2^{n-m}(2^n - V)^2} \right]&\le \frac{1}{2^{n+m-2}} \sum _{y\in \{0,1\} ^{n-m}} \left( \mathbf {Ex} \left[ V_y^2 \right] - \mathbf {Ex} \left[ V_y \right] ^2 \right) \\&\le \frac{q_F}{2^{n+m-2}}. \end{aligned}$$

Plugging this into (9), we obtain the indistinguishability bound of $\mathsf {TRP}$ as follows.

$$\mathbf{Adv }^{\mathsf {ind}}_{ \mathsf {TRP} }(\mathcal {A})\le \frac{q}{2^{\frac{n+m-1}{2}}},$$

for any distinguisher $\mathcal {A}$ making q queries.