Hlavní navigace

Názor k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od abyssal - Jak pisete, nahodne orakulum si musi ukladat jak...

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

  • 14. 11. 2006 19:41

    abyssal (neregistrovaný)
    Jak pisete, nahodne orakulum si musi ukladat jak povodnu spravu, tak vystup, ktory k nej priradilo (aby mohlo pri rovnakom dotaze odpovedat rovnako).

    Nahodne orakulum je teoreticky model (podobne ako lubovolne ine orakulum alebo trebars nedeterministicky Turingov stroj), tj. neriesi sa, kde si bude ukladat tu tabulku, podstatne su len jeho "zvonka viditelne" vlastnosti.

    Random oracle model ma hlavne v kryptografii velky vyznam, viz napr. http://en.wikipedia.org/wiki/Random_oracle_model. Napr. v mnohych dokazoch sily kryptosystemu sa predpoklada, ze hasovacie funkcie su nahodne orakula (co je v praxi splnit pomerne tazsie) a na zaklade vlastnosti nahodnych orakul sa odvodzuje sila kryptosystemu oproti urcitym utokom.

    Preto vlastnost, ze nova konstrukcia hasovacich funkcii ich robi vypocetne nerozlisitelnymi od nahodnych orakul je dost vyznamna pre bezpecnost schem pouzivajucich nove hasovacie funkcie zalozene na SNMAC konstrukcii.

    Dalsi teoreticky vyznam nahodnych orakul su relativizovane systemy v teorii zlozitosti, viz napr. Baker-Gill-Solovay (http://theory.csail.mit.edu/~madhu/ST05/scribe/lect02.pdf).