# Average case solve worst case problems In his seminal paper[^1], Ajtai constructed a set $A$ of instances of a problem such that if one can solve (with high probability) efficiently a random instance from $A$ - one can solve any instance from the set $B$ of another lattice problem. This means it can solve also the worst-case instances from $B$. As there is no known algorithm that solves the worst-case instances efficiently (although many smart people try to find efficient method for long time) - then we should have confidence that a random instance can't be solve efficiently. $ \boxed{ \begin{gathered} \begin{aligned} &\text{efficiently solve random instance from } A \end{aligned}\\ \Downarrow\\ \begin{aligned} &\text{efficiently solve every instance of } B \end{aligned} \end{gathered} } $ More specific, he showed that there is a class of lattices with their shortest vector that **IF** choosing a random instance of a lattice from this class, one can find the shortest vector (with positive probability) **THEN** any instance (including the worst case) of one of 3 hard lattice problems can be solved. The importance of this result is that before all cryptography schemes were based on the fact that breaking the scheme w.r.t specific scheme parameter allows to solve a worst-case instance of a problem. Choosing secured parameters and keys can be challenging as the relationship between the scheme and the underlining problem can be complex and require special expertise. Ajtai discovery provides a new kind of problem where any instance of it can be used securely for cryptography schemes. Related: [[Paper summary - Generating Hard Instances of Lattice Problems - Ajtai 1996]] ## Created 2026-10-09 13:16 [^1]: [[@Generating Hard Instances of Lattice Problems (Ajtai 1996)]]