84235 - Information Theory and Cryptography (2nd cycle)

Learning outcomes

Fundamentals of Information Theory: entropy, source compression, channel capacity. Fundamental limits on the energy required for transmitting information. Error Correcting Codes. Coding for audio and video. Fundamentals of cryptology and security. Applications: wireless systems, satellite communication systems, information storage, sensor networks, cyber-physical systems, Internet of Things.

Course contents

Part I: Cryptography

Introduction. Main security targets: confidentiality, integrity, availability, authentication. Encryption, Channel, Decryption, Stream, Symmetric and asymmetric ciphering.

Elements of number theory. Euclidean division between integers. Algoriths for the computation of the remainder. Greater Common Divisor. Beuzeot's theorem. The Euclidean algorithm. Modular arithmetic and its rules. The discrete logarithm problem. Finite Fields. GF(p) when p is prime. Addition, multiplication, power in GF(p). Generator elements. GF(p^m): the field elements as polynomials. Irreducible polynomials, primitive polynomials. Generation of the field with irreducible polynomials. The field elements as powers of a primitive element modulus a primitive polynomial.

Confidentiality. Block cipher as a family of indexed bijections between sets. General brute-force attack: time needed as a function of the n. of keys. Example: permutation of the alphabet, plaintext composed of characters and cyclic shift (Caesar's cipher). Number of keys, implementation with mod operator. Substitution of the alphabet with a generic permutation. Number of keys. Attack by analysis of character frequencies. The Leon Battista Alberti’s cipher disk. The Vigenere chiper: number of keys, possible attacks when the length of the key is known, when it is not known. Stream cipher: example with streams of bits and ex-or with key. The ideal case: key length as the message length, key completely random (one-time pad). Case of key with finite length, periodically reused. Practical block cipher schemes: DES and AES.

The Diffie-Helmann key exchange: algorithm and weaknesses.

The RSA: algorithm and rigorous proof of correctness. Computational issues, generation of the keys.

The basic ideas for elliptic curves cryptography (EC).

Comparison among AES, RSA, DH, 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. The cryptography in the Transport Layer Security.

Part 2: Information Theory

Information, Uncertainty and Entropy. Entropy for Discrete Memoryless Sources. Source Coding. Mutual Information and Channel Capacity. Shannon's Theorem on Channel Coding. Capacity for Gaussian Additive Channels. The Hartley-Shannon Formula for the Band Limited Additive Gaussian Channel. Energy to noise spectral density ratio. Energy and spectral efficiency, minimum theoretical energy per transmitted bit.

Channel Coding. Decision theory: Maximum Likelihood and Maximum a Posteriori decoding. Linear Block Codes. Cyclic Codes. Convolutional Codes. The Viterbi algorithm. Coding for Correlated Channels: Interleaving. Punctured Codes. Concatenated Codes. Codes on Graphs and Iterative Decoding: Turbo Codes and LDPC Codes. Decoding with message passing and belief propagation algorithms.

Applications. Cryptography, error protection, and energy budget for transmission of information in Wireless Cellular Systems, Satellite Systems, Data Storage Systems, Wireless Sensor Networks, Cyber-Physical Systems, Internet of Things.

Readings/Bibliography

Lecture notes available on line.

More material can be found in:

T. M. Cover, J. A. Thomas, Elements of Information Theory, Wiley-Interscience, New York.

W. Stallings, Cryptography and Network Security, Pearson.

F. Stajano, Security for Ubiquitous Computing, Wiley.

Teaching methods

Lectures.
Computer experiments and programming in Matlab or C or Python.

Assessment methods

Written and Oral Examination.

Teaching tools

Personal computer

Office hours

See the website of Marco Chiani