Other

Message authentication code (MAC)

One-way function (OWF)

In a way this is also an assumption, since we don't know of any function that is provably hard to invert.

Pseudo-random function (PRF)

A function that maps inputs to outputs so that the outputs appear randomly distributed. The function is deterministic in the sense that querying it on the same input always returns the same (random-looking) output.

PRF security game

Construction: PRF from PRG [GGM]

Given a length-doubling PRG \(G: \{0, 1\}^\lambda \rightarrow \{0,1\}^{2\lambda}\), we can construct a PRF \(F: \{0, 1\}^\lambda \times \{0,1\}^n \rightarrow \{0,1\}^\lambda\) which takes a \(\lambda\)-bit key \(k\) and \(n\)-bit input \(x\) and outputs a pseudorandom \(\lambda\)-bit value. The construction is described in this note. The idea is to construct a height-\(n\) tree of calls to \(G\) using \(k\) as the root. The output of \(F(k,x)\) is determined by following the path given by the bits of \(x\).

Moreover, this construction is in fact a puncturable PRF: we can puncture out points by removing the PRG seeds in the tree along the path to that point.

Pseudo-random generator (PRG)

PRG security game

Pseudo-random permutation (PRP)

Time-Lock Puzzle (TLP)

Trapdoor function (TDF)

Construction: TDF from SIS