Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.