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.

Respuesta :

Solution :

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

f is a permutation on [tex]$Z_{10}$[/tex] ,  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  [tex]$f: Z_{10} \rightarrow Z_{10}$[/tex]  

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

Now we want the total number of permutation functioning :

[tex]$f: Z_{10} \rightarrow Z_{10}$[/tex]   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  [tex]$f: Z_{10} \rightarrow Z_{10}$[/tex]  , f(0)=0 and f(1)=1 are 8!

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

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

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

[tex]$\frac{8!}{10!} = \frac{8!}{10 \times 9\times 8!} =\frac{1}{10 \times 9}=\frac{1}{90}$[/tex]

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