残りハッシュ補題

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

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

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

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

X を上のランダム変数とし、を2 ユニバーサルハッシュ関数とします。 ${\displaystyle {\mathcal {X}}}$${\displaystyle 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)}$

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

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

ここでUはSに対して一様であり、Sに依存しない。^[2]${\displaystyle \{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間の統計的な距離です。

• ユニバーサルハッシュ
• 最小エントロピー
• レニエントロピー
• 情報理論的セキュリティ

• CH Bennett、G. Brassard、JM Robert「公開討論によるプライバシーの増幅」SIAM Journal on Computing、17(2):210-229、1988年。
• C. Bennett、G. Brassard、C. Crepeau、U. Maurer。一般化されたプライバシー増幅。IEEE Transactions on Information Theory、41、1995 年。
• J. Håstad、R. Impagliazzo、LA L​​evin、M. Luby。「任意の一方向関数からの疑似乱数ジェネレーター」。SIAM Journal on Computing、v28 n4、pp. 1364-1396、1999 年。