Abstract

In the first part of this thesis we report results about some “linear” trapdoors that can be embedded in a block cipher. In particular we are interested in any block cipher which has invertible S-boxes and that acts as a permutation on the message space, once the key is chosen. The message space is a vector space and we can endow it with alternative operations (hidden sums) for which the structure of vector space is preserved. Each of this operation is related to a different copy of the affine group. So, our block cipher could be affine with respect to one of these hidden sums. We show conditions on the S-box able to prevent a type of trapdoors based on hidden sums, in particular we introduce the notion of Anti-Crooked function. Moreover we shows some properties of the translation groups related to these hidden sums, characterizing those that are generated by affine permutations. In that case we prove that hidden sum trapdoors are practical and we can perform a global reconstruction attack. We also analyze the role of the mixing layer obtaining results suggesting the possibility to have undetectable hidden sum trapdoors using MDS mixing layers. In the second part we take into account the index coding with side information (ICSI) problem. Firstly we investigate the optimal length of a linear index code, that is equal to the min-rank of the hypergraph related to the instance of the ICSI problem. In particular we extend the the so-called Sandwich Property from graphs to hypergraphs and also we give an upper bound on the min-rank of an hypergraph taking advantage of incidence structures such as 2-designs and projective planes. Then we consider the more general case when the side information are coded, the index coding with coded side information (ICCSI) problem. We extend some results on the error correction index codes to the ICCSI problem case and a syndrome decoding algorithm is also given.