From Orientations to $\ell$-adic Period Vectors

1. Il Problema e il Contesto

Il lavoro si inserisce nel campo della crittografia post-quantum, in particolare nello studio delle curve ellittiche supersingolari e dei grafi di isogenia. Sebbene schemi come CSIDH, OSIDH e SQISign abbiano dimostrato la fattibilità di primitive crittografiche basate su isogenie, la ricerca di nuove assunzioni di difficoltà (hardness assumptions) e strutture matematiche alternative rimane cruciale.

Il problema centrale affrontato dall'autore è la creazione di un ponte computazionale tra:

1. La struttura aritmetica e combinatoria delle curve ellittiche supersingolari orientate (rappresentate da classi di ideali in ordini di campi quadratici immaginari).
2. L'analisi armonica e topologica delle curve modulari, in particolare attraverso i simboli modulari e gli integrali $\ell$-adici.

L'obiettivo è definire un problema computazionale nuovo, chiamato Modular Symbol Inversion (MSI), che possa servire come fondamento per primitive crittografiche (come identificazione, firme digitali e PRF), offrendo una struttura diversa ma concettualmente affine ai problemi di cammino sui grafi di isogenia e ai problemi reticolari (SIS/LWE).

2. Metodologia

L'approccio proposto segue una pipeline algebrico-analitica che trasforma dati aritmetici discreti in vettori numerici $\ell$-adici.

A. Orientamenti e Classi di Ideali

L'autore parte da una curva ellittica supersingolare $E$ su un campo di caratteristica $p$, dotata di un orientamento $\iota: \mathcal{O} \hookrightarrow \text{End}(E)$, dove $\mathcal{O}$ è un ordine in un campo quadratico immaginario $K$.

• Le curve orientate sono parametrize dal gruppo delle classi di ideali $\text{Pic}(\mathcal{O})$.
• L'azione di una classe di ideali $[a] \in \text{Pic}(\mathcal{O})$ su una curva orientata $(E_0, \iota_0)$ produce una nuova curva $(E_a, \iota_a)$ tramite un isogeno definito dall'ideale.
• Questo processo è modellato geometricamente come un cammino sul grafo di isogenia orientato, che è un sottografo dell'albero di Bruhat-Tits associato a $\text{PGL}_2(\mathbb{Q}_\ell)$.

B. Mappatura in Omologia Relativa (Simboli Modulari)

Il passo cruciale è associare a ogni classe di ideali (e quindi a ogni curva orientata) una classe di omologia nella curva modulare $X_0(N)$.
L'autore propone tre costruzioni equivalenti (a meno di indice finito) per ottenere una classe $\gamma([a]) \in H_1(X_0(N), \mathcal{C}; \mathbb{Z})$, dove $\mathcal{C}$ è l'insieme dei punti di cuspide:

1. Modulo di Brandt: Utilizzando la corrispondenza di Jacquet-Langlands per mappare l'azione del gruppo di classi su moduli di ideali quaternionici in un'azione omologica su $X_0(N)$.
2. Punti di Heegner: Costruendo cicli geometrici tramite cammini tra punti di moltiplicazione complessa (CM) sulla curva modulare analitica.
3. Cocicli Armonici: Utilizzando l'uniformizzazione di Cerednik-Drinfeld e l'omologia del grafo finito $\Gamma \backslash \mathcal{T}_\ell$.

