Visuell hemlighetsdelning och additiva scheman

Visuell hemlighetsdelning (Naor & Shamir, 1994) delar upp en bild i n transparenser så att en överlagring av k transparenser visar hemlighetsbilden, medan färre transparenser inte avslöjar någonting – inte ens för en motståndare med obegränsad beräkningskapacitet.

Varje pixel i hemligheten förstoras till ett block på 2x2. För en svart pixel får båda delarna komplementära mönster (när de läggs ihop blir allt svart). För en vit pixel får båda delarna samma mönster (när de läggs ihop blir 50 % svart = grått). Ögat uppfattar skillnaden.

För bitsträngar: dela hemligheten S genom att generera slumpmässiga R_1, R_2, ..., R_{n-1}. Sätt R_n = S XOR R_1 XOR ... XOR R_{n-1}. XOR av alla n delar = S. Varje delmängd med n-1 delar är likformigt slumpmässig – den avslöjar ingenting om S.

XOR-baserad eller additiv hemlighetsdelning är n-av-n (alla delar krävs). Shamir SSS är k-av-n (vilka k delar som helst). Additiv hemlighetsdelning är enklare och snabbare; Shamir hanterar godtyckliga trösklar. MPC-protokoll använder ofta additiv hemlighetsdelning för aritmetiska operationer.

För heltalshemligheter delas S upp som S = s_1 + s_2 + ... + s_n (mod p). Varje s_i är ett slumpmässigt element i Z_p. För att addera två delade värden A+B adderar varje part lokalt sina delar: (a_i + b_i) mod p. Ingen kommunikation behövs för additionen.

Multiplikation av delade hemligheter kräver interaktion. Den klassiska metoden med Beaver-tripletter bygger på att delade slumpvärden (a, b, c=ab) beräknas i förväg. För att multiplicera x*y avslöjas (x-a) och (y-b) för alla parter (dessa avslöjar ingenting om x eller y), varefter x*y beräknas med hjälp av tripletten.

Ett linjärt hemlighetsdelningsschema (LSSS) realiserar godtyckliga monotona åtkomststrukturer. Shamir är en LSSS. LSSS är byggstenen för attributbaserad kryptering (ABE) och system för åtkomstkontroll med flera myndigheter.

Paketerad Shamir delar flera hemligheter i ett polynom: koda k hemligheter som koefficienter i ett polynom av grad (n-k). Detta möjliggör amorterad kommunikationskostnad i MPC-protokoll när många värden måste delas samtidigt.

Grundläggande hemlighetsdelningsscheman skyddar inte mot illvilliga deltagare som skickar in ogiltiga delar. Verifierbar hemlighetsdelning (VSS) lägger till commitmenter; robust hemlighetsdelning lägger till felkorrigering, så att återskapandet lyckas även med t felaktiga delar.

Visuell kryptografi: autentisering av tryckta dokument och säkra röstsedlar. Additiv hemlighetsdelning: SPDZ MPC och säker aggregering i federerat lärande (Google). Tröskelscheman: säkerhetskopiering av hårdvaruplånböckers seed och företagsbaserad nyckelhantering.

Ett (k,n)-ramp-schema är svagare: färre än k-d delar avslöjar partiell information (d sekretessnivåer). Det används när perfekt sekretess för partiella delar inte krävs men lagringseffektivitet är avgörande. Det möjliggör kortare delar än Shamir.

Visuell kryptografi delar upp bilder i transparenser; additiv hemlighetsdelning använder XOR för n-av-n-scheman; Shamir hanterar k-av-n. MPC använder additiv hemlighetsdelning med Beaver-tripletter för multiplikation. Nästa avsnitt: tröskelsignaturer och användning i praktiken.