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)