Intro to Crypto and Cryptocurrencies

Bitcoin

1.1 Cryptographic Hash Functions

i. Hash Function

The first cryptographic primitive that we will need to understand is a cryptographic hash function.A hash function is a mathematical function with the following three properties:

1. Its input can be any string of any size.
2. It produces a fixed size output. For the purpose of making the discussion in this chapter concrete, we will assume a 256-bit output size. However, our discussion holds true for any output size as long as it is sufficiently large.
3. It is efficiently computable. Intuitively this means that for a given input string, you can figure

ii. Security Properties

（a）Collision-resistance

Collision-resistance: A hash function $H$ is said to be collision resistant if it is infeasible to find two values, $x$ and $y$, such that $x ≠ y$, yet $H(x) = H(y)$.

（b）Hiding

A hash function $H$ is hiding if: when a secret value $r$ is chosen from a probability distribution that has high min-entropy, then given $H \left(r | x \right)$ it is infeasible to find $x$.

（c）Puzzle-Friendly

A hash function $H$ is said to be puzzle-friendly if for every possible n-bit 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 in time significantly less than $2$

1.2

#

#

#