ハードコア述語
暗号理論において、一方向性関数 f に関するハードコア述語(ハードコアじゅつご、Hard-core predicate)とは、x からは簡単に計算出来るが f(x) から計算するのは難しい述語 b のことである。より正確には、x をランダムに選んだとき f(x) から b(x) を 1/2 以上の有意な確率で計算できる確率的多項式時間アルゴリズムが存在しないとき、b を f のハードコア述語と呼ぶ。ハードコア関数も同様にして定義される(ただし弱いものと強いものがある)。
ハードコア述語は、関数 f を逆算するときに「一番難しいところ」を捉えた概念である。
一方向性関数は逆算するのが難しい。しかし像 f(x) から原像 x の部分的な情報 c を得ることについては何も言及していない。例えば、RSA関数は一方向性関数だと予想されているが、原像のヤコビ記号は像から簡単に求められる。
厳密な定義
述語 [math]b : \{0,1\}^* \to \{0,1\}[/math] が以下を満たすとき、関数 f のハードコア述語であるという:
- b は多項式時間で計算可能。すなわちある多項式時間アルゴリズム B が存在して, [math]B(x)=b(x)[/math]。
- 任意の多項式サイズ回路族 [math]\{C_n\}[/math]について, ある無視可能函数 ε が存在し,
[math]Pr[x \gets_R \{0,1\}^n : C_n(f(x)) = b(x)] \lt \frac{1}{2}+\epsilon(n)[/math]
一般的なハードコア述語
一対一関数がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ (en:Oded Goldreich) とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。 今、f を一方向性関数だとする。関数 g を
[math]g(x,r) := f(x) \circ r[/math]
と定義する([math]\circ[/math]は連結を表す)。ただし、r の長さは x の長さと同じであるとする。xj を x の j ビットとし、rj を r の j ビットとする。 このとき、
[math]b(x,r) = \bigoplus_j x_j r_j[/math]
は g のハードコア述語である。ここで、[math]\langle\cdot,\cdot\rangle[/math] をベクトル空間 [math](\Z/2\Z)^n[/math] 上の標準的な内積とすると、[math]b(x,r)=\langle x,r\rangle[/math]である。f(x) から g(x, r) を 1/2 以上に無視できない確率で計算できるアルゴリズムが存在するならば、x そのものを効率よく求めることができる。同様の構成により、[math]\log(|x|)[/math] ビットの出力を持つハードコア関数を構成することができる。
特定の関数に対するハードコア述語
入力 x の特定のビットがハードコア述語になる場合もある。たとえば、最下位ビットはRSA関数についてハードコアである。NaslundとHastadとは下位のビットがRSA関数についてのハードコア述語になることを示している(上位のビットについても拡張されたハードコア述語になる)。より強い主張として、入力の下半分を返す関数はRSA関数についてのハードコア関数だと予想されている[1]。これは下半分の各ビットがハードコア述語であるということよりは強い。なぜならば f(x) は x の各々のビットについての情報を漏らすことなく、特定のビット間の相関については情報を漏らしうるからである。
ハードコア述語の応用
任意の一方向性置換から暗号学的擬似乱数を構成することがハードコア述語によって可能となる。もし b が f のハードコア述語ならば、s をランダムな種とし、
[math]\left\{b(f^n(s))\right\}_n[/math]
が疑似乱数になる。この手法を用いて構成された擬似乱数発生器として、Blum-Blum-Shubが挙げられる。Blum-Blum-Shub擬似乱数発生器では、[math]f(x)=x^2 \bmod{N}[/math]、 b(x)=xの最下位ビットを用いている。
また、落とし戸付き一方向性置換のハードコア述語は、IND-CPA安全な公開鍵暗号方式を構成することにも使える。落とし戸付き一方向性置換を f、ハードコア述語を b とする。平文を [math]m \in \{0,1\}[/math] に対して、乱数 r を用いて
[math]E(m;r) = (f(r), b(r) \oplus m)[/math]
という暗号方式がそれである。
ある述語 b がハードコア述語であることを示す帰着は、符号のリスト復号アルゴリズムになっていることも多い。例えば、ゴールドライヒとレビンの帰着はアダマール符号 (または特殊なリード・マラー符号)のリスト復号アルゴリズムになっている。
脚注
- ↑ Goldreich Ch. 2.7.3 "Foundations of Cryptography vol 1: Basic Tools". J. Haastad, A. Schrift, and A. Shamir. The Discrete Logarithm Modulo a Composite Hides O(n) Bits. Journal of Computer and System Science, Vol. 47, pages 376-404, 1993.
参考文献
- Oded Goldreich, Foundations of Cryptography vol 1: Basic Tools, Cambridge University Press, 2001.
- Oded Goldreich and Leonid A. Levin, A Hard-Core Predicate for all One-Way Functions, STOC 1989, pp25–32.