Hlavní navigace

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....

Článek je starý, nové názory již nelze přidávat.

  • 13. 11. 2006 11:56

    bez přezdívky
    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é.
  • 13. 11. 2006 12:54

    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"?
  • 13. 11. 2006 13:33

    bez přezdívky
    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
  • 13. 11. 2006 15:05

    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.
  • 13. 11. 2006 15:33

    bez přezdívky
    Sohlasím od začátku až do .....přílišnou váhu.
    Nicméně mohli bychom v tom ustat, protože, jak jsem uvedl výše, ten nový koncept nemá s tímhle nic společného.
  • 14. 11. 2006 13:59

    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.
  • 15. 11. 2006 23:39

    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.