ハードコア述語

暗号学において、一方向性関数fのハードコア述語とは、（ xの関数として）計算は容易だが、 f(x)が与えられた場合には計算が困難な述語b （すなわち、出力が単一ビットである関数）である。形式的には、xのランダム選択に対して半分より大幅に高い確率でf(x)からb(x)を計算する確率的多項式時間（PPT）アルゴリズムは存在しない。 ^{[1] ： 34}言い換えれば、x が一様にランダムに抽出された場合、f(x)が与えられた場合には、PPTの攻撃者はハードコアビットb(x)とxの長さに関して無視できるほどの利点を持つ一様ランダムビットとを区別することしかできない。^[2]

ハードコア関数も同様に定義できる。つまり、xが一様ランダムに選択された場合、f(x)が与えられたとき、任意の PPT アルゴリズムは、ハードコア関数値h(x)と長さ|h(x)|の一様ランダムビットを区別することしかできず、 xの長さに対する利点は無視できる。^{[3] [4]}

ハードコア述語は、f を反転することの難しさを「集中した意味で」捉えます。

一方向性関数は逆関数として扱うのが難しいが、像f(x)から原像 cの部分情報を計算できるかどうかは保証されていない。例えば、RSA は一方向性関数であると推測されるが、原像のヤコビ記号は像のヤコビ記号から簡単に計算できる。^{[1] : 121}

1対1関数がハードコア述語を持つ 場合、その関数は一方向性でなければならないことは明らかです。Oded GoldreichとLeonid Levin (1989)は、あらゆる一方向性関数を簡単に変更して、特定のハードコア述語を持つ一方向性関数を得る方法を示しました。^[5] fを一方向性関数とします。g(x,r) = (f(x), r)と定義します 。ここで、 rの長さはxの長さと同じです。x _{j は}xのj^番目のビットを表し、 r _{j は}rのj^番目のビットを表します。

${\displaystyle b(x,r):=\langle x,r\rangle =\bigoplus _{j}x_{j}r_{j}}$

はgのハードコア述語です。b (x, r) = < x, r > であることに注目してください。ここで、 <·, ·> はベクトル空間( Z ₂ ) ⁿ上の標準内積を表します。この述語は計算上の問題によりハードコアです。つまり、g(x, r) は情報理論的に損失があるために計算が難しいわけではありません。むしろ、この述語を効率的に計算するアルゴリズムが存在する場合、 f を効率的に反転できる別のアルゴリズムが存在します。

同様の構成により、O(log |x|)出力ビットを持つハードコア関数が得られます。fが強い一方向性関数であると仮定します。g(x, r) = (f(x), r)と定義します。ここで、| r | = 2| x | です。長さ関数l(n) = O(log n) st l(n) ≤ nを選択します。

${\displaystyle b_{i}(x,r)=\bigoplus _{j}x_{j}r_{i+j}.}$

するとh(x, r)  := b ₁ (x, r) b ₂ (x, r) ... b _l(|x|) (x, r)は出力長l(|x|)のハードコア関数となる。^[6]

入力xの実際のビットがハードコアである場合もあります。たとえば、RSA関数への入力のすべてのビットはRSAのハードコア述語であり、 xのO(log |x|)ビットのブロックは多項式時間でランダムビット文字列と区別できません（RSA関数の逆変換が困難であるという仮定の下）。^[7]

ハードコア述語は、任意の一方向順列から擬似乱数生成器を構築する方法を提供します。bが一方向順列fのハードコア述語であり、sがランダムシードである場合、

${\displaystyle \{b(f^{n}(s))\}_{n}}$

は疑似乱数ビット列であり、f ^{n は}sにfを適用するn回目の反復を意味し、bは各ラウンドnで生成されるハードコアビットである。^{[1] : 132}

トラップドア一方向順列のハードコア述語（トラップドア述語として知られる）は、意味的に安全な公開鍵暗号化方式を構築するために使用できる。 ^{[1] : 129}

• リストデコード（リストデコードについて説明します。一方向関数からのハードコア述語の Goldreich-Levin 構築の核心は、アダマール コードのリストデコード アルゴリズムとして考えることができます）。

• Oded Goldreich、「暗号化の基礎 vol 1: 基本ツール」、Cambridge University Press、2001 年。