ハードコア述語のソースを表示

[[暗号理論]]において、[[一方向性関数]] ''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>について, ある[[無視可能函数]] &epsilon; が存在し,
{{Indent|<math>Pr[x \gets_R \{0,1\}^n : C_n(f(x)) = b(x)] < \frac{1}{2}+\epsilon(n)</math>}}

== 一般的なハードコア述語 ==
[[全単射|一対一関数]]がハードコア述語を持つならば、一方向性関数であることは自明である。ゴールドライヒ ([[:en:Oded Goldreich]]) とレビン (Levin) は1989年に任意の一方向性関数を変形した一方向性関数が、ハードコア関数を持つことを示した。
今、''f'' を一方向性関数だとする。関数 ''g'' を
{{Indent|<math>g(x,r) := f(x) \circ r</math>}}
と定義する（<math>\circ</math>は連結を表す）。ただし、''r'' の長さは ''x'' の長さと同じであるとする。''x''<sub>j</sub> を ''x'' の ''j'' ビットとし、''r''<sub>j</sub> を ''r'' の ''j'' ビットとする。
このとき、
{{Indent|<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関数についてのハードコア関数だと予想されている<ref>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.</ref>。これは下半分の各ビットがハードコア述語であるということよりは強い。なぜならば ''f''(''x'') は ''x'' の各々のビットについての情報を漏らすことなく、特定のビット間の相関については情報を漏らしうるからである。

== ハードコア述語の応用 ==
任意の一方向性置換から暗号学的[[擬似乱数]]を構成することがハードコア述語によって可能となる。もし ''b'' が ''f'' のハードコア述語ならば、''s'' をランダムな種とし、
{{Indent|<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'' を用いて
{{Indent|<math>E(m;r) = (f(r), b(r) \oplus m)</math>}}
という暗号方式がそれである。

ある述語 ''b'' がハードコア述語であることを示す帰着は、[[符号]]の[[リスト復号]]アルゴリズムになっていることも多い。例えば、ゴールドライヒとレビンの帰着は[[アダマール符号]] (または特殊な[[リード・マラー符号]]）のリスト復号アルゴリズムになっている。

== 脚注 ==
<references />

== 参考文献 ==
* Oded Goldreich, <em>Foundations of Cryptography vol 1: Basic Tools</em>, Cambridge University Press, 2001.
* Oded Goldreich and Leonid A. Levin, [http://portal.acm.org/citation.cfm?id=73010 A Hard-Core Predicate for all One-Way Functions], STOC 1989, pp25&ndash;32.

== 関連項目 ==
* [[暗号理論]]

{{DEFAULTSORT:はあとこあしゆつこ}}
[[Category:暗号技術]]
[[Category:関数]]
[[Category:数学に関する記事]]