Трудный бит

В криптографии, трудным битом для односторонней функции $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$.

Ссылки

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

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.