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