Matematické Fórum

tmr · 04. 12. 2009 11:17

(1) Uvazujme nahodnou permutaci $\pi:\,\{0,1\}^n \to \{0,1\}^n$ . Ukazte, ze $f(x)=\pi(x)\oplus x$ neni nahodna funkce.

(2) Uvazujme pseudonahodnou permutaci $\epsilon_K(x):\,\{0,1\}^n \to \{0,1\}^n$ . Ukazte, ze $E_K(x)=\epsilon_K(x)\oplus x$ je pseudonahodna funkce. Za jakych podminek tato funkce neni efektivne odlisitelna od funkce nahodne?
------

Bohuzel nemam k dispozici zadne presne definice pouzivanych pojmu. Myslim ale, ze nahodna permutace je i nahodnou funkci ( $RP\subset RF$ ). Nahodnou funkci $f$ chapu jako uniformni selekci z oboru hodnot, tj. prst. kazdeho vystupu je $1/|Rng(f)|$ . Tedy pro $n=1$ mame jen $\{0,1\}$ , tj. $P[f(x)=0] = P[f(x)=1] = 1/2$ .
XOR tuto pravdepodobnost IMHO zachovava, jen ji jeste trosku zprehazi ("fixni" permutace).
Nahodna permutace slozena s fixni permutaci je preci porad nahodna, ne?

Kdyz to rozeberu na pripady, tak to vypada zhruba takhle:
(a) $x = 1 \, \& \, \pi (x) = 1$ , pak $f(x)=0$
(b) $x = 1 \, \& \, \pi (x) = 0$ , pak $f(x)=1$
(c) $x = 0 \, \& \, \pi (x) = 0$ , pak $f(x)=0$
(d) $x = 0 \, \& \, \pi (x) = 1$ , pak $f(x)=1$

...tedy mame porad oba vystupy stejne pravdepodobne, coz je spor s tim, ze by to nemela byt nahodna funkce.

Moje otazky tedy zni nasledovne:
(1) kde je v moji uvaze nad problemem (1) chyba?
(2) jak by se resil ten druhy priklad? Pseudonahodnost chapu, ale presnou definici jsem nikde nenasel, a tudiz ani nejsem schopny podat jakykoliv uspokojujici dukaz, popr. nejak formulovat onu "efektivni odlisitelnost."

Predem diky za jakekoliv hinty ;-)

Kondr · 05. 12. 2009 00:46

Problém vidím v chybějících definicích. Pro n=1 je $\pi$ s pravděpodobností 1/2 rovno identitě (pak je f nulová) a s prvděpodobností 1/2 rovno cyklu (01) (pak je f(x)=1). Nikdy tak nedostaneme funkce f(x)=x ani f(x)=1-x, f(x) proto není náhodná funkce (aspoň ne v tom smyslu, že to může být každá funkce se stejnou pravděpodobností).

tmr · 13. 12. 2009 14:08

Nevim, jestli jsem tak nechapavy, ale ta diskuse moznych situaci pro n=1 mi prijde stejna, jako to moje (a),(b),(c),(d). Zaver mame ale oba jiny.

Jaktoze nedostanu f(x)=x ani f(x)=1-x? Vzdyt to jsou prece prave pripady (a),(c), resp. (b),(d), nebo se pletu?

Kondr · 13. 12. 2009 14:49

↑ tmr:Jde o to, že to nejde rozbít na případy (a),(b),(c),(d). My si vybereme permutaci a protivník se nám snaží dokázat, že $f(x)=\pi(x)\oplus x$ není náhodná. Protivník se nás zeptá na f(0) a když mu to řekneme, ví, kolik je f(1). Tím dokázal, že nejde o náhodnou funkci.

tmr · 13. 12. 2009 23:52

To je fakt ;-) Dik za pomoc.

Matematické Fórum

#1 04. 12. 2009 11:17

Nahodne a pseudonahodne funkce a permutace

#2 05. 12. 2009 00:46

Re: Nahodne a pseudonahodne funkce a permutace

#3 13. 12. 2009 14:08

Re: Nahodne a pseudonahodne funkce a permutace

#4 13. 12. 2009 14:49

Re: Nahodne a pseudonahodne funkce a permutace

#5 13. 12. 2009 23:52

Re: Nahodne a pseudonahodne funkce a permutace