Serving Every Symbol: All-Symbol PIR and Batch Codes

Titolo: Serving Every Symbol: All-Symbol PIR and Batch Codes

Autori: Avital Boruchovsky, Anina Gruica, Jonathan Niemann, Eitan Yaakobi.
Data: Aprile 2026 (preprint arXiv).

---

1. Il Problema e il Contesto

Il lavoro si inserisce nel campo della teoria dei codici correttori, con un focus specifico sulle applicazioni nello storage distribuito e nel recupero privato delle informazioni (PIR - Private Information Retrieval).

• Contesto Esistente: Le "Batch Codes" (codici batch) e le "PIR Codes" sono state introdotte per gestire richieste multiple di dati in modo efficiente.
  • Un codice PIR standard richiede che ogni simbolo informativo possa essere recuperato da $t$ insiemi disgiunti di server.
  • Un codice Batch richiede che un multiset di $t$ simboli informativi distinti possa essere recuperato da $t$ insiemi disgiunti.
• Il Gap di Ricerca: Le definizioni tradizionali si concentrano sulla recuperabilità dei simboli di informazione (i dati originali). Tuttavia, in scenari reali di storage e crittografia, è spesso necessario recuperare non solo i dati originali, ma anche i simboli del codice (i simboli memorizzati sui server), che sono combinazioni lineari dei dati originali.
• Obiettivo del Paper: Introdurre e studiare le versioni "All-Symbol" (per tutti i simboli) di questi codici.
  • t-All-Symbol PIR (ASP): Ogni simbolo del codice (non solo quelli di informazione) deve essere recuperabile da $t$ insiemi disgiunti.
  • t-All-Symbol Batch (ASB): Ogni multiset di $t$ simboli del codice (qualsiasi combinazione di simboli codificati) deve essere recuperabile da $t$ insiemi disgiunti.

L'obiettivo principale è determinare la lunghezza minima del codice ($n$) necessaria per soddisfare queste proprietà date la dimensione $k$ (numero di simboli di informazione) e il parametro di recupero $t$, nonché analizzare le proprietà strutturali di tali codici.

---

2. Metodologia

Gli autori adottano un approccio che combina algebra lineare, teoria dei codici e combinatoria:

1. Definizioni Formali: Vengono definiti rigorosamente i concetti di ASP e ASB utilizzando matrici generatrici $G \in \mathbb{F}_q^{k \times n}$. Un codice soddisfa la proprietà se, per ogni lista di $t$ vettori (rappresentanti i simboli richiesti), esistono $t$ sottoinsiemi disgiunti di colonne di $G$ che generano tali vettori.
2. Proprietà di Invarianza: Viene dimostrato (Lemma 3) che la proprietà di essere un codice ASP o ASB è intrinseca al codice stesso e non dipende dalla specifica matrice generatrice scelta (invariante rispetto a trasformazioni lineari invertibili).
3. Analisi Asintotica e Bound: Vengono derivati limiti inferiori e superiori per la lunghezza ottima $n$ in funzione di $k$ e $t$, utilizzando disuguaglianze combinatorie e proprietà dei codici duali.
4. Costruzioni Esplicite: Per piccoli valori di $t$ (in particolare $t=3$ e $t=4$), vengono costruite matrici generatrici specifiche (spesso basate su matrici sistematiche con colonne di parità) per dimostrare l'esistenza di codici ottimali.
5. Studio di Famiglie Classiche: Vengono analizzati codici noti come Codici MDS (Maximum Distance Separable) e Codici Simplex per verificare quanto bene soddisfino le nuove proprietà ASP/ASB e confrontare i risultati con congetture aperte.

---

3. Contributi Chiave e Risultati

A. Determinazione della Lunghezza Minima

Gli autori risolvono parzialmente il problema della lunghezza minima $n$ per piccoli valori di $t$:

• Casi Triviali:
  • Per $t=1$: $n = k$ (matrice identità).
  • Per $t=2$: $n = k + 1$ (matrice identità con una colonna di parità globale).
