Seminari Passati:

• Dr. Emmanuela Orsini, COSIC, KU Leuven, Belgium, 08 Aprile 2021

Post-quantum secure oblivious transfer

Oblivious Transfer (OT) is a fundamental primitive in modern cryptography, that has been proved to be complete for both two-party and multiparty computation. It has been used as a building block in many cryptographic protocols and has a number of interesting applications.

In this talk, we start by introducing OT, giving some basic definitions, notion of security and showing some recent applications. Then, we will consider few OT constructions based on cryptographic assumptions that are supposed to be secure against post-quantum attacks.  We conclude with a discussion on their efficiency and security.

• Dr. Luca De Feo, IBM Zurich, 05 Maggio 2021

           La corrispondenza di Deuring effettiva – la chiave per la prossima generazione di crittografia basata sulle isogenie? 

Nel 1997, nel corso di un seminario alla Scuola Normale Superiore di Parigi (ENS Ulm), Jean-Marc Couveignes presentava un'idea tanto visionaria quanto incompresa: in un vasto tentativo di generalizzazione del problema del logaritmo discreto, egli (re)introduceva la nobile e venerata teoria della Moltiplicazione Complessa (CM) in crittografia. Il piano era audace: piuttosto che dannarsi a gestire l'ingestibile CM in caratteristica 0, come si era tentato fino ad allora in crittografia sulle curve ellittiche, Couveignes costruiva direttamente sui lavori di Deuring e Waterhouse che rendevano la CM effettiva in caratteristica positiva, attraverso algoritmi di calcolo d'isogenie. Piano talmente audace che cadde nell'oblio per due lustri.

Avanti-veloce ad oggi, l'algoritmo quantistico di Shor per il logaritmo discreto, lo sviluppo della crittografia post-quantistica, e la scoperta di algoritmi più efficaci per la CM effettiva hanno riportato le idee di Couveignes alla ribalta, rappresentate principalmente dal nuovo protocollo di scambio di chiave CSIDH e dai suoi derivati. Nel frattempo la crittografia a base d'isogenie ha avuto modo di svilupparsi anche in altre direzioni, sfruttando il formalismo dei grafi d'isogenie supersingolari ed i notevoli teoremi sui loro autovalori.

Ma i lavori di Deuring e Waterhouse hanno una portata che va al di là della CM, fornendo, come dimostrato da Kohel, Lauter, Petit e Tignol, una corrispondenza di categorie pressoché effettiva tra ordini massimali di algebre di quaternioni e curve supersingolari. In principio timidamente proposta come uno strumento per la crittanalisi, Galbraith, Petit e Silva furono i primi ad avere l'intuizione che la corrispondenza effettiva di Deuring (per le curve supersingolari, quindi) potesse servire come un'ulteriore generalizzazione delle idee di Couveignes. L'intuizione si è appena concretizzata in maniera spettacolare in SQISign, il protocollo di firma digitale post-quantistico più compatto conosciuto fino ad ora.

In questa presentazione spero di riuscire a presentare, in maniera semplice ed accessibile, la corrispondenza di Deuring effettiva, i suoi algoritmi e i suoi problemi ritenuti difficili, accompagnandola di riferimenti alle applicazioni crittografiche.

• Dr. Alessandro Neri, Max Planck Institute for Mathematics in the Sciences, Lipsia, 06 Ottobre 2021

Matrici Parziali e Polinomi non Commutativi nella Teoria dei Codici

La teoria algebrica dei codici può essere vista come la teoria dei sottospazi di un dato spazio metrico. Il caso più studiato è senza dubbio quello dei codici con la metrica di Hamming. In questa situazione, viene considerato un spazio vettoriale finito-dimensionale su un campo (finito) K, dove la distanza tra due vettori è data dal numero di entrate in cui essi differiscono. Negli ultimi decenni, l'attenzione di molti ricercatori si è spostata sui codici con la metrica del rango, ovvero sottospazi di matrici a coefficienti in un campo K, in cui la distanza tra due matrici è il rango della loro differenza.

