如何展示从k-wise独立哈希函数的哈希代码的独立和统一分发? -- probability-theory 领域 和 hash 领域 cs 相关 的问题

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?


简体版||繁體版
1
vote

问题

中文

$ k $ 哈希函数的独立族族的定义,我遇到了一个romial $ h $ $ d $ $ r $ 是k-wise独立的对于所有Distinct $ X_1,X_2, Dots,X_K In D $ $ Y_1,Y_2, Dots,Y_K 在r $

$$ mathbb {p} _ {h 在h}(h(x_1)= y_1,h(x_2)= y_2, dots,h(x_k)= Y_K)= FRAC {1} {| R | ^ K} $$

wikipedia文章在k-wise独立哈希函数(使用上面定义)声明该定义等同于以下两个条件:

(i)对于所有 $ x In d $ $ h(x)$ 是统一分布在 $ r $ 鉴于 $ h $ 是随机选择的 $ H $

(ii)对于任何固定的不同键 $ x_1,x_2, dots,x_k In d $ ,作为 $ h $ $ h $ ,哈希代码 $ h(x_1),h( x_2), dots,h(x_k)$ 是独立的随机变量。

对我来说是不是显而易见的,而不是明确地假设定义中的(ii)(反之亦然)。 如何定义足以证明(i)和(ii)?

英文原文

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\dots, x_k \in D$ and $y_1, y_2,\dots, y_k \in R$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, \dots, h(x_k) = y_k) = \frac{1}{|R|^k}$$

The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:

(i) For all $x \in D$, $h(x)$ is uniformly distributed in $R$ given that $h$ is randomly chosen from $H$.

(ii) For any fixed distinct keys $x_1, x_2,\dots, x_k \in D$, as $h$ is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), \dots, h(x_k)$ are independent random variables.

It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). How is the definition sufficient for proving both (i) and (ii)?

     

回答列表

1
 
vote
vote
最佳答案
 

整个,我们假设 $ | d | geq k $

假设 $ h $ 满足,对于所有distinct $ x_1, dots,x_k in d $ and All $ y_1, ldots,y_k in r $ $$ pr_ {h 在h} [h(x_1)= y_1, ldots,h(x_k)= y_k] = frac {1} {| r | ^ k}。 $$ 现在让 $ x 中的d $ 是任意的。由于 $ | D | geq k $ ,我们可以找到 $ x_2, ldots,x_k in d $ 这样 $ x,x_2, ldots,x_k $ 是不同的。对于每个 $ y 在r $ 中, $$ pr_ {h 在h} [(x)= y] = sum_ {y_2, ldots,y_k in r} pr_ {h 在h} [h(x)= y,h(x_2)= y_2, ldots,h(x_k)= y_k] = \ sum_ {y_2, ldots,y_k 在r} frac {1} {| r | ^ k} = frac {| r | ^ {k-1}} {| r | ^ k} = frac { 1} {| r |}。 $$ 这证明(i)。要查看(ii),请设 $ x_1, ldots,x_k 中的d $ 是不同的。然后对于所有 $ y_1, ldots,y_k $ $$ pr_ {h 在h} [h(x_1)= y_1, ldots,h(x_k)= y_k] = frac {1} {| r | ^ k} = prod_ {i = 1} ^ k FRAC {1} {| r |} = prod_ {i = 1} ^ k pr_ {h 在h} [h(x_i)= y_i]。 $$

在另一个方向上,假设(i)和(ii)保持。然后,对于所有Distinct $ X_1, Ldots,X_K In d $ $ y_1, ldots,y_k $ $$ pr_ {h 在h} [h(x_1)= y_1, ldots,h(x_k)= y_k] = prod_ {i = 1} ^ k pr_ {h in h} [h(x_i)= y_i] = prod_ {i = 1} ^ k frac {1} {| r |} = frac {1} {| r | ^ k}。 $$

 

Throughout, we assume that $|D| \geq k$.

