Week One - Introduction to Crypto and Cryptocurrencies

Hash function

Takes any string as input
fixed-size output (e.g. 256bits just as BitCoin)
efficiently computable

Security properties:

Nobody can find x and y such that x!=y and H(x)=H(y)

Note: Collisions do exist. The possible outputs is finite(string of 256 bits in size), while the possible inputs can be a string of any size.

To find a collision of any hash function: Trying randomly chosen inputs and chances are 99.8% that two of them will collide. Well, it takes too long to matter.
For some possible H’s, there’s a faster way to find collisions; for others, we haven’t known yet. No H has been proven collision-free.

If r is chosen from a probability distribution that has high min-entropy, then given H(r|x), it is infeasible to find x.
High min-entropy means that the distribution is “very spread out”, so that no particular value is chosen with more than negligible probability.

For every possible output value y, if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k|x)=y.


Hash as message digest.
If we know H(x)=H(y), it’s safe to assume that x=y.
To recognize a file that we saw before, just remember its hash.
It’s useful because the hash is small.

Want to “seal a value in an envelope”, and “open the envelope” later.
Commit to a value, reveal it later.

(com, key) := commit(msg)
match := verify(com, key, msg)

To seal msg in envelope:
(com, key) := commit(msg) — then publish com
To open envelope:
publish key, msg
anyone can use verify() to check validity

Security properties:
Hiding: Given com, infeasible to find msg.
Binding: Infeasible to find msg != msg' such that verify(commit(msg), msg') == true.

Search Puzzle
Given a “puzzle ID” id (from high min-entropy distribution) and a target set Y,
try to find a “solution” x such that H(id|x)∈Y.
Puzzle-friendly property implies that no solving strategy is much better than trying random values of x.


Hash Pointer

Hash pointer is pointer to where some info is stored, and (cryptographic) hash of the info.
If we have a hash pointer, we can ask to get the info back, and verify that it hasn’t changed.

Data structure of blockchain:

This is blockchain, and it’s similar to linked list.
If some adversary wants to change a block’s data(e.g., the left one), then the content of that block is changed. And the middle block’s hash pointer is not consistent to the left block any more. So the adversary has to change middle block’s header, and next block’s header and so on.

Digital Signature

sig:=sign(sk, message)
isValid:=verify(pk, message, sig)

Requirements for signatures
·Valid signatures verify
·Can’t forge signatures