Knowledge and understanding:
1) the constituent elements of the theory of automata, computability, complexity and cryptography;
2) the limits of the procedural-algorithmic approach;
3) conceptual elements of cryptography.
4) the main classes of complexity;
5) the key cryptographic protocols with secret and public key.

Applying knowledge and understanding:
1) be able to evaluate the undecidability of a problem;
2) be able to evaluate the complexity class of an algorithm;
3) be able to design a private and public cryptographic session.

Making judgements: Being able to apply the acquired knowledge to understand the key requirements for cryptographic security and computational complexity offered by an assigned project.

Communication skills: know how to expose problems and possible solutions associated with the computability, computational complexity and cryptographic context.

Learning skills: know how to gather information from textbooks and other material for the autonomous solution of problems related to the computability, computational complexity and cryptographic context

Bachelor degree in engineering, computer science, physics, mathematics.

AUTOMATA THEORY
Regular sets, deterministic and nondeterministic automata; regular expressions; transition graphs, pumping lemma and non regular languages; Kleene theorem; pushdown automata.
GRAMMARS
Classification of grammars, context-free grammars; Chomsky hierarchy
COMPUTABILITY THEORY
URM model. URM-computable functions; generation of computable functions by concatenation, substitution, recursion, limited and unlimited minimalization; Ackermann's function.
Gödel numbering, programs Gödelization, numbering of computable functions; Cantor diagonalization, existence of non computable functions, examples of non-computable functions; the s-m-n theorem, universal programs. Decidability and undecidability; undecidability and the halting problem, undecidability of 'Phi_x is total', 'Phi_x = 0', 'Phi_x = Phi_y', Rice's theorem, recursion and fixed point theorem.
Other approaches to computability: DNA computation, neural networks.
Notes on Gödel-Kleene model of partial recursive functions and primitive recursive functions; the Turing Machine (TM), equivalences between different TM models, contraction and extension of a TM, examples.
Equivalence between different computational models and Church-Turing thesis. Background on recursive sets and recursively enumerable sets.
COMPUTATIONAL COMPLEXITY
Polynomial algorithms and intractable problems, P and NP complexity classes, relation between P and NP class; reductions in polynomial time, the class of NP-complete problems, Cook theorem (notes), examples of NP-complete problems, the structure of the NP class.
CRYPTOGRAPHY
The Shannon cryptographic communication system; problems related to data security: interception, impersonation, data integrity violation.
Secret key encryption:
Substitution and transposition ciphers; nomenclators, homophonic ciphers, statistical cryptanalytic attacks, polyalphabetic and Vigenère cipher, the principle of confusion and diffusion, rotor machines, the problem of key exchange in a network of N users.
Shannon approach; pure ciphers, residual classes of messages and cryptograms, equivocations, fundamental inequality of encryption, ideal and perfect ciphers, ideality of transposition cipher, the perfected state, cipher weakening as a function of the cryptogram length, one-time pad cipher and its perfection, unicity distance and its calculation for different ciphers.
Block ciphers; DES, IDEA and AES.
Symmetric and asymmetric encryption, Shamir’s protocol, general principles of the digital signature.
Stream ciphers; random generators and random characters, pseudo-random generators and Golomb criteria, linear feedback shift registers as generators, linear complexity and known-plaintext attack, nonlinear registers, RC4.
Public key encryption:
one-way functions, the finite logarithm and the key exchange, partial sums and the knapsack cipher, RSA cipher, ElGamal cipher, Koblitz-Miller cipher on ellitpic curves. Data integrity and extracts, DES used as a hash function. Hash functions SHA256, MD5, RIPEMD160.
Message Authentication Codes (MAC), HMAC; Key Derivation Function: PBKDF2 e Bcrypt.
RSA and ElGamal digital signatures.
Recall on algebraic structures: groups, rings, fields. Esponentation and logarithms on finite fields.
Introduction to elliptic curves. Weierstrass firm, group structure of the curve. secp256k1 standard.
Identification schemes. Schnorr scheme. Schnorr Digital signature, DSA/ECDSA identification schemes.
DSA and ECDSA digital signatures, lengths of the keys, Curve25519 and Curve448 standards.

Lecture notes of the teacher
Nigel Cutland, Computability: An Introduction, Cambridge.
Michael Sipser, Introduction to the Theory of Computation, Thomson.
Zohar Manna, Mathematical Theory of Computation, McGraw-Hill Book Company.
Michael R. Garey and David S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman Ed.
F. Fabris, Teoria dell'informazione, codici, cifrari, Bollati Boringhieri.

