Seminari

Il ciclo di seminari del gruppo UMI è un'occasione per il gruppo UMI Crittografia e Codici per esporre i risultati del gruppo e poter conoscere la ricerca attuale sugli aspetti matematici, teorici e applicati, della crittografia e della teoria dei codici.

Gli eventi sono organizzati in collaborazione con De Cifris e, con il consenso dell'oratore, disponibili online.

Lista degli eventi in programma nell'anno 2021:

Seminari

  • 08 Aprile, ore 15h00 (Emmanuela Orsini, COSIC, KU Leuven, Belgium): Post-quantum secure oblivious transfer (slides)

  • 05 Maggio, ore 15h00 (Luca De Feo, IBM Zurich): La corrispondenza di Deuring effettiva – la chiave per la prossima generazione di crittografia basata sulle isogenie? (slides)

  • 09 Giugno, ore 16h00 (Alberto Ravagnani, Eindhoven University of Technology): Il Codice Tipico su un Grande Alfabeto (slides)

  • 07 Luglio, ore 16h00 (Roberto La Scala, Università di Bari Aldo Moro): Cifrari ad equazioni alle differenze (slides)

  • 21-22 Settembre : Convegno Annuale

  • 06 Ottobre, ore 16h00 (Alessandro Neri, Max Planck Institute for Mathematics in the Sciences, Lipsia): Matrici Parziali e Polinomi non Commutativi nella Teoria dei Codici (slides)

  • 03 Novembre, ore 16h30 (Ilaria Zappatore, INRIA Paris): Diverse applicazioni della decodifica dei codici di Reed-Solomon nella versione classica e interleaved: uno sguardo al di lá della teoria dei codici

  • 01 Dicembre, ore 16h00 (Daniele Bartoli, Università degli Studi di Perugia): Teoremi di tipo Hasse-Weil e classi rilevanti di funzioni polinomiali (slides)

  • 02 Febbraio, ore 16h00 (Irene Villa, Università degli Studi di Trento): The classification of planar monomials over fields of order a prime cubed (slides)

  • 02 Marzo, ore 16h00 (Martino Borello, Université Paris 8): Il principio di indeterminazione dal punto di vista della teoria dei codici (slides)

  • 06 Aprile, ore 16h00 (Marzio Mula, Università degli Studi di Trento): Random sampling of supersingular elliptic curves (slides)

  • 04 Maggio, ore 16h00 (Giovanni Zula, Università degli studi di Modena e Reggio Emilia): Funzioni Generalized APN in caratteristica dispari e curve algebriche

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.

Il Codice Tipico su un Grande Alfabeto

Abstract: In questo seminario discuterò le proprietà del codice correttore tipico su un alfabeto (generalmente un campo finito) sufficientemente grande. I risultati si concentrano su codici nella metrica di Hamming, nella metrica del rango, e nella metrica dei sottospazi. I risultati principali del seminario illustrano forti divergenze nel comportamento dei codici con buone capacità di correzione nelle tre metriche considerate. Ad esempio, mentre il tipico codice lineare nella metrica di Hamming e' ottimale (MDS), i codici ottimali lineari nella metrica del rango (MRD) sono particolarmente rari. Le tecniche impiegate per ottenere questi risultati si basano principalmente su teoria dei grafi e combinatorica estremale.


  • Prof. Roberto La Scala, Università degli Studi di Bari Aldo Moro, 07 Luglio 2021

Cifrari ed Equazioni alle Differenze

Molti cifrari a flusso o a blocchi di interesse applicativo quali sistemi di LFSR con combinatore (E0 di Bluetooth), Trivium, Keeloq, etc possono essere modellizzati come sistemi di equazioni esplicite alle differenze su campi finiti. Tali sistemi infatti determinano l'evoluzione nel tempo dei registri interni di questi "cifrari alle differenze''.

L'utilizzo della teoria formale delle equazioni alle differenze permette lo studio di alcune proprietà di questi cifrari, quali la loro invertibilità e periodicità. Queste proprietà sono essenziali alla corretta definizione di attacchi algebrici generali ai cifrari alle differenze e quindi alla stima della loro sicurezza. Tale modellizzazione e la corrispondente crittanalisi può permettere quindi lo sviluppo di nuovi cifrari applicabili.


  • 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.



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. Irene Villa, Università degli Studi di Trento, Trento, 02 Febbraio 2022

The classification of planar monomials over fields of order a prime cubed

In finite fields of odd characteristic, planar functions play an important role. They present a one-to-one connection with commutative semifields and they can be used to construct finite projective planes. Moreover, in cryptographic scenarios, they correspond to perfect nonlinear functions, providing an optimal resistance to linear and differential cryptanalysis when used in DES-like cryptosystems.

The Dembowski-Ostrom conjecture states that, up to adding constants or linear terms, the only planar functions over finite fields are necessarily DO polynomials, that are polynomials with only quadratic terms. This conjecture was proved true for polynomials over prime fields, for monomials over fields of square order and for monomials over fields of order p^4 with p>3. Instead, it was shown false for fields of characteristic 3, with the smallest counterexample being over the finite field with 3^4 elements. In this seminar, we fill a gap by giving a complete classification of planar monomials over fields of order p^3, establishing the DO conjecture in this case. The proof makes use of Hermite’s criteria to eliminate all potential exponents that are not DO exponents.

The result presented is a joint work with Robert Coulter and Emily Bergman.


  • 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.



  • Dr. Marzio Mula, Università degli Studi di Trento, Trento, 06 Aprile 2022

Random sampling of supersingular elliptic curves

Many isogeny-based cryptographic protocols make use of supersingular elliptic curves over finite fields of large characteristic. The classic method for uniformly sampling such curves combines the reduction of suitable CM curves and random walks. This strategy, though, has a major drawback which makes it unsuitable for cryptographic applications: the endomorphism ring of the output curve can be efficiently computed.

In this talk, we explain how the classic method works and why it reveals "too much" information about the output curve. We also investigate possible alternatives based on the Hasse invariant and division polynomials.


  • Dr. Giovanni Zini Università degli Studi di Modena e Reggio Emilia, Mercoledì 4 Maggio 2022


Funzioni Generalized APN in caratteristica dispari e curve algebriche


La nozione di funzione APN è stata recentemente generalizzata da Kuroda e Tsujie (2017) a quella di funzione Generalized APN (GAPN) su un campo finito di caratteristica p qualsiasi, richiedendo che la derivata discreta generalizzata in ogni direzione sia una mappa p-a-1. Presenterò alcune interessanti costruzioni di vari autori per funzioni GAPN, nonché una condizione sufficiente data da Ozbudak e Salagean (2021) per ottenere funzioni GAPN da polinomi di permutazione. Mostrerò inoltre condizioni necessarie (ottenute in collaborazione con Bartoli, Giulietti e Peraro) sotto le quali è possibile invertire il risultato di Ozbudak e Salagean. Questi ultimi risultati sono stati ottenuti dallo studio di particolari curve algebriche associate alla funzione.


Organizzatori:

Matteo Bonini, Eleonora Guerrini, Alessio Meneghetti, Giordano Santilli

contatti: seminariumi-cc@googlegroups.com