💻 computer science

From Bits to Mixed-Radix Keys: Horner Decomposition, Uniform Sampling, and the Information-Theoretic QKD Interface of the MR-OTP

Questo articolo stabilisce un quadro pratico e teoricamente sicuro dal punto di vista dell'informazione per convertire l'entropia binaria grezza da sorgenti di Distribuzione Quantistica delle Chiavi in chiavi a base mista uniformi per il One-Time Pad a Base Mista, utilizzando il metodo di Horner per la mappatura, il campionamento per rifiuto per eliminare il bias e rigorose dimostrazioni di sicurezza ed efficienza.

Autori originali: Fabio F. G. Buono

Pubblicato 2026-06-19

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Fabio F. G. Buono

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il Quadro Generale: Un Nuovo Tipo di Serratura "Inviolabile"

Immaginate di voler inviare un messaggio segreto. Il gold standard per la segretezza è il One-Time Pad (OTP). Pensate a questo come a una serratura in cui la chiave è una sequenza casuale di numeri lunga esattamente quanto il vostro messaggio. Se la chiave è veramente casuale e non viene mai riutilizzata, il messaggio è matematicamente impossibile da decifrare, indipendentemente dalla potenza del computer che tenta di romperlo.

Tuttavia, i tradizionali OTP hanno un difetto: parlano solo "Binario" (0 e 1). Se volete inviare una lettera come "A" (che è naturalmente un simbolo, non uno 0 o 1), dovete prima tradurla in binario. Questa traduzione spreca spazio ed è inefficiente.

Questo articolo introduce il Mixed-Radix One-Time Pad (MR-OTP). Pensate a questo come a una serratura che parla la lingua nativa dei vostri dati.

Se state inviando del DNA (4 lettere), la serratura usa un dado a 4 facce.
Se state inviando un testo in inglese (26 lettere), usa un dado a 26 facce.
Se state inviando numeri (10 cifre), usa un dado a 10 facce.

Questo articolo risolve il problema pratico di come costruire questa serratura utilizzando una macchina a Distribuzione Quantistica di Chiavi (QKD), che produce solo un flusso di 0 e 1.

Il Problema Centrale: Il "Taglio Grezzo" della Casualità

L'Analogia:
Immaginate di avere una macchina che sputa fuori lanci di dadi perfetti e giusti a 6 facce (0–5). Ma la vostra serratura richiede un dado a 7 facce (0–6).

L'Errore Naif: Potreste pensare: "Prenderò un lancio a 6 facce, aggiungerò 1 e, se ottengo un 7, lo farò ricominciare da 0".
Il Problema: Questo crea un "bias" (distorsione). Alcuni numeri (come 0 e 1) apparirebbero più spesso di altri (come 6). Nel mondo della perfetta segretezza, anche un minimo bias è come lasciare una fessura aperta nella porta. Rovina la garanzia di "inviolabilità".

La Soluzione del Documento:
Gli autori propongono una rigorosa regola di "Rejection Sampling" (Campionamento per Rifiuto).

La macchina genera un numero.
Se il numero rientra nel vostro intervallo a 7 facce, lo tenete.
Se è troppo grande (ad esempio, avete ottenuto un 7 o un 8), lo scartate e riprovate.
Ripetete finché non ottenete un numero valido.

Questo assicura che ogni numero da 0 a 6 abbia esattamente la stessa probabilità di essere scelto. Il documento dimostra che questo metodo è abbastanza efficiente da essere pratico, sprecando pochissimi bit del flusso quantistico.

Il Tocco Magico: "Il Metodo di Horner"

Come si trasforma una lunga stringa di bit binari (provenienti dalla macchina quantistica) in un set specifico di lanci di dadi a basi miste (ad esempio, un dado a 7 facce, uno a 13 facce, uno a 5 facce)?

L'Analogia:
Pensate a una matrioska nidificata o a un set di istruzioni per costruire una torre.

