ハードコア述語の応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/29 04:17 UTC 版)
「ハードコア述語」の記事における「ハードコア述語の応用」の解説
任意の一方向性置換から暗号学的擬似乱数を構成することがハードコア述語によって可能となる。もし 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 がハードコア述語であることを示す帰着は、符号のリスト復号アルゴリズムになっていることも多い。例えば、ゴールドライヒとレビンの帰着はアダマール符号 (または特殊なリード・マラー符号）のリスト復号アルゴリズムになっている。
※この「ハードコア述語の応用」の解説は、「ハードコア述語」の解説の一部です。
「ハードコア述語の応用」を含む「ハードコア述語」の記事については、「ハードコア述語」の概要を参照ください。
- ハードコア述語の応用のページへのリンク
