「クラス$ \ mathscr {H} _ {p、m} $ hash関数はユニバーサルです」

Question

私はCormenらによるアルゴリズムの紹介を行っていました。 al。私が上記の証明と私が困難を感じたステップについて次の抜粋に遭遇したところ、 $ \ dagger $ と $ \ Dagger \ Dagger $

ハッシュ関数のユニバーサルクラスの設計

$ p $ は、可能なすべてのキー $ k $ があるように十分な大きさの数です。範囲 $ p - 1 $ $ p - 1 $ 。 $ z_p $ set $ \ {0,1、...、p - 1 \} $ 、および $ Z_P ^ * $ を設定 $ \ {1,2、...、p - $ 。キーのユニバースのサイズが、ハッシュテーブル内のスロット数 $ m $ の数よりも大きいと仮定します。 $ p> m $ 。

$ a \ in z_p ^ *のハッシュ関数 $ h_ {a、b} $ を定義します。 $ と任意の $ b \ $ $ ：

$ h_ {a、b}=（（a.k + b）\ mod p）\ mod m $ 。

そのようなハッシュ関数の家族：

$$ \ mathscr {h} _ {p、m}={h_ {a、b}：z_p ^ *、b \ in z_p \} $ $

---

定理：クラス $ \ mathscr {h} _ {p、m} $ {p、m} $ はユニバーサルです。

---

証明：

2つの異なるキー $ k $ と $ k \ neq l $ 。与えられたハッシュ関数 $ h_ {a、b} $

$$ r=（ak + b）\ mod p $$ 、

$$ s=（Al + B）\ mod p $$ 。

最初に $ r \ neq s $ であることに注意してください。どうして？

を観察する

$$ r - s= a（k - l）（\ mod p）$$ 。

$г\ neq s $ x $ p $ はプライム、両方の $ a $ と $（k - l）$ はゼロのゼロモジュロです。 $ p $ 、そしてそれらの製品もゼロ以外のモジュロ $ p $

である必要があります。 したがって、 $ \ mathscr {h}}の $ h_ {a、b} $ の計算中{P、M} $ 、異なる入力 $ k $ 、および $ l $ 異なる値 $ R $ と $ s $ modulo $ p $ ; 「MOD Pレベル」にはまだ衝突はありません。 さらに、 $ p（p - 1）$ $ x $の選択a、b） $А\ NEQ 0 $ を使用した $（r、s） $ r \ neq s $ 付き$ は、 $ a $ を解決できます。 $ b $ $ r $ と $ s $ $ ^ \ dagger $ ：

$$ a=（（r - s）（（k - l）^ { - 1} \ mod p））\ mod p $$ 、< / P>

$$ b=（R - AK）\ mod p $$ 、

$（（k - l）^ { - 1} \ mod p）$ は、 $ k - l $ 。 $ p（p - 1）$ のみがあるので $（r、s）$ $г\ neq s $ 、ペア間に1対1の対応があります $（a、b）$ < / span> $ a \ neq 0 $ とペア $（r、s）$ class="math-container"> $ r \ neq s $ 。したがって、任意の入力対の入力ペア $ k $ 、および $ l $ 、 $（A、B）$ $ z_p ^ * \ hyd z_p $ から、z_p $ から均一にclass="math-container"> $（r、s）$ は、異なる値のモジュロpのペアである可能性があります。

それはそれから、異なる鍵が $ k $ aの確率に続きます。

nd $ l $ 衝突は $ r \ equiv s（\ mod m）$ の確率に等しいです。 $ r $ と $ s $ がランダムに選択されている $ p $ 。 $ r $ の $ p - 1 $ の指定された値の値 $ s $ の残りの値、値 $ s $ の数、そのような $ s \ neq r $ と $ s \ equiv r（\ mod m）$ はです。 em> $ ^ {\ Dagger \ Dagger} $

$$ \ LCEIL P / M \ RCEIL - 1 <（（P + M - 1）/ M） - 1 $$ $$=（p-1）/ m $$ 。

$ s $ が $ r $ に衝突する確率 $ m $ は $（（p - l）/ m）/（p - 1）= 1 / m $ です。 。

<したがって、 $ k、l \ in z_p $ 、

