Трудный бит

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В криптографии, трудным битом для односторонней функции f называется функция h принимающая значение 0 или 1, при этом ее значение h(x) легко вычислить зная x, и трудно вычислить зная лишь f(x). Формально, полиномиально вычислимая функция h: D_n \xrightarrow[]{} \{0,1\} является трудным битом для функции f_n: D_n \xrightarrow[]{} D_n , если случайная величина h_n(\alpha_n) трудно вычислима по случайной величине f_n(\alpha_n), где (\alpha_n) — случайная величина равномерно распределенная на D_n.

Ссылки[править | править вики-текст]