Трудный бит

В криптографии, трудным предикатом для односторонней функции $f$$f$ называется функция $h$$h$, принимающая значение 0 или 1, при этом её значение $h(x)$$h(x)$ легко вычислить зная $x$$x$, и трудно вычислить зная лишь $f(x)$$f(x)$. Формально, полиномиально вычислимая функция $h_n:D_n\underset{}{\overset{}{\to }}\{0,1\}$$h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}$ является трудным предикатом для функции $f_n:D_n\underset{}{\overset{}{\to }}{D}_n$$f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}$, если случайная величина $h_n({\mathrm{\alpha <!--\; \alpha \; -->}}_n)$$h_{n}(\alpha _{n})$ трудно вычислима по случайной величине $f_n({\mathrm{\alpha <!--\; \alpha \; -->}}_n)$$f_{n}(\alpha _{n})$, где ${\mathrm{\alpha <!--\; \alpha \; -->}}_n$$\alpha _{n}$ — случайная величина, равномерно распределённая на $D_n$$D_{n}$.

См. такжеПравить

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

СсылкиПравить

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