Question

You are given a black box f : Z10 → Z10 that contains either a random permutation or a random function. Your distinguisher is allowed to invoke f twice. What is the best advantage you can achieve? Express your answer as a reduced fraction without any spaces (eg, 1/3 and not 12/36), or as 0 or 1 if appropriate.

Answer 1

Solution :

The function :    $f: Z_{10} \rightarrow Z_{10}$   be a random permutation.

f is a permutation on $Z_{10}$ ,  i.e. f is permutation 10.

Now we know that the total number of distinct permutation on to symbolize 10!.

Each of these 10! permutation to a permutation function  $f: Z_{10} \rightarrow Z_{10}$  

Therefore, total number of permutation functions  $f: Z_{10} \rightarrow Z_{10}$   are 10!.

Now we want the total number of permutation functioning :

$f: Z_{10} \rightarrow Z_{10}$   such that  f(0) = 0 and f(1)= 1

Now we notice that when f(0)=0 and f(1)=1, then two symbol '0' and '1 are fixed under permutation f.

So essentially when f(0) = 0 and f(1) = 1, f becomes permutation on 8 symbol.

Total number of permutation functioning  $f: Z_{10} \rightarrow Z_{10}$  , f(0)=0 and f(1)=1 are 8!

Now we want the probability that a random permutation  $f: Z_{10} \rightarrow Z_{10}$   satisfies f(0) = 0 and f(1) = 1.

The number of permutation function  $f: Z_{10} \rightarrow Z_{10}$  , i.e.

The probability that a random permutation  $f: Z_{10} \rightarrow Z_{10}$   satisfies f(0) = 0 and f(1) = 1 is

$\frac{8!}{10!} = \frac{8!}{10 \times 9\times 8!} =\frac{1}{10 \times 9}=\frac{1}{90}$

Therefore, the probability that a random permutation  $f: Z_{10} \rightarrow Z_{10}$   satisfies f(0)= 0 and f(1)=1 is  $\frac{1}{90}$