Трудный бит

В криптографии, трудным предикатом для односторонней функции $f$ называется функция $h$, принимающая значение 0 или 1, при этом её значение $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}$.

См. также

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

Ссылки

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