Prevodom na NP-uplne to nie je, trik je v relativizacii s nahodnymi orakulami. Ide o vypocetnu nerozlisitelnost hasovacej funkcie od nahodneho orakula, tj. pravdepodobnost lubovolneho programu rozlisit hashovaciu funkciu od nahodneho orakula je zanedbatelna (nieco ako e-n)
Zlozitost (a pravdepodobnost najdenia kolizie/preimage) sa pocita oproti poctu dotazov na orakula, v pripade orakul (ciernych skriniek) nic ine neostava.
Myslim, ze paper hovori o konstrukcii mnoziny (rodiny) hasovacich funkcii, ktore sa tak spravaju a nie o jednej konkretnej instancii hasovacej funkcie, co je celkom rozdiel - kod konkretnej instancie uz moze clovek analyzovat (nie je obmedzeny len na dotazovanie orakul).
V paperi Coron et al., kde je dokaz ze tie hash fn. su limitne nerozlisitelne od nahodnych orakul, sa predpoklada, ze kompresna funkcia f je nahodne orakulum. Podobne navrh SNMAC/NMAC/... predpoklada, ze kompresna funkcia je nahodne zvolena blokova sifra (tj. opat nahodne orakulum).
V praxi je ale nutne mat nejaku konkretnu instanciu hasovacej funkcie, tam predpoklad nahodnej blokovej sifry splneny asi nie je - je tam jedna konkretna (AFAIK o ziadnej konkretnej blokovej sifre nebolo dokazane, ze by bola nahodnym orakulom, ale nie som si 100% isty). Predpokladane SBC (special block cipher) ale maju niektore silne vlastnosti (homogenita, odolnost proti diferencialnym a linearnym utokom).
Zaver: nova schema konstrukcie - nova rodina hashovacich funkcii - je preukazatelne odolna proti "starym neduhom" ako Jouxov extension attack apod. a je vypocetne nerozlisitelna od nahodneho orakula. Co je po "nedavnej deziluzii" z nalomenia mnohych hashovacich funkcii slusny uspech.
(nestudoval som to zatial podrobne, spominane papery - Klima, Coron et. al - len som zbezne presiel, radsej uz idem spat jak pozeram na cas)
Veta 1 hovorí o _náhodnom_ výbere blokovej šifry E z BC(K,n). No ale odkiaľ takúto šifru zoberieme? Všetky, ktoré máme (a budeme mať), majú nejaký konkrétny predpis. Vadí nám to? (tá istá otázka sa vzťahuje k náhodnému orákulu vo Vete 3).
"Trocha" to vadi. Trik je v tom, ze ziadna konkretna funkcia (blokova sifra) nie je nahodnym orakulom, tym padom nie je mozne nic podobne dokazat, ak sa dosadi konkretna blokova sifra. Tie vety platia pre nahodne vybranu funkciu z mnoziny vsetkych hasovacich funkcii s HMAC/NMAC konstrukciou, teda vypovedaju o sile konstrukcie, ale nehovoria moc o konkretnej instancii. Fakt je, ze sa s tym moc neda robit, akurat mozno zabezpecit blokovu sifru proti niektorym utokom (v zmysle ako tu o tom debatujete). Na druhej strane stare konstrukcie (ako iteracne hasovacie funkcie) nemali ani tieto vlastnosti.