Recentemente, una nuova metrica è diventata molto popolare: la metrica sum-rank. Lo spazio ambiente è fatto da tuple di matrici, e la distanza tra due tuple è misurata sommando i ranghi delle differenze delle rispettive matrici. Tuttavia, questi spazi metrici possono essere visti come casi particolari di un setting molto più generale, ovvero spazi di matrici in cui alcune entrate sono fissate uguali a zero.

In questo talk inizierò dando una prima overview storica su problemi e risultati analoghi trattati in letteratura, in diversi ambiti di ricerca. In seguito, presenterò un framework unificato che racchiude i diversi spazi metrici. In particolare, mostrerò come, sotto certe ipotesi sul campo di definizione, questi spazi metrici sono isometrici a dei particolari anelli di polinomi non commutativi. Infine, usando queste isometrie, costruirò spazi di matrici a blocchi in cui tutte le matrici non nulle hanno rango alto. Come conseguenza di queste costruzioni, si ottiene una nuova famiglia di codici MDS additivi nella metrica di Hamming.

• Dr. Ilaria Zappatore, INRIA Paris, Parigi, 03 Novembre 2021

 Diverse applicazioni della decodifica dei codici di Reed-Solomon nella versione classica e interleaved: uno sguardo al di lá della teoria dei codici

I codici di Reed-Solomon costituiscono una famiglia molto popolare e utilizzata di codici lineari: la loro struttura algebrica li conferisce delle importanti proprietá e permette la costruzione di diversi algoritmi di decodifica efficaci.

La costruzione di interleaving applicata a questi codici permette di correggere i cosiddetti errori "burst", errori sulle componenti consecutive del messaggio codificato. Inoltre permette di correggere una quantitá di errori che va al di lá della capacitá di correzione del codice.

In questo talk vedremo come le tecniche di decodifica efficace dei codici di Reed-Solomon e della loro versione interleaved, possono essere utilizzate in due scenari di applicazione che prescindono dalla teoria dei codici algebrici classica.

In particolare utilizzeremo alcune tecniche di decodifica dei codici di Reed-Solomon per calcolare il logaritmo discreto sui campi finiti, mediante l'index calculus, in un ambito piú prettamente crittografico.

Inoltre vedremo come utilizzare la decodifica dei codici di Reed-Solomon nella versione interleaved in un'applicazione piú legata alla computer algebra: per la risoluzione di sistemi lineari a coefficienti polinomiali su un campo finito in uno scenario di calcolo distribuito e parallelizzato.

Questo talk contiene dei risultati ottenuti in collaborazione con D. Augot, E. Guerrini, F. Morain e R. Lebreton.

• Dr. Martino Borello, Université Paris 8, Parigi, 02 Marzo 2022

Il principio di indeterminazione dal punto di vista della teoria dei codici

Il principio di indeterminazione è un risultato classico dell'analisi armonica che afferma che, data una funzione non nulla f su un gruppo abeliano, almeno una tra f e la sua trasformata di Fourier hanno un supporto grande (si veda per esempio [4]).

In [3], gli autori mostrano come questo principio, considerato su campi finiti, è strettamente legato al problema dell'esistenza di codici ciclici asintoticamente buoni, cioè ideali dell'algebra di gruppo KCn (dove Cn è un gruppo ciclico di ordine n) la cui dimensione su K e la distanza minima (di Hamming) sono funzioni lineari in n. Tale problema è considerato come uno dei più importanti problemi aperti nella teoria classica dei codici [1]. Nel seminario, presenteremo questi due problemi e la loro connessione, e poi discuteremo gli sviluppi più recenti (vedi [2]) e le prospettive future di ricerca.

[1] E. Assmus, H. Mattson, and R. Turyn. Cyclic codes, af cambridge research labs, bedford. Technical report, AFCRL-66-348, 1966.

[2] M. Borello and P. Solé. The uncertainty principle over finite fields. Discrete Mathematics, 345(1):112670, 2022.

[3] S. Evra, E. Kowalski, and A. Lubotzky. Good cyclic codes and the uncertainty principle. L’Enseignement Mathématique, 63(3):305–332, 2018.

[4] T. Tao. An uncertainty principle for cyclic groups of prime order. Mathematical Research Letters, 12(1):121–127, 2005.