Suppose that $H$ satisfies, for all distinct $x_1,\dots,x_k \in D$ and all $y_1,\ldots,y_k \in R$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}. $$ Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x_2,\ldots,x_k \in D$ such that $x,x_2,\ldots,x_k$ are distinct. For each $y \in R$, $$ \Pr_{h \in H}[h(x)=y] = \sum_{y_2,\ldots,y_k \in R} \Pr_{h \in H}[h(x)=y,h(x_2)=y_2,\ldots,h(x_k)=y_k] = \\ \sum_{y_2,\ldots,y_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}. $$ This proves (i). To see (ii), let $x_1,\ldots,x_k \in D$ be distinct. Then for all $y_1,\ldots,y_k$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k} = \prod_{i=1}^k \frac{1}{|R|} = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i]. $$

In the other direction, suppose that (i) and (ii) hold. Then for all distinct $x_1,\ldots,x_k \in D$ and $y_1,\ldots,y_k \in R$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i] = \prod_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} . $$

 
 
   
   

相关问题

6  Codomain /范围是哈希函数始终$ mathbb {z} $或$ mathbb {n} $?  ( Is the codomain range of a hash function always mathbbz or mathbbn ) 
从 wikipedia 哈希函数是任何映射大数据的算法或子程序 可变长度,称为键,较小的数据集 固定长度。例如,一个人的名字,有变量 长度可以散列到一个整数。退回的值 通过哈希函数称为哈希值,哈希代码,哈希议量, 校验和或简单的哈希。 我想知道哈希函数的范围/码球器是否始终是自然数或整数的...

14  传播输入的功能  ( Function that spreads input ) 
我想知道是否从n比特号与具有以下特征的n位数字的函数$ f $: $ f $应该是双重的 $ f $和$ f ^ { - 1} $应该可以计算得很快速 $ f $应该返回与其输入没有明显相关的数字。 理由是: 我想写一个在数据上运行的程序。数据的一些信息存储在二进制搜索树中,其中搜索键是字母表的符号。随着...

3  使用哈希的二进制搜索树的术语?  ( Term for binary search tree using hashes ) 
我正在寻找一种使用最小内存和代码轻松存储和访问符号表的方法,我与BST一起使用。然而,符号倾向于以foo0,foo1,foo2 ......所以树平衡是一个问题。 我被认为是平衡和自动平衡算法,但是我意识到给出了一个很好的哈希函数的钥匙的哈希应该有50%的左/右的平均电量。而且我已经有一个哈希函数,以便没有额外的代码...

1  解释操作系统中的哈希页面表  ( Explain hashed page tables in operating system ) 
我有一个难以了解虚拟内存管理中使用的散列页表。这是我参考的幻灯片的图片: 我理解p是哈希,然后在页面表中检查哈希以进行匹配。什么是元素参考这里?这是页表输入吗?链均值是什么以及虚拟页码所在的地方? 某种物体可以帮助我理解流程图吗?谢谢 ...

0  哈希函数订单从原产地最接近最近的船只  ( Hash function orders ships from closest to furthest from the origin ) 
假设我们有一个圆雷达,扫描 $ x ^ 2 + y ^ 2 leq z ^ 2 $ (一个圆圈) 。 我们希望设计一个哈希函数 $ h $ ,我们可以订购 $ n $ 从最接近的船只远离原产地。 我们希望在 $ theta(n)$ 时间中进行这个订购算法的<强>预期时间复杂性。< / p> 每艘船都有一个坐标 ...

1  一些固定间隔中MD5哈希的前缀的冲突  ( Collisions of prefixes of md5 hashes in some fixed interval ) 
我想知道,如果在无符号介质范围内有MD5哈希碰撞(0 - 16777215)。可悲的是,由于内存(RAM)限制,我无法运行脚本来检查此项。答案可能是没有;下一步是 - 在找到第一次碰撞之前,需要多少个字符? MD5哈希有32个字符。如果你只使用,让我们说,来自所有MD5哈希在媒体范围内的前九个字符,他们仍然是...

