Список обозначений

Предикат трудный

hard-core predicate

Полиномиально вычислимый предикат $b\colon\{0,1\}^*\to\{0,1\}$ называется трудным для функции $f\colon\{0,1\}^*\to\{0,1\}^*$, если он является трудной функцией для $f$. Известно, что предикат труден для функции $f$ тогда и только тогда, когда он полиномиально вычислим и трудно аппроксимируем по $f$ (см. функция трудно аппроксимируемая).

Если не требовать от функции $f$ никаких свойств, то трудные предикаты для $f$ могут быть построены легко. Например, если $f(x)=x_{[2,\dots,\lvert{x}\rvert]}$ и $b(x)=x_{[1]}$ для всех непустых строк $x\in\{0,1\}^*$, то $b$ — трудный предикат для функции $f$. Причина этого факта состоит в том, что $f(x)$ не содержит никакой информации о $b(x)$. В то же время если функция $f\colon\{0,1\}^*\to\{0,1\}^*$ полиномиально вычислима и инъективна, то из существования трудного предиката для $f$ вытекает односторонность $f$ (см. [1]).

Частный случай теоремы Гольдрайха”– Левина (см. функция трудная), относящийся к трудным предикатам, выглядит следующим образом.

Теорема 1
Пусть $f$ — произвольная односторонняя функция. Тогда предикат $b$, определенный равенством \[ b(x,y)=\bigoplus_{i=1}^nx_{[i]}y_{[i]}\quad (x,y\in\{0,1\}^n,\, n\in\mathbb N), \] является трудным для функции $(x,y)\mapsto(f(x),y)$ ($x,y\in\{0,1\}^n$, $n\in\mathbb N$).

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна