Трудный бит

В криптографии, трудным предикатом для односторонней функции $f$ называется функция $h$, принимающая значение 0 или 1, при этом её значение $h(x)$ легко вычислить зная $x$, и трудно вычислить зная лишь $f(x)$. Формально, полиномиально вычислимая функция $h_n:D_n\underset{}{\overset{}{\to }}\{0,1\}$ является трудным предикатом для функции $f_n:D_n\underset{}{\overset{}{\to }}{D}_n$, если случайная величина $h_n({\alpha }_n)$ трудно вычислима по случайной величине $f_n({\alpha }_n)$, где ${\alpha }_n$ — случайная величина, равномерно распределённая на $D_n$.

См. также

• Криптографическая хеш-функция

Ссылки

• Гирш Э. А. «Сложность вычислений и основы криптографии». Курс лекций описывающий основы сложности вычислений и криптографии.
• Верещагин Н. К. Конспект лекций курса по криптографии.