|
|
On search complexity of discrete logarithm
Václavek, Jan ; Hubáček, Pavel (vedoucí práce) ; Koucký, Michal (oponent)
Tato práce studuje problém diskrétního logaritmu v kontextu TFNP- složitostní třídy vyhledávacích problémů se syntakticky zaručenou existencí řešení pro všechny instance. Hlavním výsledkem práce je důkaz PPP-, resp. PWPP-úplnosti dvou vhodných variant diskrétního logaritmu, které jsme pojmenovali Index, resp. DLog. Příslušné redukce do- kazující PWPP-úplnost problému DLog navíc využívají dva nové PWPP-úplné problémy, které poskytují nový strukturální pohled na třídu PWPP. První z těchto problémů, Dove, je zmírnění PPP-úplného problému Pigeon. Dove je první PWPP-úplný problém, který není definovaný pomocí explicitně kompresní funkce. Druhý z těchto problémů, Claw, je totální vyhledávací problém zachycující výpočetní složitost prolomení claw-free per- mutací. V kontextu třídy TFNP odpovídá PWPP-úplnost problému Claw vztahu mezi hašovacími funkcemi rezistentními k nalézání kolizí a claw-free permutacemi popsanému v kryptografické literatuře. 1
|
host ::
RSS.