Tvrdý kousek

V kryptografii je pevným predikátem pro jednosměrnou funkci funkce , která nabývá hodnoty 0 nebo 1, přičemž její hodnotu lze snadno vypočítat s vědomím a obtížně vypočítat pouze s vědomím . Formálně je polynomiálně vyčíslitelná funkce tvrdým predikátem pro funkci , pokud je náhodná proměnná těžko vypočítatelná z náhodné proměnné , kde je náhodná proměnná rovnoměrně rozdělena na . $F$ $h$ $h(x)$ $X$ $f(x)$ $h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}$ $f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}$ $h_{n}(\alpha _{n})$ $f_{n}(\alpha _{n})$ $\alpha_{n}$ $D_{n}$

Viz také

Kryptografická hašovací funkce

Odkazy

Girsh EA " Výpočetní složitost a základy kryptografie " . Kurz přednášek popisující základy výpočetní složitosti a kryptografie.
Vereshchagin N.K. Poznámky k přednáškám z kurzu kryptografie.