随机性可以节省:短种子能使每对哈希值具有所需联合分布,即使整组值并非相互独立。运用方差界或分析碰撞时,这个区别很重要。我们使用素数域,因为每个非零元素都有乘法逆元。
两个随机系数
固定素数 q,记 Fq=Z/qZ。种子是独立均匀地从 Fq 选出的一对 (a,b),它选定的哈希函数为
ha,b(x)=ax+b(modq),x∈Fq.这个族有 q2 个等可能的成员,且包括 a=0 的情况。
下文的输入 x,y 在随机选种子之前固定。对固定 x 及任意 u,恰有 q 个 (a,b) 满足 ax+b=u(每个 a 对应一个 b),所以 h(x) 均匀分布。更强的陈述同时涉及两个键。
设 x=y 为 Fq 中固定的元素。对每个 u,v∈Fq,
P(h(x)=u, h(y)=v)=q21.因此 h(x) 与 h(y) 相互独立,并各自在 Fq 上均匀分布。
方程 ax+b=u 及 ay+b=v 蕴含 a(x−y)=u−v。由于域中 x−y=0,它有逆元,所以 a=(u−v)(x−y)−1 被唯一确定,然后 b=u−ax 也被唯一确定;反过来,这对 (a,b) 满足两条方程。因此 q2 个等可能种子中恰有一个产生值对 (u,v),概率为 1/q2。对 v 求和得每个值的概率为 1/q,联合概率正是乘积 q1⋅q1。
证明透视
解出种子
唯一不寻常的一步,是把“哪些种子给出这两个值?”看成以 (a,b) 为未知数的线性方程组,而不是以 (x,y) 为未知数。真正起作用的假设只有域中的 x=y:它使系数 x−y 可逆,这正是 q 必须是素数、键必须是不同的域元素的原因。种子分布必须保留 a=0:它把两个键都送到 b,排除它便会改变联合分布,下面的常见错误会说明这点。论证只数种子的个数,从未用到 u,v 的具体值,所以一次涵盖全部 q2 个值对。
将 q 个 u=v 的情况相加,得到 P(h(x)=h(y))=1/q。此结论假设输入是不同的域元素:余数相同的两个整数不是此哈希的不同输入。它也假设输入与种子独立地预先固定;先看种子再选输入的对手属于不同模型。
三个键与容易误用的推论
令 q=7,固定键 0,1,2。若 (a,b)=(1,2),三个值为 (2,3,4);若 (a,b)=(0,4),则为 (4,4,4)。一般而言,若 a=0,乘以 a 是单射,所以三个不同的键都不碰撞;若 a=0,三个全部碰撞。由于 a 均匀分布,
P(至少一次碰撞)=71,E[碰撞对数]=73.
期望也可由三个两两碰撞概率及线性性得到。并集界给出 P(某次碰撞)≤3/7,有效但在此偏松。对 m 个固定且不同的域元素,同样的并集界论证至多给出 (2m)/q(任何概率当然至多为一)。对这个特定的仿射族,当 m≥2 时,至少一次碰撞的精确概率是 1/q:要么所有键碰撞,要么全不碰撞。这个结论不应假定适用于任意两两独立族。
反例模式
哈希值两两独立,碰撞事件却相依
对这三个固定键,每一对哈希值相互独立。但事件 h(0)=h(1) 与 h(1)=h(2) 恰好都等于事件 a=0,它们的联合概率是 1/7,不是 1/49;把两个概率相乘是无效的。此外在 F7 中 h(2)=2h(1)−h(0),所以三个哈希值并非相互独立。
例题
令 q=5,键 x=1、y=3,目标值 u=0、v=3。则 a=(u−v)(x−y)−1;在模 5 下,u−v=−3≡2,x−y=−2≡3,而 3−1=2,因为 3⋅2=6≡1。所以 a=2⋅2=4,b=u−ax=0−4=−4≡1。验算:h(1)=4⋅1+1=5≡0,h(3)=4⋅3+1=13≡3。两个目标都达到,而计算表明没有其他种子可以做到。
例题 1.4.4
(F7 上三个键的碰撞数)
取 F7 中的键 0,1,2。种子 (a,b)=(3,5) 给出值 5,1,4,没有碰撞;种子 (0,4) 给出 4,4,4,有三对碰撞。只有 a=0(49 个种子中的七个)会产生碰撞,所以 E[碰撞对数]=71⋅3+76⋅0=73,与三对各为 1/7 一致。
令 q=7,用整数 2 和 9 作为键。由于 9≡2(mod7),它们是同一个域元素,对每个种子都有 h(2)=h(9),碰撞概率是 1 而非 1/7。定理不适用,因为在 F7 中 x=y 不成立。把 9 换成不同的余数 3,碰撞概率便恢复为 1/7。
常见错误
(为避免平凡哈希而剔除 a=0)
函数 h0,b 是常数,看起来像可以丢弃的退化情况。若把 a 限制为非零,则对 x=y,h(x) 与 h(y) 永远不相等,于是 P(h(x)=h(y))=0=1/q,两个值的联合分布也不再在 Fq2 上均匀。两两独立性需要完整的种子空间。
定理针对 Fq 中不同的元素。相差 q 的倍数的键以概率 1 碰撞。应先把键化为模 q 的余数,或使用大于最大键的素数。
种子带来什么
由两个域元素索引的函数共有 q2 个且等可能;存储种子需要两个域元素。固定 q 时,直接求值每个键使用一次域乘法和一次加法;精确的比特成本取决于表示方式及算术实现。两两独立性足以支持某些方差计算,但不能证成任意事件概率的乘积,也不能满足指数尾界论证所需的完全独立假设。若键是任意长的字符串,还需要额外的编码或哈希构造,以及它自己的碰撞分析。
习题
快速检查
(设 q=7、a=3、b=5,计算 h(2)。)
解答 · 答案
h(2)=3⋅2+5=11≡4(mod7)。
快速检查
(对不同的固定 x,y,P(h(x)=h(y)) 是多少?)
把 P(h(x)=u,h(y)=u) 对 u 求和。
解答 · 答案
u 的 q 个取值各贡献 1/q2,总和为 q/q2=1/q。
快速检查
(对三个不同的固定域元素键,计算碰撞对数的期望。)
解答 · 答案
共有三对,各以概率 1/q 碰撞,所以期望为 3/q。线性性不需要碰撞事件之间独立,而这些事件其实是相依的。
快速检查
(若 x 与 y 是相差 q 的整数,能套用“不同域元素”的结论吗?)
解答 · 答案
不能。它们的余数相同,是同一个域元素,在此映射下必然得到相同的哈希值:碰撞概率是 1,不是 1/q。