Queste costruzioni definiscono un omomorfismo $\rho: \text{Pic}(\mathcal{O}) \to \text{Aut}(H')$, dove $H'$ è un sottolattice stabile rispetto agli operatori di Hecke dell'omologia relativa.

C. Vettori di Periodi $\ell$-adici

Una volta ottenuta la classe di omologia $\gamma$, l'autore calcola i suoi periodi $\ell$-adici.

• Si fissa una base di forme cuspali di peso 2, $f_1, \dots, f_d \in S_2(\Gamma_0(N))$.
• Si utilizza l'integrazione di Coleman (un metodo di integrazione p-adica su curve) per calcolare i pairing $\langle f_i, \gamma \rangle_\ell$.
• Il risultato è un vettore troncato modulo $\ell^m$:
  $$\Pi_m(\gamma) = (\langle f_1, \gamma \rangle_\ell, \dots, \langle f_d, \gamma \rangle_\ell) \pmod{\ell^m} \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$$
  Questo vettore è computabile in modo efficiente senza necessitare di un modello algebrico esplicito della curva modulare, sfruttando le espansioni q delle forme modulari.

3. Il Problema di Inversione dei Simboli Modulari (MSI)

Il cuore della proposta crittografica è il problema MSI (Modular Symbol Inversion):

• Input: Un vettore troncato $y \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$ che è noto essere il risultato $\Pi_m(\gamma_*)$ di una classe di omologia "breve" $\gamma_*$.
• Definizione di "Breve": Una classe $\gamma$ è considerata breve se può essere rappresentata come somma di un numero limitato $L$ di generatori elementari (es. spigoli nell'albero di Bruhat-Tits o simboli di Manin), ovvero $\gamma = \sigma_{i_1} + \dots + \sigma_{i_L}$.
• Obiettivo: Trovare qualsiasi classe breve $\gamma$ tale che $\Pi_m(\gamma) = y$.

Analisi della Difficoltà:

• Lo spazio delle classi brevi cresce esponenzialmente con la lunghezza $L$ (fattore di diramazione $B$), mentre lo spazio di output ha dimensione $\ell^{md}$.
• Il problema è diverso da SIS (Short Integer Solution) perché la matrice del sistema lineare è altamente strutturata (deriva da periodicità modulari) e lo spazio delle soluzioni ammissibili è un sottoinsieme sparso e combinatorialmente vincolato (cammini validi).
• Non esistono riduzioni note a problemi reticolari classici o a problemi di cammino su grafi di isogenia, rendendo MSI un'assunzione di difficoltà indipendente.

4. Risultati e Contributi Chiave

1. Costruzione del Ponte: L'autore formalizza rigorosamente la mappa da curve supersingolari orientate a vettori di periodi $\ell$-adici, dimostrando l'equivalenza di tre approcci costruttivi (Brandt, Heegner, Bruhat-Tits).
2. Definizione di MSI: Viene introdotto un nuovo problema computazionale che combina algebra lineare su campi finiti con la complessità combinatoria dei cammini su grafi esponenziali.
3. Primitive Crittografiche: Vengono delineati schemi basati su MSI:
   • Protocollo di Identificazione: Simile a Schnorr, basato sulla difficoltà di invertire la mappa dei periodi per un cammino segreto.
   • Pseudorandom Functions (PRF): Costruzione di funzioni pseudo-casuali iterando la mappa dei periodi su cammini derivati da stringhe di input.
4. Analisi dei Parametri: Vengono forniti criteri per la selezione dei parametri ($p, N, \ell, m, L$) per garantire la sicurezza contro attacchi classici (forza bruta, meet-in-the-middle) e quantistici (algoritmo di Grover). Si suggerisce di usare $\ell \in \{3, 5\}$ per l'efficienza computazionale e $N$ sufficientemente grande per massimizzare la dimensione del vettore di periodo $d$.

5. Significato e Implicazioni

• Nuova Direzione Crittografica: Questo lavoro apre una nuova strada nella crittografia post-quantum, spostando l'attenzione dai grafi di isogenia puri (dove i vertici sono curve) a strutture ibride che coinvolgono l'omologia delle curve modulari.
• Robustezza Teorica: La difficoltà del problema MSI non dipende dalla struttura specifica del grafo di isogenia, ma dalla complessità intrinseca di invertire una mappa lineare su un dominio combinatorio esponenziale. Questo offre una diversificazione rispetto agli attacchi noti su CSIDH o SQISign.
• Efficienza Computazionale: L'uso dell'integrazione di Coleman permette di calcolare i period vector direttamente dai dati modulari, evitando la costruzione di modelli algebrici complessi, il che è vantaggioso per implementazioni pratiche.
• Stato Attuale: Il lavoro è presentato come una proposta esplorativa. Le primitive crittografiche sono in fase di studio e richiedono un'analisi più approfondita delle proprietà di distribuzione dei periodi e della resistenza ad attacchi strutturali specifici.

In sintesi, il paper propone un framework teorico solido per trasformare problemi di cammino su grafi aritmetici in problemi di inversione di vettori periodici $\ell$-adici, offrendo un nuovo candidato promettente per la crittografia post-quantum basato su una struttura matematica ricca e finora poco sfruttata in ambito crittografico.