Hash函数是将任意长度的输入，映射为固定长度的输出：
h
:
Z
2
∗
↦
Z
2
n
h:Z_2^*\mapsto Z_2^n
h:Z2∗↦Z2n 通常
n
n
n的取值为：128，160，256，512。 
Hash函数应具有如下特性：
- Pre-image resistant：即已知
y
y
y，根据
h
(
x
)
=
y
h(x)=y
h(x)=y求
x
x
x，需要
2
n
2^n
2n次尝试。
- 2nd pre-image resistance：已知
M
M
M和
h
(
M
)
h(M)
h(M)，找到另一个
M
′
M'
M′使得
h
(
M
′
)
=
h
(
M
)
h(M')=h(M)
h(M′)=h(M)，需要
2
n
2^n
2n次尝试。
- Collision resistance：找到任意的
x
1
!
=
x
2
x_1!=x_2
x1!=x2，使得
h
(
x
1
)
=
h
(
x
2
)
h(x_1)=h(x_2)
h(x1)=h(x2)，需要
2
n
/
2
2^{n/2}
2n/2次尝试。
一个好的Hash函数，应表现得像一个random oracle。
密码学中Hash函数可用于：
- 签名：用 s i g n R S A ( h ( M ) ) sign_{RSA}(h(M)) signRSA(h(M))代替 s i g n R S A ( M ) sign_{RSA}(M) signRSA(M)
- 密钥推导：由主key K K K推导keys K i = h ( K ∣ ∣ i ) K_i=h(K||i) Ki=h(K∣∣i)
- Bit commitment, predictions： h ( w h a t I k n o w ) h(what\ I\ know) h(what I know)
- 消息认证： h ( K ∣ ∣ M ) h(K||M) h(K∣∣M)
random oracle(RO)是将任意长度的消息映射为无限输出string。 支持的输入参数为 ( M , l ) (M,l) (M,l)，其中 M M M代表的是输入的消息， l l l代表希望的输出字符串的长度。 输出为 Z Z Z，为 l l l长度的字符串。是独立且均匀分布的字符。 random oracle的输出是自洽的，即相同的输入，对应相同的输出。
random oracle没有internal collisions。
3. tranditional construction——Merkle-Damgård
f
f
f被称为
b
b
b-bit排列函数（同时也为extendable output function(XOF)），
b
=
r
+
c
b=r+c
b=r+c，其中的
r
r
r为bits of rate，
c
c
c为bits of capacity(security parameter)。
sponge函数又可称为海绵函数，主要分为两个阶段：
- absorbing 吸收阶段。对应该阶段的为hash碰撞。
- squeezing 挤压阶段。对应该阶段的为周期性output。
论文 《Sponge functions》中sponge函数等的定义如下： 
参考资料： [1] Sponge functions [2] Introduction to sponge-based cryptography Part 1: Keccak and SHA-3 [3] Cryptographic sponge functions [4] 博客Fiat-Shamir heuristic（含实现）和Random oracle
