В криптографии, трудным предикатом для односторонней функции называется функция , принимающая значение 0 или 1, при этом её значение легко вычислить зная , и трудно вычислить зная лишь . Формально, полиномиально вычислимая функция является трудным предикатом для функции , если случайная величина трудно вычислима по случайной величине , где — случайная величина, равномерно распределённая на .
См. также Криптографическая хеш-функция
Ссылки Гирш Э. А. «Сложность вычислений и основы криптографии». Курс лекций описывающий основы сложности вычислений и криптографии. Верещагин Н. К. Конспект лекций курса по криптографии.
Категория:Криптографические хеш-функции