Let $N\in\mathbb{N}$ and $G$ the group $\mathbb{Z}/n\mathbb{Z}$.
Let $q< N$ and:
- $a_1, ..., a_q$ pairwise distinct elements of $G$
- $b_1, ..., b_q$ pairwise distinct elements of $G$
- $x_1, ..., x_q$ pairwise distinct elements of $G$
- $y_1, ..., y_q$ pairwise distinct elements of $G$.
Let $P$ be a random permutation of $G$ verifying $P(a_i)=b_i, \forall i\leq q$.
Let $Q$ be a random permutation of $G$.
Let $k_0, k_1$ be random elements of $G$.
Let $E$ denote the function $E(x)=P(x + k_0)+k_1$
I want to prove that $$\Pr[E(x_q)=y_q|E(x_\ell )=y_\ell, \forall \ell < q]$$ is greater than $$\left(1-\frac{2q}{N}\right)\Pr[Q(x_q)=y_q|Q(x_\ell)=y_\ell, \forall \ell < q]$$
The first probability is over the randomness of $k_0, k_1$ and $P$. The second probability is over the randomness of $Q$.
If we hadn't equations $P(a_i)=b_i$ on $P$, then the two probabilites would be equal. So this result would show that, adding conditions to $P$ doesn't change too much the distribution of $(E(x_1), ..., E(x_q))$, it should still be close of the uniform distribution.
Thank you
