Visueel delen van geheimen en additieve schema's

Visueel delen van geheimen (Naor & Shamir, 1994) splitst een afbeelding op in n transparanten, zodat het over elkaar leggen van k transparanten de geheime afbeelding zichtbaar maakt, terwijl minder transparanten niets onthullen — zelfs niet aan een tegenstander met onbeperkte rekenkracht.

Elke pixel van het geheim wordt uitgebreid tot een blok van 2x2. Voor een zwarte pixel krijgen beide deelwaarden complementaire patronen (bij het stapelen volledig zwart). Voor een witte pixel krijgen beide deelwaarden hetzelfde patroon (bij het stapelen 50% zwart = grijs). Het oog neemt het verschil waar.

Voor bitreeksen: deel je geheim S door willekeurige R_1, R_2, ..., R_{n-1} te genereren. Stel R_n = S XOR R_1 XOR ... XOR R_{n-1} in. Als je alle n deelwaarden met XOR combineert, krijg je S. Elke deelverzameling van n-1 deelwaarden is uniform willekeurig — er wordt niets over S onthuld.

XOR- of additief delen is n-uit-n (alle deelwaarden zijn nodig). Shamir SSS is k-uit-n (willekeurige k deelwaarden volstaan). Additief delen is eenvoudiger en sneller; Shamir ondersteunt willekeurige drempels. MPC-protocollen gebruiken vaak additief delen voor rekenkundige bewerkingen.

Voor gehele geheimen deel je S als S = s_1 + s_2 + ... + s_n (mod p). Elke s_i is een willekeurig element van Z_p. Om twee gedeelde waarden A+B op te tellen, telt elke partij lokaal zijn deelwaarden op: (a_i + b_i) mod p. Voor optellen is geen communicatie nodig.

Voor het vermenigvuldigen van gedeelde waarden is interactie nodig. De klassieke methode met Beaver-triples berekent vooraf een gedeelde willekeurige triple (a, b, c=ab). Om x*y te vermenigvuldigen maak je (x-a) en (y-b) aan alle partijen bekend (deze onthullen niets over x en y) en bereken je vervolgens x*y met de triple.

Een Lineair Schema voor Geheim Delen (LSSS) realiseert elke monotone toegangsstructuur. Shamir is een LSSS. LSSS'en vormen de bouwsteen voor versleuteling op basis van attributen (ABE) en systemen voor toegangsbeheer met meerdere beheerders.

Packed Shamir deelt meerdere geheimen in één polynoom: codeer k geheimen als coëfficiënten van een polynoom van graad (n-k). Hierdoor dalen de geamortiseerde communicatiekosten in MPC-protocollen wanneer veel waarden tegelijkertijd moeten worden gedeeld.

Basisschema's voor geheimdelen bieden geen bescherming tegen kwaadwillende deelnemers die ongeldige deelwaarden indienen. Verifiable Secret Sharing (VSS) voegt commitments toe; Robust Secret Sharing voegt foutcorrectie toe, zodat reconstructie zelfs met t foute deelwaarden slaagt.

Visuele cryptografie: authenticatie van gedrukte documenten en veilige stembiljetten. Additief delen: SPDZ-MPC en veilige aggregatie in federatief leren (Google). Drempelschema's: back-ups van hardwarewalletseeds en sleutelbeheer voor ondernemingen.

Een (k,n)-rampschema is zwakker: minder dan k-d deelwaarden onthullen gedeeltelijke informatie (d niveaus van geheimhouding). Dit wordt gebruikt wanneer perfecte geheimhouding van gedeeltelijke deelwaarden niet nodig is, maar efficiënte opslag wel cruciaal is. Rampschema's maken kortere deelwaarden mogelijk dan Shamir.

Visuele cryptografie splitst afbeeldingen op in transparanten; additief delen gebruikt XOR voor n-uit-n-schema's; Shamir ondersteunt k-uit-n. MPC gebruikt additief delen met Beaver-triples voor vermenigvuldiging. Hierna: drempelhandtekeningen en gebruik in de praktijk.