AUTOMATA THEORY
Regular sets, deterministic and nondeterministic automata; regular expressions; transition graphs, pumping lemma and non regular languages; Kleene theorem; pushdown automata.
GRAMMARS
Classification of grammars, context-free grammars; Chomsky hierarchy.
COMPUTABILITY THEORY
URM model. URM-computable functions; generation of computable functions by concatenation, substitution, recursion, limited and unlimited minimalization; Ackermann's function.
Gödel numbering, programs Gödelization, numbering of computable functions; Cantor diagonalization, existence of non computable functions, examples of non-computable functions; the s-m-n theorem, universal programs. Decidability and undecidability; undecidability and the halting problem, undecidability of 'Phi_x is total', 'Phi_x = 0', 'Phi_x = Phi_y', Rice's theorem, recursion and fixed point theorem.
Other approaches to computability: DNA computation, neural networks.
Notes on Gödel-Kleene model of partial recursive functions and primitive recursive functions; the Turing Machine (TM), equivalences between different TM models, contraction and extension of a TM, examples.
Equivalence between different computational models and Church-Turing thesis. Background on recursive sets and recursively enumerable sets.
COMPUTATIONAL COMPLEXITY
Polynomial algorithms and intractable problems, P and NP complexity classes, relation between P and NP class; reductions in polynomial time, the class of NP-complete problems, Cook theorem (notes), examples of NP-complete problems, the structure of the NP class.
CRYPTOGRAPHY
The Shannon cryptographic communication system; problems related to data security: interception, impersonation, data integrity violation.
Secret key encryption:
Substitution and transposition ciphers; nomenclators, homophonic ciphers, statistical cryptanalytic attacks, polyalphabetic and Vigenère cipher, the principle of confusion and diffusion, rotor machines, the problem of key exchange in a network of N users.
Shannon approach; pure ciphers, residual classes of messages and cryptograms, equivocations, fundamental inequality of encryption, ideal and perfect ciphers, ideality of transposition cipher, the perfected state, cipher weakening as a function of the cryptogram length, one-time pad cipher and its perfection, unicity distance and its calculation for different ciphers.
Block ciphers; DES, IDEA and AES.
Symmetric and asymmetric encryption, Shamir’s protocol, general principles of the digital signature.
Stream ciphers; random generators and random characters, pseudo-random generators and Golomb criteria, linear feedback shift registers as generators, linear complexity and known-plaintext attack, nonlinear registers, RC4.
Public key encryption:
one-way functions, the finite logarithm and the key exchange, partial sums and the knapsack cipher, RSA cipher, ElGamal cipher, Koblitz-Miller cipher on ellitpic curves. Data integrity and extracts, DES used as a hash function. Hash functions SHA256, MD5, RIPEMD160.
Message Authentication Codes (MAC), HMAC; Key Derivation Function: PBKDF2 e Bcrypt.
RSA and ElGamal digital signatures.
Recall on algebraic structures: groups, rings, fields. Esponentation and logarithms on finite fields.
Introduction to elliptic curves. Weierstrass firm, group structure of the curve. secp256k1 standard.
Identification schemes. Schnorr scheme. Schnorr Digital signature, DSA/ECDSA identification schemes.
DSA and ECDSA digital signatures, lengths of the keys, Curve25519 and Curve448 standards.

Video-projector presenting the theoretical principles, in-class exercise. All lecture files and handouts are available on Moodle. All lectures are recorded and available in real time on the Teams platform

Link to Moodle:
https://moodle2.units.it/course/view.php?id=2959

Knowledge, understanding, and communication skills will be evaluated through an oral exam, held in front of a blackboard, and based on three main questions about the program being performed. The first question pertains to the theory of computation, the second to cryptography, and the third covers all remaining topics. The grade, including the possibility of honors (laude), is determined in a completely subjective manner, based on the teacher’s experience.
In any type of content produced by the student for admission to or participation in an exam (projects, reports, exercises, tests), the use of Large Language Model tools (such as ChatGPT and the like) must be explicitly declared. This requirement must be met even in the case of partial use.
Regardless of the method of assessment, the teacher reserves the right to further investigate the student's actual contribution with an oral exam for any type of content produced.