主題
Search

通用雜湊函式

設 h:{0,1}^(l(n))×{0,1}^n->{0,1}^(m(n)) 可透過演算法有效計算（解決一個 P 問題）。對於固定的 y in {0,1}^(l(n))，將 h(x,y) 視為 h_y(x) 的函式 x，它將 n 位對映（或雜湊）到 m(n) 位。設 Y in _R{0,1}^(l(n))，則如果對於不同的 x,x^' in {0,1}^n 且對於所有 a,a^' in {0,1}^(m(n))，則稱 h 為（成對獨立的）通用雜湊函式：

Pr_(Y)[(h_Y(x)=a) and (h_Y(x^')=a^')]=1/(2^(2m(n))),

即，h_Y 獨立且均勻地對映所有不同的 x,x^'。

這些函式很容易構造（Wegman and Carter 1981, Luby 1996）。

另請參閱

雜湊函式

使用 探索

參考文獻

Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.Wegman, M. N. and Carter, J. L. "New Hash Functions and Their Use in Authentication and Set Equality." J. Comput. System Sci. 22, 265-279, 1981.

在 上被引用

通用雜湊函式

請這樣引用

Weisstein, Eric W. "通用雜湊函式。" 來自 —— 資源。 https://mathworld.tw/UniversalHashFunction.html

主題分類