ハードコア述語
任意の一方向性置換から暗号学的擬似乱数を構成することがハードコア述語によって可能となる。もし b が f のハードコア述語ならば、s をランダムな種とし、
{ b ( f n ( s ) ) } n {\displaystyle \left\{b(f^{n}(s))\right\}_{n}}
が疑似乱数になる。この手法を用いて構成された擬似乱数発生器として、Blum-Blum-Shubが挙げられる。Blum-Blum-Shub擬似乱数発生器では、 f ( x ) = x 2 mod N {\displaystyle f(x)=x^{2}{\bmod {N}}} 、 b(x)=xの最下位ビットを用いている。
また、落とし戸付き一方向性置換のハードコア述語は、IND-CPA安全な公開鍵暗号方式を構成することにも使える。落とし戸付き一方向性置換を f、ハードコア述語を b とする。平文を m ∈ { 0 , 1 } {\displaystyle m\in \{0,1\}} に対して、乱数 r を用いて
E ( m ; r ) = ( f ( r ) , b ( r ) ⊕ m ) {\displaystyle E(m;r)=(f(r),b(r)\oplus m)}
という暗号方式がそれである。
ある述語 b がハードコア述語であることを示す帰着は、符号のリスト復号アルゴリズムになっていることも多い。例えば、ゴールドライヒとレビンの帰着はアダマール符号 (または特殊なリード・マラー符号)のリスト復号アルゴリズムになっている。