Worst-case to average-case reduction

Worst-case to average-case reduction is a proof technique that shows: if a computational problem is hard in the worst case, then a related problem is hard on average. Such reductions are rare and valuable because they allow cryptographic schemes to base their security on worst-case hardness assumptions — which are more robust than average-case assumptions — while still guaranteeing that random instances are hard.

The classical example is the connection between the \'\'\'Shortest Vector Problem\'\'\' (worst-case) and \'\'\'Learning With Errors\'\'\' (average-case), proved by Regev in 2005. Regev showed that an algorithm that solves LWE on average can be converted into an algorithm that solves approximate SVP in the worst case. This means that breaking LWE-based cryptography would require solving a lattice problem that is hard even in the worst case — a much stronger guarantee than mere average-case hardness.

For \'\'\'NP-complete\'\'\' problems, worst-case to average-case reductions are not known to exist. This is one of the central open problems in theoretical computer science: does worst-case hardness imply average-case hardness for NP? A positive answer would transform cryptography, allowing cryptographic schemes based on any NP-hard problem. A negative answer would mean that average-case hardness is a genuinely stronger assumption than worst-case hardness.

From a systems perspective, worst-case to average-case reductions are \'\'\'trust bridges\'\'\'. They connect the abstract world of complexity theory (where we prove things about worst-case hardness) to the practical world of cryptography (where we need guarantees about random instances). Without such bridges, cryptography rests on conjectures about average-case distributions that are harder to justify than worst-case assumptions.