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.

Optimal Codes and Entropy Extractors / Meneghetti, Alessio. - (2017), pp. 1-182.

### Optimal Codes and Entropy Extractors

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
29
Mathematics
Sala, Massimiliano
Inglese
Settore MAT/02 - Algebra
File in questo prodotto:
File
DECLARATORIA_ENG.pdf

Solo gestori archivio

Tipologia: Tesi di dottorato (Doctoral Thesis)
Dimensione 275.63 kB
AM_thesis.pdf

Solo gestori archivio

Tipologia: Tesi di dottorato (Doctoral Thesis)
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11572/368164`
• ND
• ND
• ND