👋 Welcome to Theoreticles

In this post, we discuss an important class of algebraic structures known as $q$-ary lattices that are central to lattice-based cryptographic primitives. Hardness of problems Computational hardness usually revolves around problems with worst-case hardness guarantees since we want to design algorithms that run efficiently even on the worst possible input. On the other hand, cryptographic schemes require security guarantees for random keys. Therefore, cryptographic applications require problems with average-case hardness guarantees....

This post assumes basic familiarity with Turing machines, P, NP, NP-completeness, decidability, and undecidability. Don’t hesitate to contact me via email if you need further clarification. Without further ado, let’s dive in. Introduction Why do we need reductions? From Archimedes terrorizing the good folk of ancient Syracuse to Newton watching apples fall during a medieval plague, science has always progressed one ‘Eureka!’ at a time. Romantic as these anecdotes may be, for mathematics, we can hardly look to Mother Nature for providing us the key insight to our proofs....