Skip to content

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.

Puncturable PRF [SW14]
Pseudo-random generator (PRG)

PRG security game

Pseudo-random permutation (PRP)
Time-Lock Puzzle (TLP) [RSW96]

This is a sort of time-locked commitment, which can be opened via some puzzle solving operation that takes at least time \(T\) (even up to parallelization, i.e., it solving a puzzle should be a sequential operation).

Existing constructions:

Compared to TLPs, time-lock encryption enables immediate/"automatic" decryption as soon as time \(T\) has elapsed (though of course one option for realizing this is to put the decryption key in a TLP and outsource the solving to a third party who will reliably publish the solution as soon as it is found).

Trapdoor function (TDF)

Construction: TDF from SIS