The Length of Functional Batch and PIR Codes

Titolo: La Lunghezza dei Codici Batch e PIR Funzionali

Autori: Altan B. Kılıç, Alberto Ravagnani, Flavio Salizzoni
Affiliazioni: Eindhoven University of Technology (Paesi Bassi), Max Planck Institute for Mathematics in the Sciences (Germania).

1. Il Problema e il Contesto

Il lavoro si concentra sulla teoria dei codici per la Recupero Privato di Informazioni (PIR - Private Information Retrieval) e sui Codici Batch, generalizzati al caso funzionale.

• Contesto: In un database distribuito, un utente vuole recuperare dati senza rivelare al server quali dati specifici stia richiedendo. I codici PIR permettono di recuperare un singolo simbolo (o una funzione di esso) attraverso insiemi di recupero disgiunti. I codici Batch generalizzano questo concetto permettendo il recupero simultaneo di più simboli (o funzioni).
• Obiettivo: Determinare la lunghezza minima ($n$) di un codice lineare su un campo finito $\mathbb{F}_q$ di dimensione $k$, capace di servire una lista di $t$ vettori (o funzioni) non nulli.
• Parametri Chiave:
  • $k$: Dimensione del messaggio (numero di simboli di informazione).
  • $t$: Dimensione della richiesta (numero di vettori da recuperare simultaneamente).
  • $q$: Dimensione del campo finito ($\mathbb{F}_q$).
  • $n$: Lunghezza del codice (numero di nodi di memorizzazione).
• Funzioni Studiate:
  • $FP(k, t, q)$: Lunghezza minima per un codice PIR funzionale $t$.
  • $FB(k, t, q)$: Lunghezza minima per un codice Batch funzionale $t$.
  • Si ha sempre $FB(k, t, q) \geq FP(k, t, q)$.

La maggior parte della letteratura precedente si era concentrata esclusivamente sul caso binario ($q=2$). Questo paper estende l'analisi a campi finiti arbitrari ($q$ generico).

2. Metodologia

Gli autori adottano un approccio combinatorio e algebrico basato sulla teoria dei codici lineari e sulla geometria dei campi finiti:

1. Definizione Formale: Introducono la nozione di "insieme di recupero" (recovery set) e formalizzano quando una matrice generatrice può servire una lista di vettori.
2. Analisi Esatta per Parametri Specifici: Calcolano i valori esatti di $FB(k, t, q)$e$FP(k, t, q)$ per casi particolari (es. $k=2$, o $t$ multiplo di potenze di $q$).
3. Costruzioni di Matrici: Progettano matrici generatrici specifiche (spesso combinando matrici identità e colonne aggiuntive) per dimostrare limiti superiori.
4. Argomenti di Conteggio e Principio dei Cassetti: Utilizzano il principio dei cassetti (pigeonhole principle) per dimostrare limiti inferiori, analizzando la distribuzione dei vettori nelle colonne della matrice.
5. Analisi Asintotica: Studiano il comportamento delle funzioni quando $t \to \infty$ (con $k$ fissato) e quando sia $k$ che $t$ tendono all'infinito simultaneamente, utilizzando il Lemma di Fekete per le funzioni subadditive.

3. Contributi Chiave e Risultati

A. Valori Esatti e Generalizzazioni

• Caso $k=2$: Viene derivata una formula esatta per $FB(2, t, q)$ per qualsiasi $q$:
  $$FB(2, t, q) = \left\lceil \frac{2(q+1)t}{q+2} \right\rceil = t + \left\lceil \frac{qt}{q+2} \right\rceil$$
  Questo generalizza il risultato noto per $q=2$.
• Relazione tra PIR e Batch: Viene mostrato che per certi valori di $t$ (multiplo di $2^k$ nel caso binario), la lunghezza minima per i codici PIR e Batch coincide.
• Generalizzazione della Congettura di Zhang-Etzion-Yaakobi: La congettura originale (per $q=2$) afferma che il codice simplex $[k, 2^k-1]$ è un codice batch funzionale $2^{k-1}$. Gli autori generalizzano questo risultato a campi arbitrari, identificando il massimo $t$ tale che $FP(k, t, q) = q^k - 1$:
  $$FP\left(k, \frac{q^k + q - 2}{2}, q\right) = q^k - 1$$
  Viene inoltre proposto un problema aperto per generalizzare la lunghezza dei codici Batch per $t = q^k + q - 2$.

B. Limiti Superiori e Inferiori

• Limiti Generali: Vengono stabiliti limiti inferiori non banali che dipendono da $q$. Ad esempio, per $q \neq 2$:
  $$FB(k, t, q) \geq \frac{tk}{\log_{q-1}(t(q-1) + 1)}$$
• Comportamento per $q$ Grande: Se $q$ è sufficientemente grande (specificamente $q \geq \binom{kt}{k-1}$), la lunghezza minima è semplicemente $kt$, ovvero non c'è sovraccarico rispetto al caso di memorizzazione diretta.
• Asimmetria $k$ vs $t$: Viene dimostrato che $FB(k, t, q) \neq FB(t, k, q)$ in generale. In particolare, per $t$ molto grande rispetto a $k$, la lunghezza può essere significativamente diversa dal caso scambiato.

C. Comportamento Asintotico

• $t \to \infty$ (con $k$ fissato): Gli autori calcolano il limite del rapporto lunghezza/performance:
  $$\lim_{t \to \infty} \frac{FP(k, t, q)}{t} = \lim_{t \to \infty} \frac{FB(k, t, q)}{t} = \frac{2(q^k - 1)}{q^k + q - 2}$$
  Questo risultato è cruciale perché stabilisce il "costo" asintotico per ogni richiesta aggiuntiva in termini di nodi di storage.
• $k, t \to \infty$ simultaneamente: Viene mostrato che il rapporto normalizzato $FB(k, t, q) / (kt)$ tende a zero, indicando che l'efficienza del codice migliora all'aumentare delle dimensioni, ma con un tasso di crescita logaritmico specifico.

4. Significato e Implicazioni

1. Superamento del Caso Binario: Questo lavoro è fondamentale perché sposta l'analisi dei codici PIR e Batch dal dominio binario (dominante nella letteratura) a campi finiti arbitrari, offrendo strumenti per sistemi di archiviazione su campi più grandi (es. campi di Galois usati in crittografia o codici di correzione d'errore moderni).
2. Risoluzione Parziale di Congetture Aperte: Il paper fornisce prove parziali e generalizzazioni della "Functional Batch Conjecture", collegandola a problemi di matching in gruppi abeliani finiti.
3. Ottimizzazione dello Storage: I risultati forniscono limiti teorici precisi per progettare sistemi di archiviazione distribuita che garantiscono la privacy (PIR) e la capacità di recupero parallelo (Batch) con il minimo overhead di storage.
4. Nuovi Problemi Aperti: Il paper definisce nuovi problemi aperti, in particolare riguardanti la determinazione esatta di $FB(k, q^k + q - 2, q)$ e il comportamento esatto della funzione al variare di $q$.

In sintesi, il paper offre un quadro teorico completo e rigoroso per la lunghezza minima dei codici funzionali, generalizzando risultati noti, fornendo nuove formule esatte per casi critici e stabilendo il comportamento asintotico fondamentale per la progettazione di sistemi di recupero informazioni privati ed efficienti.