Blog · Collection
Cryptography
Provable security: pseudorandom functions, symmetric encryption and MACs, number theory and public-key cryptography, signatures, random oracles, interactive proofs and elliptic curves.
Modern cryptography replaces “it looks hard to break” with proofs: a scheme counts as secure if breaking it would mean solving a problem believed to be hard.
Symmetric cryptography
A pseudorandom function is a keyed function that no efficient adversary can tell apart from a truly random function. From it one can build encryption that stays secure against chosen-plaintext attacks, because each message is encrypted with fresh randomness and equal messages give different ciphertexts. One can also build message authentication codes that make forgery infeasible. Combining the two in the right order, encrypt-then-MAC, gives authenticated encryption.
Number theory and public keys
Finite fields and modular arithmetic supply the hard problems: factoring large integers, behind RSA, and computing discrete logarithms, behind Diffie–Hellman key exchange and ElGamal encryption. There is a practical side too: how fast the best known attacks are, and therefore how long keys need to be for a given level of security. Elliptic curves provide groups in which discrete logarithms are harder still, so much shorter keys give the same security.
Signatures, random oracles and proofs
Digital signatures let anyone verify who signed a message. Many practical schemes are proved secure in the random oracle model, which treats a hash function as a truly random function; that is a useful but idealized assumption. Interactive proofs, including zero-knowledge proofs, let one party convince another that a statement is true without revealing why. Unconditional, information-theoretic security, as in the one-time pad, needs no hardness assumptions at all, but it requires keys as long as the messages.