Hash functions: H: M -> T where |M| » |T| that is space of messages is larger than space of the hash. Hash function H is collision-resistant if it is hard to find the collision of H. For example, SHA-256 maps long strings to 256-bit hashes. Sign - σ signature = sign(Sk, m) Verify - verify(Pk, m, σ) outputs “yes”/“no”