11.1杂凑函数的定义 ●定义111一个函数族{:y→rmn>m称为强无 碰撞压缩函数族,若下面两个条件成立。 (1)计算hn(x)是容易的,即存在一个多项式时间 算法F,若F的输入为1和x∈1,则其输出为 hn(x)。 (2)给定算法F要找两个不同的消息x≠x2(x1=x2) 使得h3(x)=h31(x2是困难的,即对每一个多项式时 间概率算法M,每一正多项式p(n)和一切充分大 的n有P(M(b Un)1")∈CnUn)<1m(n)(111) 其中Un表示{0,1}上的均匀分布随机变量11.1 杂凑函数的定义 ⚫ 定义 11.1 一个函数族 称为强无 碰撞压缩函数族，若下面两个条件成立。 （1）计算hn (x)是容易的，即存在一个多项式时间 算法F，若F的输入为1 n和 ，则其输出为 hn (x) 。 （2）给定算法F要找两个不同的消息 ， 使得 是困难的，即对每一个多项式时 间概率算法M’，每一正多项式p(n)和一切充分大 的n有 （11.1） 其中Un表示{0,1}n上的均匀分布随机变量。 h     n m n m n : 0,1 → 0,1 ;    n x  0,1 ( ) 1 2 1 2 x  x x = x ( ) ( ) 1 2 1 2 h x h x x x = P  ( ( ),1 ) ( ) 1/ ( ) ' r M h U Cn Un p n n n n  