Average-case versus worst-case complexity of computation
Ajay Nerurkar, Jin‐Yi Cai · 1999
Two natural notions of hardness of computational problems are worst-case hardness which measures how hard the hardest instance of a problem is, and average-case hardness which is a measure of how hard it is to solve a randomly given instance. While the former is the more traditional notion, it might be argued that it is the latter that truly captures the complexity of the problem. From a cryptographic viewpoint too, it is the average-case complexity that is important. This dissertation studies the connection between the two notions of complexity for specific problems, particularly ones involving lattices. The most important such problem is the Shortest Vector Problem (SVP): Given a lattice, compute a shortest non-zero vector in it. We improve upon a result of Miklos Ajtai who proved that the average-case hardness of this problem over a certain class of lattices was equivalent to the worst-case hardness of other lattice problems. Since these latter problems are thought to be hard in the worst-case, this says that the SVP on that class is hard on average. This is significant for the security of a future cryptosystem based on the SVP. We also present a worst-case hardness result for the SVP, proving that it is NP-hard to find an approximately short vector in a given lattice. A graph-theoretic application of lattices is also shown. The graphs considered are called circulant graphs and the problem is to find a shortest loop in such a graph. With every circulant graph is associated a lattice and finding a shortest loop in the graph is the same as finding a shortest vector in the lattice. This enables us to apply lattice techniques to study the complexity of this problem. Finally, moving away from lattices, we show that a hierarchy exists for a probabilistic complexity class under certain hardness assumptions. The assumptions are worst-case, but for a hierarchy theorem to be proved, average-case hardness is required. We make use of standard techniques to effect the conversion. This once again underlines the usefulness of a connection between these two kinds of computational complexity.