Seminars at Unicampania

Title: Cercare la chiave che non esiste: NP, coNP e crittografia

La possibile uguaglianza tra le classi di complessità NP e coNP è uno dei più grandi problemi aperti della teoria della complessità. In questo seminario divulgativo (in italiano) spiegherò con esempi semplici ma rigorosi il senso di questa uguaglianza, con enfasi sulle sue applicazioni nella teoria dei polinomi e, soprattutto, nella crittografia.

Title: Continuously Non-Malleable Codes: A Tutorial

Non-malleable codes (Dziembowski, Pietrzak, Wichs, ICS10) allow to encode a message into a codeword in such a way that limited tampering against the codeword either yields the original message or a completely unrelated value. Continuous non-malleability further strengthen the above in the setting where the attacker can carry multiple tampering attacks.

In this talk, I will review the main definitions and constructions of continuously non-malleable codes, highlighting their applications to cryptography.

Title: Crittoanalisi per difenderci dai ransomware

In questo seminario, rivolto principalmente a studenti di  matematica e informatica, riassumo il ruolo della  crittografia nei ransomware. 

I ransomware sono attacchi informatici che puntano  (tra le altre cose) a cifrare documenti nei computer delle vittime, rendendoli inutilizzabili. 

L’unico modo per recuperare i documenti originali è  pagare il riscatto ”ransom” ai cyber criminali, che  restituiscono (forse)  la chiave di decifratura. 

Sebbene molto diffusi, i ransomware sono soggetti a  vincoli pratici che si riflettono sulle proprietà matematiche degli algoritmi crittografici che usano. Queste proprietà possono talvolta essere dedotte e sfruttate per decrittare i file senza piegarsi al ricatto. 

Completerà il seminario un accenno alla mia esperienza  personale in questo campo.

Title: Rank-metric Lattices -- slides 

Higher-Weight Dowling Lattices (HWDL in short) are special families of geometric lattices introduced by Dowling in connection with coding theory. The elements of HWDLs are the F_q-linear subspaces of F_q^n having a basis of vectors with Hamming weight bounded from above, ordered by inclusion. These lattices were further studied, among others, by Bonin, Kung, and more recently by Ravagnani.

In this talk, we define and investigate structural properties of the q-analogues of HWDLs, which we call rank-metric lattices (RML in short). Their elements are the F_q^m-linear subspaces of F_{q^m}^n having a basis of vectors with rank weight bounded from above, ordered by inclusion. We determine which RMLs are supersolvable and compute their characteristic polynomials. In the second part of the talk, we establish a connection between RMLs and the problem of distinguishing between inequivalent rank-metric codes.

The new results in this talk are joint work with A. Ravagnani.

Title: Rank-metric codes with high degree of symmetry -- slides 

Rank-metric codes are linear spaces of matrices over a field, endowed with the metric induced by the rank. Their study was initiated by Delsarte, who originally introduced rank-metric codes for a purely combinatorial interest. It is only in 2008 that these codes raised the interest of coding theorist, due to their application in network coding proposed by Silva-Kschischang-Koetter. Since then, the theory of rank-metric codes has exponentially grown, bridging researchers in mathematics, engineering and computer science.

In this talk, I will focus on rank-metric codes with restrictions, starting from symmetric ones. Over fields of characteristic different from 2, symmetric matrices can be identified with degree 2 homogeneous polynomials. This allows us to view symmetric rank-metric codes as living inside the space of such polynomials. I will show how to extend the study of symmetric rank-metric codes to higher degree of symmetry. One can equip the space of homogeneous polynomials of degree d with the metric induced by the essential rank, which is the minimal number of linear forms needed to express a polynomial. In this context, I will outline a generalized construction of symmetric Gabidulin codes to polynomials of degree d over field of characteristic 0 or larger than d.

This is a joint work with Arthur Bik.

Title: Lectures on “Eigenvalue techniques in graph theory” -- notes

In this talk we will discuss eigenvalue bounds in algebraic graph theory with an emphasis on how to apply them in the context of finite geometry. The goal is to give complete proofs of these bounds. A familiarity with linear algebra and some basic notions of graph theory will be assumed, but no background in algebraic graph theory is required.

We will start by proving the expander mixing lemma. Then we will discuss how it can be applied to prove some results in projective planes, which can often also be proven through purely combinatorial arguments. Next we will discuss some more advanced tools to calculate the eigenvalues of graphs. This leads us to the theory of association schemes. We will show how eigenvalue bounds can surpass purely combinatorial arguments in some more complicated graphs than those coming from association schemes.

Title: On the non-existence of Cameron-Liebler sets of k- spaces in PG(n,q)

See the link.

Title: A graph co-spectral to NO+(8,2)

The graph NO+(8,2) is a strongly regular graph with parameters (120,63,30,36). In their recent book, Brouwer and Van Maldeghem mention the existence of a non-isomorphic, strongly regular graph with the same parameters, admitting Sym(7) as automorphism group. In this talk we discuss a geometric construction of this alternative graph. This is joint work with Sam Adriaensen, Robert Bailey and Morgan Rodgers.

Title: Skew polynomial rings and their applications