The course provides an introduction to the basic mathematical instruments necessary to modern cryptography and coding theory. In particular, we shall provide the tools necessary to describe and investigate some of the most relevant symmetric and asymmetric cryptosystems and consider their application to actual problems like anonimity, confidentiality and authentication.
We shall also discuss the theory of linear error correcting codes (bounds, properties, encoding and decoding algorithms) and their applications, as well as introduce modern developments in the area of turbo and LDPC codes.
DETAILED PROGRAMME (and outline of the main topics)
An introduction to cryptography.
What is cryptography? Modern cryptography and protocols.
Attack models and security definitions; symmetric and public key cryptography.
Shannon's theorem on cryptography
Elements of group theory
Finite groups; subgroups; laterals and transversals; normal subgroups and homomorphisms; cyclic groups; Lagrange's theorem; DLOG
DLOG-based cryptography
Diffie-Hellman and basic cryptoanalysis. Authentication and signatures. The STS protocol.
ElGamal encryption; its properties and its cryptoanalysis.
Modular integers and a little number theory
The Euclidean algorithm and its extended variant. Congruences and modular arithmetic; Fermat's little theorem; Jacobi's symbol and Euler's function. Primality testing.
RSA and its variants
Some basic properties of RSA; the Chinese remainder theorem; some attacks.
Semantic security and IND-CPA; variants of RSA; OAEP
Euclidean domains and finite fields.
The extended Euclidean algorithm revisited; Euclidean domains; polynomial rings; finite fields.
From DES to AES
Feistel's architecture; DES and 3-DES; design criteria; linear and differential cryptoanalysis.
AES: construction and implementation; properties and analysis.
Elliptic curve cryptography.
Elliptic curves over finite fields; the group law and its implementation.
EC-based protocols and their realisation.
Bilinear pairing and key escrow.
Bilinear pairing between groups; applications and attacks; ID-based encryption; key-escrow
Zero knowledge and anonimity
What does zero knowledge mean? Protocols and applications.
Anonimity in a digital world; re-encryption, mixnets and onions. The e-voting problem.
Homomorphic encryption
Linear error correcting codes
A mathematical theory of communication and Shannon's theorem (on coding theory).
Error correcting codes; block codes; Hamming distance; linear codes; bounds and syndrome decoding.
Cyclic codes
Construction; encoding and decoding.
Reed-Solomon and BCH codes.
Construction; bounds; Welch-Berlekamp's algorithm. The Discrete Fourier Transform and its applications.
LDPC and turbo codes
A short introduction to Network coding