Visuell hemmelighetsdeling og additive skjemaer

Visuell hemmelighetsdeling (Naor & Shamir, 1994) deler et bilde i n transparenter, slik at det hemmelige bildet vises når k transparenter legges oppå hverandre, mens færre enn k transparenter ikke avslører noe – selv ikke for en beregningsmessig ubegrenset angriper.

Hver piksel i hemmeligheten utvides til en blokk på 2x2. For en svart piksel får begge andelene komplementære mønstre (når de legges oppå hverandre, blir alt svart). For en hvit piksel får begge andelene det samme mønsteret (når de legges oppå hverandre, blir 50 % svart = grått). Øyet oppfatter forskjellen.

For bitstrenger: Del hemmeligheten S ved å generere tilfeldige R_1, R_2, ..., R_{n-1}. Sett R_n = S XOR R_1 XOR ... XOR R_{n-1}. Når alle n andelene XOR-kombineres, blir resultatet = S. Ethvert delsett på n-1 andeler er uniformt tilfeldig – det avslører ingenting om S.

XOR-/additiv deling er n-av-n (alle andeler kreves). Shamirs SSS er k-av-n (vilkårlige k andeler). Additiv deling er enklere og raskere, mens Shamir håndterer vilkårlige terskler. MPC-protokoller bruker ofte additiv deling til aritmetiske operasjoner.

For heltallshemmeligheter: del S som S = s_1 + s_2 + ... + s_n (mod p). Hver s_i er et tilfeldig element i Z_p. For å legge sammen to delte verdier A+B legger hver part lokalt sammen sine andeler: (a_i + b_i) mod p. Ingen kommunikasjon er nødvendig for addisjon.

Multiplikasjon av delte hemmeligheter krever samhandling. Den klassiske metoden med Beaver-trippel forhåndsberegner en delt, tilfeldig (a, b, c=ab). For å multiplisere x*y offentliggjør man (x-a) og (y-b) for alle parter (dette avslører ingenting om x,y), og beregner deretter x*y ved hjelp av trippelet.

Et lineært hemmelighetsdelingsskjema (LSSS) realiserer enhver monoton tilgangsstruktur. Shamir er et LSSS. LSSS er byggesteinen for attributtbasert kryptering (ABE) og systemer for tilgangskontroll med flere autoriteter.

Packed Shamir deler flere hemmeligheter i ett polynom: kod k hemmeligheter som koeffisientene i et polynom av grad (n-k). Dette gir en amortisert kommunikasjonskostnad i MPC-protokoller når mange verdier må deles samtidig.

Grunnleggende delingsskjemaer gir ingen beskyttelse mot ondsinnede andelseiere som sender inn ugyldige andeler. Verifiserbar hemmelighetsdeling (VSS) legger til forpliktelser; robust hemmelighetsdeling legger til feilkorrigering, slik at gjenoppbyggingen lykkes selv med t feilaktige andeler.

Visuell kryptografi: autentisering av trykte dokumenter, sikre stemmesedler. Additiv deling: SPDZ-MPC, sikker aggregering i føderert læring (Google). Terskelskjemaer: sikkerhetskopiering av frø i maskinvarelommebøker, nøkkelhåndtering i virksomheter.

Et (k,n)-rampeskjema er svakere: færre enn k-d andeler avslører delvis informasjon (d nivåer av hemmelighold). Det brukes når perfekt hemmelighold av delvise andeler ikke er nødvendig, men lagringseffektivitet er avgjørende. Det gjør det mulig å bruke kortere andeler enn Shamir.

Visuell kryptografi deler bilder i transparenter; additiv deling bruker XOR for n-av-n-skjemaer, mens Shamir håndterer k-av-n. MPC bruker additiv deling med Beaver-trিপler til multiplikasjon. Neste: terskelsignaturer og bruk i praksis.