Optimal Codes and Entropy Extractors

In this work we deal with both Coding Theory and Entropy Extraction for Random Number Generators to be used for cryptographic purposes. We start from a thorough analysis of known bounds on code parameters and a study of the properties of Hadamard codes. We find of particular interest the Griesmer bound, which is a strong result known to be true only for linear codes. We try to extend it to all codes, and we can determine many parameters for which the Griesmer bound is true also for nonlinear codes. In case of systematic codes, a class of codes including linear codes, we can derive stronger results on the relationship between the Griesmer bound and optimal codes. We also construct a family of optimal binary systematic codes contradicting the Griesmer bound. Finally, we obtain new bounds on the size of optimal codes. Regarding the study of random number generation, we analyse linear extractors and their connection with linear codes. The main result on this topic is a link between code parameters and the entropy rate obtained by a processed random number generator. More precisely, to any linear extractor we can associate the generator matrix of a linear code. Then, we link the total variation distance between the uniform distribution and the probability mass function of a random number generator with the weight distribution of the linear code associated to the linear extractor. Finally, we present a collection of results derived while pursuing a way to classify optimal codes, such as a probabilistic algorithm to compute the weight distribution of linear codes and a new bound on the size of codes.