Avanti (Costruzione): Iniziate con la prima cifra, moltiplicatela per la dimensione del dado successivo, aggiungete la cifra successiva, moltiplicatela per la dimensione del dado successivo, e così via. Questo è chiamato Metodo di Horner. È un trucco matematico intelligente per impacchettare numeri di diverse dimensioni in un unico grande intero.
Indietro (Scompattamento): Per recuperare le chiavi, fate l'opposto. Prendete il numero grande, dividetelo per la dimensione dell'ultimo dado per ottenere il resto (l'ultima chiave), poi dividete il risultato per la dimensione del dado successivo, e così via.

Il documento dimostra che questo processo di "impacchettamento e scompattamento" è una corrispondenza perfetta, uno-a-uno. È il ponte algebrico che permette di trasformare un flusso di 0 e 1 in un set perfetto e non distorto di chiavi a base mista.

La Garanzia di Sicurezza: "Lo Scudo a Due Strati"

Il documento affronta una domanda inquietante: E se un hacker scoprisse la "forma" dei dadi (la sequenza di basi) che stiamo usando?

Gli autori dimostrano uno "Scudo a Due Strati":

Strato 1: La Forma è Nascosta (Computazionalmente Difficile).
Se l'hacker non sa che stiamo usando un dado a 7 facce o un dado a 13 facce, deve indovinare. Il documento mostra che indovinare la sequenza delle dimensioni dei dadi è incredibilmente difficile, specialmente se l'hacker vede solo il messaggio criptato (ciphertext) senza il testo originale. Infatti, se vedono solo il ciphertext, è matematicamente impossibile conoscere affatto le dimensioni dei dadi.
Strato 2: La Chiave è Inviolabile (Informazionale/Teorica).
Anche se l'hacker scopre le dimensioni dei dadi (la "forma"), non può comunque leggere il messaggio. Perché? Perché la chiave effettiva (i numeri casuali lanciati su quei dadi) viene generata ex novo per ogni messaggio.

L'Analogia: Immaginate che l'hacker scopra che state usando un dado a 26 facce. Ottimo per lui! Ma non sa ancora quale numero (A–Z) avete lanciato per questo specifico messaggio. Poiché il lancio era veramente casuale e non è mai stato riutilizzato, conoscere la dimensione del dado non gli dice nulla sulla lettera.

La Grande Conclusione: La sicurezza del messaggio non dipende dal fatto che l'hacker sia troppo lento nel indovinare le dimensioni dei dadi. Anche se indovinassero le dimensioni istantaneamente, il messaggio rimarrebbe perfettamente segreto perché la chiave è casuale.

Efficienza: Risparmiare Spazio

Il documento evidenzia anche un piacevole effetto collaterale.

Vecchio Modo (OTP Binario): Per inviare una lettera "A" (1 di 26), dovete usare 5 bit (poiché $2^5 = 32$ ). Sprecate 6 bit di spazio perché 32 è maggiore di 26.
Nuovo Modo (MR-OTP): Utilizzate esattamente lo spazio necessario per 26 opzioni.
Il Risultato: Su milioni di messaggi, questo risparmia una enorme quantità di "materiale di chiave" (i bit casuali necessari dalla macchina quantistica). È come fare le valigie: il vecchio modo vi costringeva a usare una scatola gigante per una piccola maglietta; il nuovo modo usa una scatola che si adatta perfettamente alla maglietta.

Sintesi delle Rivendicazioni

Come convertire: È possibile trasformare i bit casuali quantistici in chiavi a base mista usando un metodo di "rifiuto e riprova" combinato con un trucco matematico chiamato decomposizione di Horner.
Nessun Bias: Questo metodo crea una chiave perfettamente uniforme, che è necessaria per la garanzia di "inviolabilità".
Sicurezza End-to-End: L'intero processo (Macchina Quantistica $\to$ Conversione $\to$ Crittografia) è matematicamente dimostrato come inviolabile.
A Prova di Futuro: Anche se un supercomputer del futuro riuscisse a indovinare istantaneamente le "dimensioni dei dadi" (la sequenza di basi), i messaggi rimarrebbero sicuri perché le chiavi sono fresche e casuali.
Efficienza: Risparmia spazio rispetto ai tradizionali metodi binari, specialmente per i linguaggi naturali e i dati biologici.

Il documento non afferma che questo sia un prodotto commerciale pronto per la vendita oggi, né afferma di risolvere tutti i problemi crittografici. Dimostra rigorosamente le basi matematiche e gli algoritmi necessari per far funzionare questo specifico tipo di "perfetta segretezza" con l'hardware quantistico reale.

Sintesi Tecnica: Dai Bit alle Chiavi a Radice Mista

Enunciato del Problema
Il One-Time Pad a Radice Mista (MR-OTP), introdotto in un lavoro precedente [1], generalizza il classico One-Time Pad binario a spazi di cifre con basi non uniformi. Esso consente la codifica nativa di alfabeti di dati eterogenei (ad es., sequenze di DNA, testo latino) senza conversione binaria intermedia, preservando al contempo la perfetta segretezza di Shannon. Tuttavia, un dispiegamento pratico richiede un meccanismo per convertire l'output di entropia binaria grezza di una sorgente di Distribuzione Quantistica delle Chiavi (QKD) in una tupla di chiavi uniformemente distribuita sullo spazio delle chiavi a radice mista.

Un approccio ingenuo — leggere $k = \lceil \log_2 P \rceil$ bit (dove $P$ è il prodotto delle basi) e ridurre l'intero risultante modulo $P$ — introduce una distorsione statistica nota come "bias del modulo". Nell'ambito dell'informazione teorica, qualsiasi non-uniformità nella distribuzione della chiave viola l'ipotesi del teorema della perfetta segretezza, rendendo il sistema insicuro indipendentemente dall'entità del bias. Il documento affronta la sfida algoritmica di convertire un flusso binario uniforme in una tupla di chiavi a radice mista uniforme senza introdurre questo bias, mantenendo al contempo la sicurezza informazionale end-to-end.

Metodologia
Il documento stabilisce un'equivalenza strutturale tra i pesi posizionali a radice mista e la forma annidata della valutazione polinomiale.

Corrispondenza Algebrica: Gli autori identificano il metodo di Horner e il suo inverso come la canonical dualità algebrica per questa conversione. La mappa diretta (valutazione di Horner) compone una tupla di cifre in un singolo intero, mentre la mappa inversa (decomposizione di Horner inversa) recupera le cifre da un intero tramite successiva riduzione modulare. Ciò stabilisce una biiezione tra lo spazio delle chiavi $\mathcal{K}$ e l'intervallo di interi $\{0, \dots, P-1\}$ .
Campionamento per Rifiuto (Rejection Sampling): Per eliminare il bias del modulo, il documento propone un algoritmo di campionamento per rifiuto (Algoritmo 1). L'algoritmo estrae $k$ bit per formare un intero $V$ . Se $V \ge P$ , il campione viene scartato e il processo si ripete. Se $V < P$ , viene applicata la decomposizione di Horner inversa per generare la tupla di chiavi.
Framework di Analisi della Sicurezza: Il documento analizza l'intera pipeline (QKD $\to$ Estrazione della Chiave $\to$ Cifratura MR-OTP) attraverso sessioni singole e multiple. Utilizza uno schema di partizione a rotazione delle chiavi (key-rolling) in cui blocchi disgiunti dello stream QKD sono utilizzati per la chiave e la sequenza di basi di ogni sessione.
Tassonomia degli Avversari: L'analisi della sicurezza distingue quattro classi di avversari: basati su test, algebrici, illimitati (unbounded) e basati solo sul testo cifrato (ciphertext-only). Separa il "segreto computazionale" (la sequenza di basi $B$ ) dal "segreto informazionale" (il pad $K$ ).

Contributi Chiave e Risultati

Campionamento di Chiavi Uniformi: Il documento dimostra che la riduzione modulare ingenua rompe la perfetta segretezza (Proposizione 3.1). Dimostra che il campionamento per rifiuto combinato con la decomposizione di Horner inversa ripristina una distribuzione uniforme sullo spazio delle chiavi (Teorema 3.4). Il costo atteso in bit di questo processo è limitato da $2\lceil \log_2 P \rceil$ , con un numero atteso di round di rifiuto pari al massimo a 2 (Proposizione 3.5).
Sicurezza End-to-End: La composizione di una sorgente QKD ideale, dell'algoritmo di campionamento per rifiuto e del MR-OTP raggiunge la perfetta segretezza di Shannon per una singola sessione (Teorema 4.2) e attraverso $N$ sessioni sotto uno schema di rotazione delle chiavi per partizione (Teorema 6.2). Ciò avviene senza assunzioni computazionali.
Efficienza di Rappresentazione: Il documento quantifica il guadagno di efficienza del MR-OTP rispetto al OTP binario per alfabeti naturali. Operando nello spazio dei simboli nativi, il MR-OTP elimina l' "overhead binario" ( $\lceil \log_2 b \rceil - \log_2 b$ ) inerente alla codifica binaria. Ad esempio, offre una riduzione di circa il $16,9\%$ del materiale di chiave per le cifre decimali e di circa il $6,0\%$ per l'alfabeto latino (Proposizione 5.3).
Problema del Recupero della Base (BRP - Base Recovery Problem):
- Solo Testo Cifrato: Il documento dimostra che il recupero della sequenza di basi $B$ dal solo testo cifrato è informazionalmente insolubile (Corollario 8.2). Il testo cifrato fornisce zero informazioni su $B$ oltre al vincolo $b_i > c_i$ .
- Testo in Chiaro Noto: Nel contesto del testo in chiaro noto, il documento stabilisce un limite inferiore incondizionato sulla complessità delle query per gli avversari basati su test, mostrando che l'identificazione di $B$ richiede almeno $|F_T| - 1$ query, dove $|F_T|$ rimane esponenziale rispetto alla lunghezza del messaggio $L$ per piccoli valori di $T$ (Teorema 8.10).
- Invarianza della Sicurezza: Un risultato centrale (Teorema 8.15) dimostra che anche se un avversario (limitato o illimitato) recupera con successo la sequenza di basi $B$ da dati in chiaro noti, ottiene zero informazioni su qualsiasi messaggio futuro cifrato con una nuova chiave. La sicurezza informazionale del pad è preservata indipendentemente dallo stato computazionale del problema del recupero della base.
Estrazione a Lotti (Batched Extraction): Il documento introduce un algoritmo di estrazione a lotti (Sezione 9) che estrae un singolo intero grande per generare $N$ cifre di chiave simultaneamente. Ciò riduce l'overhead di rifiuto rispetto al campionamento sequenziale, avvicinandosi al limite teorico di entropia di $\log_2 b$ bit per simbolo quando $N \to \infty$ (Teorema 9.2).
Sorgenti Non Ideali: Il documento estende le garanzie di sicurezza a sorgenti QKD non ideali che sono $\epsilon$ -vicine all'uniformità nella distanza di variazione totale. Dimostra che il degrado della sicurezza end-to-end è limitato da $2N\epsilon$ per $N$ sessioni (Teorema 10.3).

Significatività e Rivendicazioni
Il documento sostiene di fornire la completa base algoritmica per il dispiegamento del MR-OTP con sorgenti QKD mantenendo una rigorosa sicurezza informazionale. La sua importanza primaria risiede in:

Risoluzione del Problema del Bias: Fornisce un metodo provabilmente corretto (campionamento per rifiuto + inversione di Horner) per convertire l'entropia binaria in chiavi a radice mista senza violare il requisito di uniformità della perfetta segretezza.
Sicurezza Temporale Incondizionata: Stabilisce che la sicurezza dei messaggi futuri è indipendente dalla difficoltà computazionale del recupero della sequenza di basi. Anche se la sequenza di basi viene recuperata, il sistema mantiene la perfetta segretezza per le cifrature fresche. Ciò crea una struttura di sicurezza a "due livelli" dove lo strato computazionale (nascondere la base) e lo strato informazionale (nascondere il messaggio) sono indipendenti.
Efficienza: Dimostra che il MR-OTP non è solo teoricamente solido ma anche praticamente più efficiente del OTP binario per alfabeti non potenze di due, riducendo il consumo di chiavi senza sacrificare la sicurezza.
Classificazione degli Avversari: Classifica rigorosamente le capacità degli avversari, dimostrando che la garanzia informazionale è incondizionata per tutte le classi di avversari, mentre i risultati di durezza computazionale si applicano solo a specifici sottoinsiemi (test vs. algebrici) nel contesto del testo in chiaro noto.

Il documento si conclude identificando problemi aperti, specificamente riguardo alla variante a rotazione dinamica della chiave (dove la sequenza di basi dipende dai testi cifrati precedenti) e la durezza computazionale nel caso medio del Problema del Recupero della Base per avversari algebrici.