CODE SMOOTHING, UNIFORM DISTRIBUTIONS, AND APPLICATIONS

Abstract

This dissertation investigates the problem of approximating uniform distributions over Hamming spaces, with applications to secure communication, randomness extraction, and computational hardness reductions. The central technique used in this study is code smoothing, which involves applying additive noise to a uniformly random codeword, producing an output distribution that closely approximates uniformity. We characterize the code rate thresholds required to achieve strong uniformity guarantees, quantified using R{\'e}nyi divergence. Our results show that random linear codes, as well as structured families like Reed-Muller and LDPC codes, are highly effective at smoothing. Building on these code families, we develop practical and effective coding schemes for use in wiretap channel settings.

We also study uniformity guarantees achievable through hash functions, using techniques closely related to code smoothing.In particular, we show that certain classes of linear and $k$-universal hash families provide strong uniformity guarantees, quantified by R{\'e}nyi divergence. This enables the extraction of uniform distributions to meet modern cryptographic requirements that impose stringent security guarantees.

We further apply smoothing techniques to investigate cryptographic reductions, with a focus on the computational hardness of the Learning Parity with Noise (LPN) problem---a foundational problem in lightweight cryptography. While prior work has explored reductions from the decoding problem to LPN to establish its hardness, our work sharpens this connection by delineating the parameter regimes where such reductions are viable, thus clarifying both the possibilities and the limitations of this approach.

Together, these contributions demonstrate how smoothing serves as a unifying analytical tool across coding theory, cryptography and computer science enabling both practical constructions and theoretical insights.