Cryptanalysis reference

Notes on the attacks that public-key parameters are sized against. Each page says what the attack needs, what it costs, what the largest computation on record used, and when the attack stops applying. Every page cites the original papers, and those are the thing to read if you need precision.

How the pages are organised

Most published attacks don't break deployed systems. They improve an exponent, or need a structural coincidence that sensible parameters avoid, or assume an oracle nobody has. So the question each page tries to answer is what the attack would cost against a particular set of parameters, and what would have to change for that cost to become affordable.

Each page covers, in order:

Generic group algorithms

These work in any cyclic group where you can compute the group operation and test equality. Shoup's lower bound says no generic algorithm can use fewer than about √p operations, where p is the largest prime dividing the group order, so these algorithms set the baseline every discrete-log parameter is measured against.

Index calculus and descent

Index calculus collects relations over a factor base and solves a linear system. It is the reason discrete logarithms in finite fields take subexponential time. Whether anything like it works on elliptic curves has been an open question since Semaev's 2004 paper.

Lattice attacks

When a secret is partly known, from a few leaked bits, a biased nonce, or a small root of a modular equation, lattice reduction can often recover the rest. Many breaks of deployed ECDSA and RSA implementations come from this family rather than from any weakness in the underlying problem.

Isogeny attacks

Isogeny problems are the newest of these assumptions. SIKE was broken outright in 2022, after it had reached the fourth round of NIST's standardisation process, which is a good reason to read the attacks on its successors closely.