В криптографии , трудным предикатом для односторонней функции ${\displaystyle f}$ называется функция ${\displaystyle h}$ , принимающая значение 0 или 1, при этом её значение ${\displaystyle h(x)}$ легко вычислить зная ${\displaystyle x}$ , и трудно вычислить зная лишь ${\displaystyle f(x)}$ . Формально, полиномиально вычислимая функция ${\displaystyle h_{n}:D_{n}{\xrightarrow[{}]{}}\{0,1\}}$ является трудным предикатом для функции ${\displaystyle f_{n}:D_{n}{\xrightarrow[{}]{}}D_{n}}$ , если случайная величина ${\displaystyle h_{n}(\alpha _{n})}$ трудно вычислима по случайной величине ${\displaystyle f_{n}(\alpha _{n})}$ , где ${\displaystyle \alpha _{n}}$ — случайная величина, равномерно распределённая на ${\displaystyle D_{n}}$ .

См. также

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

Ссылки

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