从散列函数中获取$n-1$位也将是散列函数吗？

Question

如果$\mathcal{H}=左(\text{Gen}，H\右)$是一个抗碰撞散列族，那么$\mathcal{W}=\左(\文本{Gen}，W\右)$$W_{S}左(x\右)$表示$n-1$左大部分左(x\右)$也是抗碰撞散列家族吗？

我认为$\mathcal{H}$不会是抗碰撞散列族，但我找不到$x \neq‘$的确切反例，以致于$W_{S}左(x\右)=W_{S}左(x’\右)$。我的猜测是用归纳法证明我们可以推断出$k$位，并且仍然认为它是一个抗碰撞的散列函数，即使$k=n-1$将导致我们得到一个图像为1位的函数，而且该函数显然不是有效的哈希函数。

Answer 1

如果$\mathcal{H}=左(\text{Gen}，H\右)$是一个抗碰撞散列族，那么$\mathcal{W}=\左(\文本{Gen}，W\右)$$W_{S}左(x\右)$表示$n-1$左大部分左(x\右)$也是抗碰撞散列家族吗？

一般情况下，不。

假设$\mathcal{H}'$是一个抗碰撞散列族，并定义了$\mathcal{H}_k(x {H})= \mathcal{H}'_k(x) {H}- b$，其中$b$是一个位元。

$\mathcal{H}$是抗碰撞的(因为$\mathcal{H}_k$中的碰撞意味着$\mathcal{H}‘_k$中的碰撞)；但是$\mathcal{W}$不是，因为$\mathcal{W}_k(00) = \mathcal{W}_k(01)$