84235 - Information Theory and Cryptography (2nd cycle)

Learning outcomes

At the end of the course, students will know the fundamentals of information theory: entropy, compression, and the capacity of transmission channels. Theoretical analysis of the energy required for information transmission. Error-correcting codes for audio and video. Fundamentals of cryptology and communication security. Applications: wireless systems, satellites, data storage, sensor networks, cyber-physical systems, and the Internet of Things.

Course contents

The course is organized into two main parts: cryptography and information theory.

Part I: Cryptography

Introduction. Main security goals: confidentiality, integrity, availability, and authentication. Encryption, channel, decryption. Symmetric and asymmetric ciphers.

Elements of number theory. Euclidean division of integers. Algorithms for computing remainders. Greatest common divisor. Bézout’s theorem. Euclidean algorithm. Modular arithmetic and its properties. Discrete logarithm problem. Finite fields. GF(p), with p prime. Addition, multiplication, and exponentiation in GF(p). Generators. GF(p^m): representation of field elements as polynomials. Irreducible polynomials and primitive polynomials. Field generation using irreducible polynomials. Representation of field elements as powers of a primitive element modulo a primitive polynomial.

Confidentiality. Block ciphers as indexed families of bijections between sets. Exhaustive attack: required time as a function of the number of keys. Examples: alphabet permutation, plaintext consisting of characters and cyclic shift cipher, or Caesar cipher. Number of keys and implementation using the modulo operator. Alphabet substitution through a generic permutation. Number of keys. Attack based on character frequency analysis. Leon Battista Alberti’s cipher disk.

Vigenère cipher: number of keys, possible attacks when the key length is known and when it is unknown. Stream ciphers: example with bit streams and XOR operation with the key. Ideal case: key length equal to the message length and completely random, or one-time pad. Case of a finite-length key reused periodically. Practical block encryption schemes: DES and AES.

Diffie-Hellman key exchange: algorithm and vulnerabilities.

RSA: algorithm and rigorous proof of correctness. Computational aspects and key generation.

Basic concepts of elliptic-curve cryptography.

Comparison among AES, RSA, DH, and ECDH.

Integrity. Cryptographic hash functions. Message Authentication Code. Digital signatures.

Authentication: passwords, salting and hashing, one-time passwords.

Challenge-response. Man-in-the-middle attack.

Applications: cellular systems, WiFi. Cryptography in Transport Layer Security.

Part II: Information Theory

Information, uncertainty, and entropy. Entropy for discrete memoryless sources. Source coding. Mutual information and channel capacity. Shannon’s channel coding theorem. Capacity of additive Gaussian channels. Hartley-Shannon formula for the band-limited additive Gaussian channel. Ratio between energy per bit and noise spectral density. Energy efficiency and spectral efficiency. Theoretical minimum energy per transmitted bit.

Channel coding. Decision theory: maximum-likelihood and maximum a posteriori decoding. Linear block codes. Cyclic codes. Convolutional codes. Viterbi algorithm. Coding for correlated channels: interleaving. Punctured codes. Concatenated codes. Codes on graphs and iterative decoding: turbo codes and LDPC codes. Decoding through message-passing and belief-propagation algorithms.

Applications. Cryptography, error protection, and energy budget for information transmission in wireless cellular systems, satellite systems, data storage systems, wireless sensor networks, cyber-physical systems, and the Internet of Things.

Readings/Bibliography

Lecture notes made available online by the instructor constitute the main material for preparing the exam.

The following books are recommended for consultation and further study:

• T. M. Cover, J. A. Thomas, Elements of Information Theory, Wiley-Interscience, New York.
• W. Stallings, Cryptography and Network Security, Pearson.

Teaching methods

The course is organized into in-person lectures, during which the fundamentals of information theory and cryptography are presented. The theoretical treatment of the topics is accompanied by examples, the discussion of application-oriented problems, and the solution of exercises, with the aim of illustrating and highlighting the practical applications of the concepts introduced.

For some topics, computer experiments and programming activities in Matlab, C, or Python may also be discussed, with the aim of implementing and numerically evaluating methods and algorithms introduced during the course.

Assessment methods

Assessment will take place through a single two-hour written examination, aimed at assessing the achievement of the learning outcomes of the course. The examination consists of open-ended questions and exercises related to the topics covered during the course. During the examination, the use of books, notes, calculators, or other electronic devices is not allowed, except for any aids authorized as part of approved adjustments for students with specific learning disorders or disabilities.

The examination is aimed at assessing the students’ knowledge and understanding of the fundamentals of information theory and cryptography; their ability to apply the theoretical methods and mathematical tools presented during the course to the solution of specific problems; their autonomy of judgement in critically evaluating different solutions for the compression, coding, protection, and transmission of information; as well as their clarity of presentation and correct use of technical language. 

Excellent marks will be awarded to students who demonstrate an organic and in-depth knowledge of the topics covered, a strong ability to autonomously and critically apply the theoretical and methodological tools acquired, correctness in formulating and solving exercises, the ability to connect the different topics of the course, and full command of technical language.

Intermediate marks will be awarded to students who demonstrate correct but not fully in-depth knowledge of the contents, adequate but not always autonomous application skills, sufficient ability to connect the topics, and overall correct use of technical language.

A pass mark will be awarded to students who demonstrate essential knowledge of the topics and an ability to apply the acquired tools limited to simpler cases. Significant gaps in the knowledge of fundamental concepts, difficulties in applying methodological tools, errors in formulating or solving exercises, and inappropriate use of technical language will be assessed negatively.

No intermediate tests or assignments to be submitted before the examination are planned.

With regard to assessment, the use of generative Artificial Intelligence is not allowed. Any use of it constitutes a violation of academic integrity.

Students with specific learning disorders or temporary or permanent disabilities are advised to contact the relevant University office in good time, available at https://site.unibo.it/studenti-con-disabilita-e-dsa/en . The office will be responsible for proposing any necessary adjustments, which must in any case be submitted to the instructor for approval at least 15 days before the examination. The instructor will assess their suitability also in relation to the learning outcomes of the course.

Teaching tools

Teaching material: lecture notes and supplementary material will be made available to students in electronic format through the institutional repositories.

Software tools: computational environments and programming languages such as Matlab, C, or Python may be used for possible numerical experiments and programming activities.

Personal computer: the use of a personal computer may be useful for independently carrying out the numerical experiments and programming activities proposed during the course.

Office hours

See the website of Enrico Paolini