Lattice-based cryptography leverages Euclidean lattices (and carefully-applied "noise") to construct secure cryptographic primitives. In recent years, these primitives have become quite practical (and academically popular), yielding a large number of variant schemes that are mild variants on the same core construction(s).
First, we introduce a relaxed notion of security for a cryptographic primitive that we call (c,s)-bit security. This parameterizes security with a (standard, computational) security parameter c, as well as a statistical security parameter s, and seems well-adapted for summarizing the concrete hardness of problems that contain both computationally-hard and statistically-hard components. We pair this with the notion of distinguishing advantage of aborting adversaries (Micciancio and Walter, Eurocrypt 2018), and characterize optimal adversaries in this setting.
Next, we propose a framework for the design of lattice-based encryption, parameterized by two coding-theoretic objects. We show that one can instantiate many lattice-based cryptosystems with compact ciphertexts in our framework, and show there are fundamental limits on the ciphertext size for cryptosystems built within our framework.
Finally, we show that one may harden the approximate FHE scheme of Cheon, Kim, Kim, and Song (Asiacrypt 2017) against the passive attacks of Li and Micciancio (Eurocrypt 2021), via applying an appropriate notion of differential privacy. Here, we find that to achieve (c,s)-bit security, the overhead of our countermeasure scales entirely with s (which may plausibly be set lower than c). We show that our countermeasure's overhead is nearly optimal, by arguing that instantiating it with smaller overhead yields an insecure scheme. Finally, we investigate another proposed countermeasure that lacked a proof of security, and show simple attacks against it.
