ハードコア述語
一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ (en:Oded Goldreich) とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。 今、f を一方向性関数だとする。関数 g を
g ( x , r ) := f ( x ) ∘ r {\displaystyle g(x,r):=f(x)\circ r}
と定義する( ∘ {\displaystyle \circ } は連結を表す)。ただし、r の長さは x の長さと同じであるとする。xj を x の j ビットとし、rj を r の j ビットとする。 このとき、
b ( x , r ) = ⨁ j x j r j {\displaystyle b(x,r)=\bigoplus _{j}x_{j}r_{j}}