残りハッシュ補題

残りハッシュ補題は、ラッセル・インパグリアッツォ、レオニード・レビン、マイケル・ルビーによって初めて提唱された暗号学の補題である。^[1]

$n$ 個の均一ランダムビットを持つ秘密鍵 $X$ が与えられ、攻撃者がその鍵の $t$ $<$ $n$ ビットの値を知ることができたとすると、残余ハッシュ補題によれば、攻撃者がどの t ビットを知っているかを知らなくても、攻撃者がほとんど何も知らない約 $n$ $-$ $tビットの$ $鍵$ を生成することが可能である。攻撃者は $n$ $-$ $t$ ビット以外のすべてを知っているので、これはほぼ最適である。

より正確には、残余ハッシュ補題は、ほぼ一様に分布するランダム変数 $X$ から、（ $X$ の最小エントロピーに漸近する）ビットの長さを抽出できることを示しています。言い換えれば、 $Xについて部分的にしか知識のない攻撃者は、抽出された値についてはほとんど何も知りません。これは$ プライバシー増幅とも呼ばれます（「量子鍵配送」の記事のプライバシー増幅のセクションを参照）。 $H_{\infty }(X)$

ランダム性抽出器は同じ結果を実現しますが、（通常は）ランダム性は少なくなります。

$X$ を上の確率変数とし、を2-ユニバーサルハッシュ関数とする。 ${\mathcal {X}}$ $m>0$ ${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$

{\textstyle m\leq H_{\infty }(X)-2\log \left({\frac {1}{\varepsilon }}\right)}

すると、 $X$ に対して一様かつ独立な $S$ に対して、次式が成り立ちます。 ${\mathcal {S}}$

{\textstyle \delta \left[(h(S,X),S),(U,S)\right]\leq \varepsilon .}

ここで $Uは$ $S$ に対して一様で独立である。^[2] $\{0,1\}^{m}$

${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$ $はX$ の最小エントロピーであり、 $X$ のランダム性の程度を測る指標です。最小エントロピーは常にシャノンエントロピー以下です。は $X を$ 正しく推測する確率であることに注意してください。（最も可能性の高い値を推測するのが最善の推測です。）したがって、最小エントロピーは $X を$ 推測するのがどれほど難しいかを測る指標となります。 ${\textstyle \max _{x}\Pr[X=x]}$

${\textstyle 0\leq \delta (X,Y)={\frac {1}{2}}\sum _{v}\left|\Pr[X=v]-\Pr[Y=v]\right|\leq 1}$ $は、 X$ と $Y$ 間の統計的な距離です。

参照

参考文献

^ Impagliazzo, Russell ; Levin, Leonid A. ; Luby, Michael (1989)、「一方向性関数からの擬似乱数生成」、Johnson, David S. (編)、第21回ACMコンピューティング理論シンポジウム論文集、1989年5月14日～17日、ワシントン州シアトル、米国、{ACM}、pp. 12～ 24、doi : 10.1145/73007.73009、S2CID 18587852
^ Rubinfeld, Ronnit ; Drucker, Andy (2008年4月30日)、「Lecture 22: The Leftover Hash Lemma and Explicit Extractions」(PDF)、MITコース6.842「Randomness and Computation」の講義ノート、MIT 、 2019年2月19日取得

CH Bennett、G. Brassard、JM Robert. 公開討論によるプライバシーの増幅. SIAM Journal on Computing, 17(2):210-229, 1988.
C. ベネット、G. ブラッサード、C. クレポー、U. マウラー「一般化されたプライバシー増幅」IEEE Transactions on Information Theory、41、1995年。
J. Håstad, R. Impagliazzo, LA Levin, M. Luby. 任意の一方向性関数からの擬似乱数生成器. SIAM Journal on Computing, v28 n4, pp. 1364-1396, 1999.

[1] Impagliazzo, Russell ; Levin, Leonid A. ; Luby, Michael (1989)、「一方向性関数からの擬似乱数生成」、Johnson, David S. (編)、第21回ACMコンピューティング理論シンポジウム論文集、1989年5月14日～17日、ワシントン州シアトル、米国、{ACM}、pp. 12～ 24、doi : 10.1145/73007.73009、S2CID 18587852

[2] Rubinfeld, Ronnit ; Drucker, Andy (2008年4月30日)、「Lecture 22: The Leftover Hash Lemma and Explicit Extractions」(PDF)、MITコース6.842「Randomness and Computation」の講義ノート、MIT 、 2019年2月19日取得