• Caso $t=3$:
  • Viene dimostrato che per $t=3$, le proprietà ASP e ASB coincidono.
  • La lunghezza ottima è data da $n = k + r$, dove $r$ è il più piccolo intero tale che $\binom{r}{2} \geq k$.
  • La costruzione utilizza una matrice sistematica $(I_k | A)$, dove le righe di $A$ sono vettori di peso 2 distinti.
• Caso $t=4$:
  • Vengono forniti limiti stretti. Per campi di caratteristica dispari ($q$ dispari), la lunghezza è compresa tra $k + 1 + r$ e $k + 2 + r$ (dove $r$ è definito come per $t=3$).
  • Per campi binari ($q=2$) e specifici valori di $k$, viene dimostrata l'uguaglianza con il limite inferiore.
  • Viene mostrato che la relazione nota per i codici batch standard ($B(k,4,2) = P(k,4,2) + 1$) non si estende direttamente al caso "All-Symbol" per tutti i parametri, richiedendo talvolta più ridondanza.

B. Proprietà Strutturali e Limiti

• Relazione con la Distanza Duale: Vengono stabiliti limiti superiori per $t$ basati sulla distanza minima del codice duale $d^\perp$. In particolare, per un codice ASP, vale $t \leq \lfloor \frac{n-1}{d^\perp - 1} \rfloor + 1$.
• Codici MDS: Per i codici MDS, la proprietà ASP è soddisfatta con $t = \lfloor \frac{n-1}{k} \rfloor + 1$, raggiungendo il limite teorico.
• Codici Simplex: Viene analizzato il codice Simplex binario di dimensione $k$ e lunghezza $n=2^k-1$.
  • Si dimostra che il codice Simplex è un codice batch funzionale per $t = 2^{k-1}$.
  • Viene fornita ulteriore evidenza a supporto della Congettura 2 (da [1]), che afferma che il codice Simplex è un codice batch funzionale per $t = 2^{k-1}$. In particolare, si dimostra che il codice può servire qualsiasi lista di $2^{k-1}$ simboli se i vettori richiesti sono linearmente indipendenti.

C. Confronto con Codici Esistenti

• Viene mostrato che i codici "All-Symbol" sono una generalizzazione più forte dei codici PIR e Batch tradizionali.
• Per $t=3$, i codici ASP/ASB coincidono con i codici PIR/Standard Batch ottimali.
• Per $t \geq 4$, i codici All-Symbol richiedono generalmente una lunghezza maggiore rispetto alle loro controparti standard, evidenziando il costo della recuperabilità universale di tutti i simboli del codice.

---

4. Significato e Implicazioni

1. Unificazione Teorica: Il lavoro unifica diverse famiglie di codici precedentemente studiati separatamente, inclusi i codici decodificabili con logica maggioritaria in un passo (one-step majority-logic decodable codes) e i codici con proprietà di riparazione disgiunta (DGRP).
2. Applicazioni Pratiche:
   • Storage Distribuito: Garantisce che qualsiasi dato memorizzato (anche dati intermedi o parità) possa essere recuperato in modo robusto e parallelo, migliorando la tolleranza ai guasti e il bilanciamento del carico.
   • PIR (Private Information Retrieval): Estende la privacy e l'efficienza ai simboli del codice stesso, non solo ai dati grezzi, cruciale per protocolli crittografici avanzati.
3. Avanzamento della Congettura Aperta: Il contributo più significativo nella teoria dei codici è il progresso verso la risoluzione della congettura sul codice Simplex come codice batch funzionale, fornendo nuovi casi risolti e una comprensione più profonda delle proprietà di recupero dei codici classici.
4. Direzioni Future: Il paper delinea chiaramente le sfide rimanenti, tra cui la caratterizzazione esatta per $t \geq 4$ e l'analisi del comportamento asintotico al crescere di $k$ e $t$, oltre all'influenza della dimensione dell'alfabeto $q$.

In sintesi, questo articolo stabilisce le fondamenta per una nuova classe di codici "All-Symbol", fornendo limiti ottimali, costruzioni esplicite e collegamenti teorici profondi con problemi aperti nella teoria dei codici, con un impatto diretto sull'efficienza e l'affidabilità dei sistemi di storage moderni.