WikiSort.ru - Не сортированное

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

См. также

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

Ссылки

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

Это заготовка статьи по криптографии. Вы можете помочь проекту, дополнив её.