Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od anonym - Lepší bych nedokázal odpovědět. Tak jenom připojím kratičký...

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

  • 18. 11. 2006 11:34

    bez přezdívky
    Lepší bych nedokázal odpovědět. Tak jenom připojím kratičký důkaz.

    Skutečně, jakákoliv konkrétní (nejen hašovací) funkce f nemůže být náhodným orákulem. Stačí dát dvěma lidem ten funkční předpis f a obou dvou se nezávisle ptát na výsledek hašovací hodnoty na konkrétní vstup. Jestliže první z nich vlastní náhodné orákulum, nemůže ten druhý se stoprocentní jistotou předvídat všechny hodnoty, které ten první odpoví. První by je měl totiž vybírat náhodně. Je tu zanedbatelná pravděpodobnost, že ten druhý se vždycky náhodně trefí do odpovědi prvního. Ta pravděpodobnost je menší než jakékoliv malé číslo, pokud orákulum nemá limitovánu délku zprávy.