Structure vs. Hardness Through the Obfuscation Lens
Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of structured (mostly algebraic) problems like factoring, discrete log or finding short lattice vectors. While structure is perhaps what enables advanced applications, it also puts the hardness of these problems in question. In particular, this structure often puts them in low complexity classes such as \({\textsf {NP}} \cap {\textsf {coNP}}\) or statistical zero-knowledge (SZK).