对于hash function的安全性,也至少有如下由弱至强三重含义:
1。one-way property:Given h(x), it is hard to find m such that h(m)=h(x)
这个“hard to find”是指不存在多项式时间的算法,可以在某多项式分之一的概率下找
到m,这个概率是对x而言的,而不是对h(x)而言的。这和one-way function定义一样。
2。weak collision-free property:Given m, it is hard to find m', such
thatm!=m' and h(m)=h(m').
3。strong collision-free property:It is hard to find such pair m and m' that
m!=m' and h(m)=h(m').