$$ pr \ {h_ {a、b}（k）= h_ {a、b}（l）\ \ leq 1 / m $$

$ \ mathscr {h} _ {p、m} $ は確かにユニバーサルです。

---

疑問：

証明書の次の記述を理解できなかった：

$ \ Dagger $ ：可能な $ p（p - 1）$ $（a、b）$ の選択 $А\ Neq 0 $ の選択結果のペア $（r、s）$ $ r \ neq s $ は、解決できるためです。 $ a $ と $ b $ 与えられた $ r $ < / span>と $ s $

なぜ「 $ $ 、 $ b $ を解決できます。 "Math-Container"> $ R $ と $ s $ " $ \ \ inipsies $ 「可能な $ p（p - 1）$ p（p - 1）$ の選択 $（a、b）$ $А\ Neq 0 $ で $（r、s）$ が渡されます。 $г\ neq s $ "

---

$ \ dagger \ dagger $ ： $ r $ の指定値 $ p - 1 $ $ s $ の残りの値、値の数 $ s $ $ s \ neq r $ と $ s \等高線R（\ mod m）$ は、最大 $ \ lceil p / m \ rceil - 1 $ です。

$ \ lceil p / m \ riil - 1 $ ？

Answer 1

$ k_1 \ neq k_2 \ in \ mathbb {z} _p $ の場合、

$ \ pr \制限_ {（a、b）\ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} [AK_1 + B \ Equiv AK_2 + b \ pmod m] \ le \ frac {1} {m} $ 。

$ \ mathbb {z} _p $ でafets and virtspleplicationの両方が予備成形されている場合は。

$ a \ sim u（z_p ^ *）$ と $ b \ sim uの場合（Z_P）$ $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ 、 $（AK_1 + B、AK_2 + B）$ は $ \ {（x、y）\ in \ mathbb {z} _p ^ 2で一様に分布しています。 X \ NEQ Y \} $ （つまり、 $ H（k_1）$ 、 $ H（k_2）$ は異なるエントリを持つペアを越えて共同で均一なもので、ランダム性は $ h $ の選択を超えています）。これは、すべての $（c_1、c_2）\ in \ mathbb {z} _p ^ 2 $ で $ C_1 \ NEQ C_2 $ 、次の線形方程式のシステム：

$ \ begin {align *} ＆ak_1 + b= c_1 \\ ＆ak_2 + b= c_2 \ end {align *} $

は、変数 $（a、b）\ times \ mathbb {z} _p $ に一意の解決策を持ちます。 $ k_1-k_2以来、最初の利回りから2番目の式を減算する $ a（k_1-k_2）= c_1-c_2 $ $ はゼロ以外です。両側を逆に乗算し、 $ a=（k_1-k_2）^ { - 1}（c_1-c_2）$ 。 $ c_1 \ neq c_2 $ の場合、これは $ a $ のゼロ以外のソリューションです。 $ b $ を抽出します。したがって、 $（c_1、c_2）$ ごとに、 $ c_1 \ neq c_2 $ $（a、b）\ in z_p ^ * \ times \ mathbb {z} _p $ $ \ big（ h_ {a、b}（k_1）、h_ {a、b}（k_2）\ big）=（c_1、c_2）$ 。これはあなたの最初の質問を解決します。

今、 $ \ mathbb {z} _p $ への $ \ LCEIL P / M \ RCEIL $ バケット、 $ b_1、...、b_ {l=lceil p / m \ rceil} $ 次のように： $ b_1={0,1、...、m-1 \}、b_2={m、m + 1、...、2m-1 \} $ 、...、< SPAN CLASS="Math-Container"> $ B_L={m \ lfloor p / m \ rfloor、m \ lceil p / m \ rceil + 1、...、p-1 \} $ 。最後のバケットは $ m $ のサイズです。同じバケット内の2つの要素は同等のモジュロ $です。 m $ 。 $ \ {（x、y）\ in \ mathbb {z} _p ^ 2での異なるペアの数を結論する。 X \ NEQ Y \} $ それは同等のモジュロ $ m $ が $ p（\ lceil）です。 P / M \ RCEIL-1）$ 、最初の要素を選択した後、 $ \ lceil p / m \ rceil-1 $ を囲むから選択する要素（あなたは異なるバケットを選ぶ必要があり、各バケットは最大1つの候補に提供する必要があります）。 $ \ big（h_ {a、b}（h_1）、h_ {a、b}（k_2）\ big）\ sim u（\ {（x、y）\ \ mathbb {z} _p ^ 2 | x \ neq y \}）$ であるので、私たちはついに結論を出すことができます：

$ \ pr \ limits _ {（a、b）\ in \ mathbb {z} _p ^ * \ time \ mathbb {z} _p} \ left [h_ {a、 B}（k_1）= h_ {a、b}（k_2）\ pmod m \ right]=frac {p（\ lceil p / m \ rceil-1）} {p（p-1）} \ le \ frac {1} {M} $

$ a $ を許容するには、 $ 0 $ を使用してください。 $ \ big（h（k_1）、h（k_2）\ big）$ は $ \ mathbb { z} _p ^ 2 $ ですが、 $ \ frac {1} {p} $ の追加の確率があります $ A= 0 $ と私たちのハッシュは同等のモジュロ $ m $ になりますので、この場合、 $ O（\ frac {1} {m}）$ 衝突確率に束縛されています。