1  关于佐色斯散系与碰撞机会的理论问题  ( Theoretical question about zobrist hashing and chances of collision with slight ) 
我有一个哈希表,它使用 zobrist散列计算各种位置的散列。哈希表用于查找各种换位。对于某些位置,我不想允许任何换位,但我仍然想要将位置存储在哈希表中。因此,我试图通过xor与保存位置结构的对象的内存地址来使职位的哈希统一。这是一些伪代码: hash = zobristHash(position); if (m...

2  证明计算Minhash  ( Proving calculating minhash ) 
我正在阅读关于minhash技术来估计2套之间的相似性:给定集A和B,H是散列函数,$ H_ min(s)$是设置s的最小散列,即$ h_ MIN(S)= min(h(s))在s中的s。我们有等式: $$ p(h_ min(a)= h_ min(b))= frac {| a cap b |} {| a ...

-1  完美(或几乎完美)哈希函数,用于n位整数,恰好k位设置  ( Perfect or almost perfect hash function for n bit integers with exactly k bits ) 
我有一个数据集,其中包含2598960元元素(最多)52位长度的无符号整数。数据集具有完全5位设置的属性。 这只是1个数据集 - 我有类似的数据集的整数,精确地设置了6,7和9位。 鉴于数据集的这种特殊属性,有没有办法,我可以创建除了提出的方法之外的最小完美哈希函数在这里,我被拒绝,因为查找需要2个哈希并使用if语句...

4  整数设置与同性恋散列等类似的草图上的脱节查询  ( Integer set disjointness query on sketches with something like homomorphic hashi ) 
假设我有两组整数 $ a $ 和 $ b $ ,我有一个草图函数 $ mathsf {scraxt} _n: mathcal {p}( mathbb {z}) to 2 ^ n $ 返回bitstring的数据结构大小 $ n $ 。可以使用函数 $ mathsf {disjoint} _n:2 ^ n tim...

83  为什么最好在散列函数中使用素数作为mod?  ( Why is it best to use a prime number as a mod in a hashing function ) 
如果我有1到100的键值列表,我希望在11个桶中组织它们,我被教导形成mod函数 $$ h = k bmod 11 $$ 现在所有值都将在9行中一个接一个地放置。例如,在第一个桶中,将有0,11,22磅$ 0.在第二,将有1,12,23 dots $等。 让我们说我决定成为一个坏男孩,并使用非素数作为我的散...

1  单向哈希功能吗?  ( Are hash functions one way ) 
我听说我们可以将任何文本转换为哈希代码,但哈希代码不能转换回没有蛮力的文本。 假设我们认为文本"mal" 。单个字母的哈希代码是 m = 6f8f57715090DA2632453988D9A1501B a = 0cc175b9c0f1b6a831c399e269772661 l = 2db95e8e1a...

0  为什么字母表可以在Base 256中的数字中表示  ( Why can the alphabet be represented in numbers in base 256 ) 
这是字符串散列的背景。我不确定为什么像,CS一样,可以表示为CS ='C'* 256 +'/ p> 有谁知道这个? ...

3  算法追随其差分关系后的集合  ( Algorithm that hashes a collection of sets following their disjointness relation ) 
我想知道是否有一个简单的算法来做这项工作: 假设我有一个对象$ c $的集合,以及二进制关系$ r:c times c $,它是自动反光的($ forall c 中c:c r c $)和对称($ forall b,c c:b r c 意味着c r b $)。关系不一定是传递的。 我想找到一个整数函数$$ h...

0  转换为基础-R号码  ( Conversion to base r numbers ) 
我正在阅读robert sedgewick的算法4th版本,并且难以在一个特定的问题上陷入困境。本书的第460页,作者正在描述散列字符串的技术并使用模块化散列的素数。从第四行开始: If R is greater than any character value, this computation would ...

4  使用$ O(| S |)$预计算,查找Substring $ [i,J] $的哈希[i,j] $ o(1)$  ( Finding hash of a substring i j in o1 using os pre computation ) 
给定字符串 $ s $ 长度 $ n $ 字符,是否可以计算其子字符串的哈希 $ [i,j] $ (从索引 $ i $ 到 $ j $ ,两个包含的)在 $ o(1)$ 使用某种形式的预兆?我们可以使用滚动哈希的修改吗? 以下是我问题的类似问题。在它中,字符串以压缩形式给出。示例:如果字符串是 "aaabccdeee...

2  如何创建10个字符,唯一代码,没有碰撞,但不可预测?  ( How can i create 10 character unique codes with no collisions but without bein ) 
如果我们使用数字和字母,有 $ 36 ^ {10} $ 唯一的组合。碰撞已经不太可能,但我需要它是不可能的,所以使用散列超出了图片(?)。 如果它们已被"激活" 可兑换,则使用案例是兑换每个人。认为像Webkinz代码一样。 效率低下的解决方案是一次生成所有这些,每个都有一个属性,每次都说它是否已被激活,并保留已经兑...

0  散列算法最小化分布  ( Hashing algorithm which minimizes distribution ) 
考虑应用 A1, A2 .. AN 具有属性 P11, P12,... PN1, PN2..我们有以下约束 - total number of properties >> number of applications total number of properties >> number of bucke...

5  哈希函数究竟是什么?  ( What exactly is a hash function ) 
我不知道我如何在生活中得到这种遥远,而不是真正掌握这一点,而是因为它发生了,我仍然非常困惑哈希函数的概念。我做了一些googling / wikipedia-ing,这就是我得到的: 哈希表很好,因为索引可以存储在较小的数组中 散列函数有点像均匀的随机数发生器,总是具有相同的种子但不是真的(而且我没有为什么) 但...

9  攻击不满足单向财产的哈希函数  ( Attack on hash functions that do not satisfy the one way property ) 
我正在修改计算机安全课程,我陷入了过去的一个问题之一。这是: 爱丽丝($ a $)希望使用共享秘密$ s_ {ab} $向Bob($ b $)发送短信$ m $才能验证消息来自她的消息。她建议发送一个有两件的一条消息: $$ a to b: quad m,h(m mathbin patplel s_ {a...

18  Quantum Computing最终可以用来让现代的哈希戏剧休息?  ( Could quantum computing eventually be used to make modern day hashing trivial to ) 
简单地说,如果一个是用电源构建量子计算设备,例如20夸张,可以使用这种计算机来制作任何类型的现代散列算法无用吗? 甚至可以利用传统计算应用中量子计算的功率? ...

2  为什么具有简单的乘法循环和非常好的雪崩不足以产生分布良好的散列值?  ( Why having a simple multiplication loop and very good avalanche isnt enough to ) 
现代非加密32-和64位值哈希函数,例如Lookup3,Murmurhash3和Cityhash具有相当复杂的环路,每个迭代包括许多乘法,XOR和旋转。为什么需要这一点,因为有很好的雪崩程序(32 - &gt; 32和64位),它会有效地随机混合比特。所以,即使这个简单的循环: hash = seed; whi...

27  有防绽放过滤器吗?  ( Is there an anti bloom filter ) 
a bloom filter 使得可以有效地跟踪是否已经遇到了各种值在处理过程中。当有许多数据项时,盛开的过滤器可能会导致在哈希表上保存的重要内存。盛开过滤器的主要特征,它与哈希表共享,如果一个项目不是新的,它总是说"不是新的" ,但是一个非零概率将被标记为"不是新的"即使是新的。 是否有一个"反绽放过滤器" ...

2  碰撞障碍物函数  ( Collision resistant hash function ) 
功能是$( varepsilon,t)$ - 如果没有布尔电路(使用"不是" ,"," 或"或" )大小的大多数$ t $的碰撞,则输出概率的碰撞至少$ varepsilon $。 让$ h_0: {0,1 } ^ {2m} lightarrow {0,1 } ^ M $是$( varepsilon,t)$ ...

1  与素数步行有关吗?  ( Is open adressing with prime steps bijective ) 
谁可以帮助我这个主题:探测,具有素数。 我正在努力定义散列函数$ h(k,i)$ h(k,i)$以便在长度m表中的开放寻址,即,带插槽数$ 0,1,2, dots,m - 1 $。 我们知道函数$ h(k,i)= h_1(k)+ i cdot h_2(k) mod m $为每一个$ h_2(k)$和$ m产生每...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有