Vlákno názorů k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od anonym - Rozvinula se tu diskuse k P, NP apod....
-
Rozvinula se tu diskuse k P, NP apod. problémům. To je ok, jen na okraj poznamenávám, že důkazy, které jsem předložil, nejsou na těchto problémech založeny (kdyby byly, nezlobil bych se, takhle je to ale lepší). Na základě počtu operací, které má útočník k dispozici, vypočítávám jeho šanci na nalezení kolize a na nalezení vzoru. V rozšířeném článku jsou to hodnoty začínající Adv_..., které znamenají pravděpodobnost úspěchu. Věty 1 až 4 říkají, že tyhle pravděpodobnosti jsou mizivé, pokud se počty nutných operací nepohybují v řádu 2^n u vzoru a 2^(n/2) u kolize. To je OK, protože tyhle počty operací jsou platné pro náhodná orákula také. -
aaa (neregistrovaný)Nechapu. Co by jako mel "dukaz P/NP" dokazat? Pride mi, ze tu nikdo moc nerozumi tomu, co je to P a co je to NP. Problem nalezeni kolize k hasovaci funkci je resitelny v linearnim case protoze obor funkcnich hodnot je konecny. Tak nevim co by mel byt jako ten NP-uplny problem.
NP-uplnost je definovana nad !NEKONECNOU! mnozinout a problemu, ktery urcuje prislusnost do teto mnoziny. Tak napriklad, mnozina vsech grafu ktere lze obarvit 3mi barvami, je NP-uplna. (vsimnete si ze je nekonecna)
A i kdyby, to ze je nejaky problem NP-uplny nemusi znamenat ze je "neresitelny". NP-uplny problem ktery resi algoritmus se slozitosti O(1.000000001^n) je "resitelny" mnohem lepe nez kdejaky problem v P.
Co teda vlastne mame "P/NP dokazat"? -
Problém P/NP jsem v diskusi ani v článku nezmínil, nevyužívám je. Když už se ale do toho pustili jiní diskutující, proč se jich nezeptáte?
Já bych nebyl proti, kdyby se ukázalo, že pro konkrétní instanci hašovací funkce je problém nalezení její kolize NP-úplný problém. Nedokazuje to nic, dává to jen lepší reference, :-)
A to z důvodu, který sám uvádíte pomocí symbolu O(1.000000001^n).
Teorie složitosti rozděluje problémy do tříd. V každé třídě jsou problémy přibližně (řádově) stejně složité. Jejich složitost se uvádí jako funkce jejich rozměru, parametru. Třeba u hašovací funkce je parametrem n počet bitů hašovacího kódu. Zatím známe algoritmy, které umí nalézt vzor (resp.kolizi) k zadané haši se složitostí 2^n (resp.2^(n/2)). To je exponenciální složitost (nikoli lineární...). Proto tento problém nemůže patřit do třídy P, kde mají algoritmy složitost nejvýše polynomiální vzhledem k n, tj. třeba n^3 apod.
Jedna z nesložitějších tříd problémů je třída NP-úplných problémů. Nikdo se nebude zlobit, když jeho kryptografické konstrukce budou odpovídat problémům z této třídy. Na druhé straně se tomu nepřikládá takový praktický význam, právě z důvodu, který uvádíte. Přikládá se tomu ale význam teoretický.
Pokud vás zajímají definice, například v on-line příručce na str. 57 - 63, http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf -
aaa (neregistrovaný)aha, takze kdyz mluvime o prislusnosti hashovaci funkce do tridy NP, musime ji mit parametrizovanou pres delku vystupniho hashe. Takze H(x, n) da na vystup n bytovy hash. Chapu to dobre? U takove funkce by se uz o NP uplnosti dalo diskutovat. Nicmene, i zde bych vysledku neprikladal prilisnou vahu, protoze napriklad fakt, ze "H(x, 1000) = konstanta" nic nemeni na tom, ze H muze byt nekde treba v PSPACE.
-
Jano (neregistrovaný)Vazeny pane, zkuste treba wikipedii. Patrne byste se dozvedel, ze prislusnost problemu do trid neni podminovana nejakou nekonecnosti. Zlozitost algoritmu je definovana jako pocet kroku klasickeho turingova stroje v zavislosti na delce vstupu (pouze 0 a 1). Samozrejme v realu nikdo netvori pravidla pro zakladni turinguv stroj, protoze bylo ukazano, ze libovolny pocitac (ne zrovna kvantovy - mluvime o deterministickych algoritmech :) urychluje vypocet "jen malo". Taky vstup nemusi byt pocitany binarne.
V praxi tedy vezmeme problem (zadani transformace vstupu na vystup) a merime, kolik kroku algoritmus potrebuje na vypocteni teto transformace. Pokud existuje (deterministicky) algoritmus, kde vstup neni v mocniteli, je problem v P, jinak je v NP. Specialni tridou je NPC, kam patri algoritmy, kde staci najit P algoritmus pro jeden z nich a cela trida NP bude patrit do P. -
rocky (neregistrovaný)chtelo by to vic opatrnosti a premysleni, kolego... aaa mluvil o nekonecne tride problemu (spis instanci konkretniho problemu, ne?). Kdby byla konecna, tak se da i s resenim v klidu zakodovat do prechodove funkce turingova stroje, cili razem tu je ten deterministiciky algoritmus.
