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 (in aula); Progetto individuale;

Exam: Written test; Individual project;

... The course is divided in two parts: 1) Information Theory; 2) Applications. Each part of the course is assessed by two tests assessing the student’s knowledge of the topics presented in the course: 1. Written test on part 1 and on part 2 of the course. 2. Matlab project on part 1 and on part 2 of the course. The grade of each test will be obtained as a weighted average with weights 5/8 and 3/8 of the grades on part 1 and part 2, rounded to the nearest integer / 30. Here follows a detailed description of the two tests. 1. Written test. a) It consists of two or three questions (on each part of the course) selected from a list of questions available from the web site before the exam. The questions cover all the topics in each part of the course. The assessment will consider the correctness of the answers, the clarity and rigorousness of the development, and their exhaustiveness. The questions aim at assessing the knowledge on the topics listed in the course program. b) The typical overall duration is 1.5 hours, exceptionally extended to 2 hours in some cases. c) Students shall not use wireless devices of any kind. Books, notes, printed material, notebooks, tablets or any device or instrument capable of storing information, are also NOT ALLOWED. d) All grades are possible from 0/30 to 30/30. The overall grade of the written test is obtained as a weighted average with weights 5/8 and 3/8 of the grades on part 1 and part 2. 2. Matlab project. Individual Matlab projects are assigned to the students. The projects cover the topics presented in the course. The projects are sent by email to the institutional accounts of the students who cannot cooperate and must develop the program independently. Violations invalidate the test (any form of cheating will be reported to the discipline committee). Students must reply with a Matlab script from their institutional account to both teachers within the deadline (from three to six days according to the project complexity) specified in the email they have previously received. All grades are possible from 0/30 to 30/30. The overall grade of the Matlab projects is obtained as a weighted average with weights 5/8 and 3/8 of the grades on part 1 and part 2. Final grade. The final grade is calculated by averaging the grades proposed for the two parts of the exam. The "cum laude" grade is reserved for extraordinary performances only if both teachers agree to award it. Grades are proposed to the students over a limited time period. Students are allowed to accept or reject the proposed grade if the proposed grade is at least 18/30. Accepted grades are put on record.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.