Keep updating :)

1.1 Cryptographic Hash Functions

It's a function: f(x) --> y
There are several properties of the input x, the output y, and the hash function f().

Input x

1. any string as input

Output y

1. fixed-size output

The hash function f

1. efficiently computable
2. collision-free: if x and y are not the same, then f(x) != f(y). However, the collision happens, why? Because the number of the possible input is much large than the possible output of the hash function f(). The pigeonhole principle!. No hash function is proven to be collision-free. So, we usually assume that our hash is collision-free.
3. hiding: Given y (which is obtained from f(x)), we are not able to know what x is.
4. puzzle friendly: no solving strategy is much better than trying random values of x

SHA-256 Hash Function: We skip the introduction of this function and will introduce it in a new blog.

1.2 Hash Pointers and Data Structures

Hash pointer

1. pointer to where some information is stored, and
2. (cryptographic) hash of the info

if we have a hash pointer, we can:

1. ask to get the information back
2. verify if the if information hasn't changed

1.3 Digital Signatures

1. Only you can sign, but anyone can verify
2. signature is tied to a particular document --> cannot be cut-and-pasted to another doc.

How to make it happen? There are three API:

1. (sk, pk) := generateKeys(keysize) ---> sk: secret signing key; pk: public verification key
2. signature := sign(sk, message)
3. isValid := verify(pk, message, siganature)

Any requirements of signatures?

1. ``valid signatures verify'' --> verify(pk, message, sign(sk, message)) == true
2. `` "can't forge signatures" --> adversary who: knows pk gets to see signatures on messages of his choice can't produce a verifiable signature on another message.