（散列和认证）设H为一个散列函数类，其中的每个散列函数
将关键字全域U映射到{0,1，...，m-1}上。我们称H是k全域的（k-universal），如果对每个由k个不同的关键字<x(1),x(2),...,x(k)>构成的固定序列，以及从H中随机选出的任意散列函数h，序列<h(x(1)),h(x(2)),...,h(x(n))>是mk个长度为k的序列（其元素取自{0,1，...,m-1}）中任意一个的可能性相同。
a.证明：如果散列函数簇H是2全域的，则它是全域的。
b.设全域U为取自Zp={0,1,...，p-1}中数值的n元组集合，此处p为素数。考虑元素x=<x0,x1,...,xn-1>
U。对于任意的n元组a=<a0,a1,...,an-1>U，定义散列函数ha为
并设H={ha}。证明：H是全域的，但不是2全域的。（提示：寻找一个关键字，使得H中所有散列函数对其都得到相同的值）
c.假设将（b）中的H略作修改：对任意的
和任意的
，定义
且H={h'ab}。论证H'是2全域的。（提示：考虑固定的n元组
和
，对某个i有
。当ai和b包括Zp时，h'ab(x)和h'ab(y)会如何？）
d.假设Alice和Bob悄悄地约定了一个自取2全域散列函数簇H中的散列函数h。每个将关键字全域U映射到Zp上，此处p为素数，后来，Alice通过互联网向Bob发送了一个消息m，其中
。她同时还通过发送一个认证标记t=h(m)来向Bob认证这一消息，而Bob则要检查他所接收到的(m,t)对是否确实满足t=h(m)。假设某一对手半路中截获了(m,t)，并试图将该值对替换为另一值对(m',t')来欺骗Bob。论证无论该对手的计算机性能多好，他成功欺骗Bob接受(m',t')的概率至多为1/p，即使他知道所用的散列函数簇H。
