Computational cryptography › Hashes and symmetric ciphers
Hardness assumption

Block cipher / PRF security

In plain words

The assumption that a cipher like AES scrambles data so well that it looks random to anyone without the key.

The idea: A block cipher like AES takes a key and a 16-byte block and returns a scrambled block. The bet is that, without the key, its outputs look like those of a truly random function. That's what makes encryption work: run the cipher on a counter (1, 2, 3...) to get a random-looking stream and mix it into your data. If the stream had any pattern, the pattern would leak into the data.

Why it matters: Protects nearly all data sent over the internet and stored on disks.

The details

On the map: AES ≈ random permutation ChaCha20 ≈ random function

The assumption that AES behaves like a random permutation[1], and ChaCha20 like a random function[2], to anyone without the key.

It isn't provable, but rests on decades of cryptanalysis: the best attacks on full AES barely beat brute force[3]. Grover's algorithm halves the effective key length in theory, so 256-bit keys are recommended for the long term.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (7 boxes)

References

  1. NIST. Advanced Encryption Standard (AES). NIST FIPS 197, 2001. doi:10.6028/NIST.FIPS.197
  2. Daniel J. Bernstein. ChaCha, a variant of Salsa20. SASC 2008. cr.yp.to/chacha/chacha-20080128.pdf
  3. Andrey Bogdanov, Dmitry Khovratovich and Christian Rechberger. Biclique Cryptanalysis of the Full AES. Advances in Cryptology – ASIACRYPT 2011. doi:10.1007/978-3-642-25385-0_19