Трудный бит
В криптографии, трудным предикатом для односторонней функции называется функция , принимающая значение 0 или 1, при этом её значение легко вычислить зная , и трудно вычислить зная лишь . Формально, полиномиально вычислимая функция является трудным предикатом для функции , если случайная величина трудно вычислима по случайной величине , где — случайная величина, равномерно распределённая на .
См. также
Ссылки
- Гирш Э. А. «Сложность вычислений и основы криптографии». Курс лекций описывающий основы сложности вычислений и криптографии.
- Верещагин Н. К. Конспект лекций курса по криптографии.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.