The aim of this course is to introduce the algebraic tools necessary for an understanding of coding theory and cryptography. Actual protocols and examples of implementation will also be presented.
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.
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
* L. Giuzzi, "Codici Correttori", Springer-Verlag Unitext 25 (2006)
* W. Stallings, "Cryptography and network security", Prentice Hall (2010)
* N.P. Smart, Cryptography: an introduction, Springer-Verlag (2013)
* A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, "Handbook of applied cryptography", CRC Press (2001)
* C. Swenson, "Modern Cryptanalysis", Wiley Publishing, Inc. (2008)
* G.V. Bard, "Algebraic Cryptanalysis", Springer-Verlag (2009)
* A. Joux, "Algorithmic cryptanalysis", CRC Press (2009)
* M.W. Baldoni, C. Ciliberto, G.M. Piacentini Cattaneo, "Aritmetica, Crittografia e Codici", Springer Verlag Unitext 24 (2006)
Suggested papers:
* the contents of
http://luca-giuzzi.unibs.it/corsi/2015-16/Brescia/Algebra_Codici_Crittog...
* R.A. Mollin, "RSA and Public-Key cryptography", CRC Press (2003)
* C.Cid, S.Murphy, M. Robshaw, "Algebraic aspects of the advanced encryption standard"
* C. Swenson, Modern Cryptanalysis, Wiley Publishing, Inc. (2008)
Public lecture
Oral exam or essay on a topic related to the course.
Further texts, references and papers shall be made available on the lecturer's personal web page