Condivisione visiva dei segreti e schemi additivi

La condivisione visiva del segreto (Naor e Shamir, 1994) divide un'immagine in n trasparenze, in modo che la sovrapposizione di k trasparenze riveli l'immagine segreta, mentre un numero inferiore non rivela nulla, nemmeno a un avversario computazionalmente illimitato.

Ogni pixel del segreto viene espanso in un blocco 2x2. Per un pixel nero, entrambe le condivisioni ricevono pattern complementari (quando vengono sovrapposte, risultano completamente nere). Per un pixel bianco, entrambe ricevono lo stesso pattern (quando vengono sovrapposte, il 50% nero produce il grigio). L'occhio percepisce la differenza.

Per le stringhe di bit: si condivide il segreto S generando R_1, R_2, ..., R_{n-1} casuali. Si imposti R_n = S XOR R_1 XOR ... XOR R_{n-1}. L'operazione XOR su tutte le n condivisioni restituisce S. Qualunque sottoinsieme di n-1 condivisioni è uniformemente casuale e non rivela nulla su S.

La condivisione XOR/additiva è n-di-n (sono necessarie tutte le condivisioni). La SSS di Shamir è k-di-n (sono sufficienti k condivisioni qualsiasi). La condivisione additiva è più semplice e veloce; Shamir gestisce soglie arbitrarie. I protocolli MPC usano spesso la condivisione additiva per le operazioni aritmetiche.

Per i segreti interi, si condivide S come S = s_1 + s_2 + ... + s_n (mod p). Ogni s_i è un elemento casuale di Z_p. Per sommare due valori condivisi A+B, ogni partecipante somma localmente le proprie condivisioni: (a_i + b_i) mod p. Per l'addizione non è necessaria alcuna comunicazione.

La moltiplicazione di valori condivisi segretamente richiede un'interazione. Il classico metodo della tripla di Beaver consiste nel precalcolare una tripla casuale condivisa (a, b, c=ab). Per moltiplicare x*y, si rivelano (x-a) e (y-b) a tutti i partecipanti (questi valori non rivelano nulla su x e y), quindi si calcola x*y usando la tripla.

Uno schema lineare di condivisione del segreto (LSSS) realizza qualsiasi struttura di accesso monotona. Shamir è un LSSS. Gli LSSS sono il componente fondamentale della crittografia basata sugli attributi (ABE) e dei sistemi di controllo degli accessi a più autorità.

La condivisione impacchettata di Shamir inserisce più segreti in un unico polinomio: codifica k segreti come coefficienti di un polinomio di grado (n-k). Questo consente di ammortizzare il costo della comunicazione nei protocolli MPC quando è necessario condividere simultaneamente molti valori.

Gli schemi di condivisione di base non offrono protezione contro i partecipanti malevoli che inviano condivisioni non valide. La condivisione verificabile del segreto (VSS) aggiunge commitment; la condivisione robusta del segreto aggiunge la correzione degli errori, così la ricostruzione riesce anche in presenza di t condivisioni errate.

Crittografia visiva: autenticazione di documenti stampati e schede elettorali sicure. Condivisione additiva: SPDZ MPC e aggregazione sicura nell'apprendimento federato (Google). Schemi a soglia: backup del seed di portafogli hardware e gestione delle chiavi aziendali.

Uno schema a rampa (k,n) è più debole: meno di k-d condivisioni rivelano informazioni parziali (d livelli di segretezza). Viene usato quando non è necessaria la segretezza perfetta delle condivisioni parziali, ma l'efficienza di archiviazione è fondamentale. Consente di usare condivisioni più brevi rispetto a Shamir.

La crittografia visiva divide le immagini in trasparenze; la condivisione additiva usa XOR per gli schemi n-di-n; Shamir gestisce gli schemi k-di-n. La MPC usa la condivisione additiva con le triple di Beaver per la moltiplicazione. Prossimo argomento: firme a soglia e utilizzo nel mondo reale.