This course is focused on information theory and its applications. Information theory is the basis of any modern ICT discipline and in this course the students will learn key concepts on how to measure, compress, elaborate, store, and transmit it. Important applications to algorithms for statistical inference and cryptography will be presented, too. The course will cover the theoretical background, algorithm development and software implementations.

At the end of the course, the students will know the fundamental concepts of Information theory and some key applications. They will have a clear knowledge of the concept of information source entropy measuring the information content of any source. They will learn the basic elements of source coding and the principles of many important algorithms used by all modern data compression techniques. They will know the most important results on channel capacity, which are at the basis of all modern communication systems. They will know crypto-information theory and the key concepts of enciphering, authentication, and integrity, along with some of the most important modern enciphering algorithm including RSA, AES/DES, and Blowfish/Twofish. They will become familiar with several fundamental algorithms, scuch as Viterbi and belief propagation, which have important applications to statistical inference, machine learning, artificial intelligence and decoding. Moreover, they will have the ability of implementing efficient software realization of key algorithms like the Huffman encoding for source coding, the Blahut-Arimoto algorithm for capacity computation, the Viterbi and decision tree algorithm for statistical inference, and homomorphic encryption to privacy preserving analytics.

Key notions from probability theory.

Information Theory 1. Entropy of discrete random variables (15 hours) o Information source o Information content and measure o Entropy and relevant inequalities o Entropy rate of a source o Markovian source o Laboratory: - Computation of entropies - Test of entropy inequalities - Computation of entropy rates 2. Source coding (13 hours) o Fixed-length encoding o Fixed-to-variable length encoding o Source code classification o Kraft inequality o McMillan theorem o Shannon theorem for source codes o Huffman codes o Laboratory: - Efficiency of Huffman codes 3. Discrete channels (12 hours) o Joint and conditional entropies o Mutual information o Entropy and mutual information inequalities o Laboratory: - Computation of conditional entropies and mutual information - Test of relevant inequalities o Markov chain o Data-Processing Inequality and its interpretation o Laboratory: - Verification of the data-processing inequality o Shannon theorem and the capacity of symmetric channels o Laboratory: - Computation of the capacity of a symmetric channel - Computation of the capacity of a discrete channel - Blahut-Arimoto algorithm and its implementation 4. Crypto-Information theory and wiretap channels (10 hours) o Perfect secrecy o One-time pad o Maurer cryptosystem o Unicity distance o Wiretap channel o Effective secrecy capacity o Laboratory: - Calculation of the effective secrecy capacity Applications 6. Algorithms for applied information theory (10 hours) o Viterbi algorithm o Belief propagation algorithm o Decision trees o Laboratory: - Basic Viterbi algorithm implementation - Decision tree algorithm implementation 7. Cryptosystems (10 hours) o Enciphering, authentication, integrity, attacks o Private key vs. Public key o Basic enciphering techniques o Laboratory: - Basic enciphering, frequency analysis attack 8. Algorithms for cryptography (10 hours) o Introduction to RSA o Notions of AES/DES, Blowfish/Twofish o Hash functions o Homomorphic encryption and applications to privacy preserving analytics o Laboratory: - Basic example of homomorphic encryption

The course will consist of 40 hours of lectures and 40 hours of Matlab laboratory where the students will implement and optimize the proposed algorithms.

• Course notes provided by the teachers • T.M. Cover and J.A. Thomas, Elements of Information Theory, Wiley, 2006 • El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011 • H. Delf and H. Knebl, Introduction to VCryptography (2nd ed.), Springer, 2006 • X. Yi et al, Homomorphic Encryption and Applications, Springer, 2014 • J. Hoffstein et al, An Introduction to Mathematical Cryptography, Springer, 2008

Modalità di esame: Prova scritta tramite PC con l'utilizzo della piattaforma di ateneo;

Questions are taken from a list available from the web site covering all the topics taught in the course. Grading considers precision, correctness, conciseness, completeness.

Modalità di esame: Test informatizzato in laboratorio; Prova scritta tramite PC con l'utilizzo della piattaforma di ateneo;

Questions are taken from a list available from the web site covering all the topics taught in the course. Grading considers precision, correctness, conciseness, completeness.