Visuelles Secret Sharing und additive Verfahren

Visual Secret Sharing (Naor & Shamir, 1994) teilt ein Bild in n transparente Folien auf, sodass das Übereinanderlegen von k Folien das geheime Bild sichtbar macht, während weniger Folien keinerlei Informationen preisgeben — selbst für einen rechnerisch unbeschränkten Angreifer.

Jedes Pixel des Geheimnisses wird zu einem 2x2-Block erweitert. Bei einem schwarzen Pixel erhalten beide Shares komplementäre Muster (übereinandergelegt sind alle Pixel schwarz). Bei einem weißen Pixel erhalten beide Shares dasselbe Muster (übereinandergelegt sind 50 % der Pixel schwarz = Grau). Das Auge nimmt den Unterschied wahr.

Für Bitstrings: Teilen Sie das Geheimnis S, indem Sie zufällige Werte R_1, R_2, ..., R_{n-1} erzeugen. Setzen Sie R_n = S XOR R_1 XOR ... XOR R_{n-1}. Das XOR aller n Shares ergibt S. Jede Teilmenge aus n-1 Shares ist gleichverteilt zufällig und gibt keinerlei Informationen über S preis.

XOR- bzw. additives Sharing ist ein n-of-n-Verfahren (alle Shares werden benötigt). Shamir SSS ist ein k-of-n-Verfahren (beliebige k Shares reichen aus). Additives Sharing ist einfacher und schneller; Shamir unterstützt beliebige Schwellenwerte. MPC-Protokolle verwenden für arithmetische Operationen häufig additives Sharing.

Für ganzzahlige Geheimnisse teilen Sie S als S = s_1 + s_2 + ... + s_n (mod p). Jedes s_i ist ein zufälliges Element von Z_p. Um zwei geteilte Werte A+B zu addieren, addiert jede Partei lokal ihre Shares: (a_i + b_i) mod p. Für die Addition ist keine Kommunikation erforderlich.

Die Multiplikation von mit Secret Sharing geteilten Werten erfordert Interaktion. Die klassische Methode verwendet ein Beaver-Tripel: Berechnen Sie gemeinsam ein geteiltes zufälliges (a, b, c=ab) vorab. Um x*y zu multiplizieren, machen Sie (x-a) und (y-b) für alle Parteien sichtbar (diese Werte verraten nichts über x,y) und berechnen Sie anschließend x*y mithilfe des Tripels.

Ein Linear Secret Sharing Scheme (LSSS) setzt jede monotone Zugriffsstruktur um. Shamir ist ein LSSS. LSSS bilden die Grundlage für attributbasierte Verschlüsselung (ABE) und Systeme zur Zugriffssteuerung mit mehreren Autoritäten.

Packed Shamir teilt mehrere Geheimnisse in einem Polynom: Es kodiert k Geheimnisse als Koeffizienten eines Polynoms vom Grad (n-k). Dadurch lassen sich die Kommunikationskosten in MPC-Protokollen amortisieren, wenn viele Werte gleichzeitig geteilt werden müssen.

Einfache Sharing-Verfahren schützen nicht vor böswilligen Teilnehmern, die ungültige Shares übermitteln. Verifiable Secret Sharing (VSS) ergänzt Commitments; Robust Secret Sharing fügt Fehlerkorrektur hinzu, sodass die Rekonstruktion selbst bei t fehlerhaften Shares gelingt.

Visuelle Kryptografie: Authentifizierung gedruckter Dokumente, sichere Wahlzettel. Additives Sharing: SPDZ MPC, sichere Aggregation beim föderierten Lernen (Google). Schwellenwertverfahren: Sicherung von Hardware-Wallet-Seeds, Schlüsselverwaltung in Unternehmen.

Ein (k,n)-Ramp-Verfahren ist schwächer: Weniger als k-d Shares geben teilweise Informationen preis (d Geheimhaltungsstufen). Es wird eingesetzt, wenn perfekte Geheimhaltung partieller Shares nicht erforderlich ist, die Speichereffizienz jedoch entscheidend ist. Es ermöglicht kürzere Shares als Shamir.

Wie viele Shares werden bei XOR-basiertem additivem n-of-n-Sharing benötigt, um das Geheimnis zu rekonstruieren?

Visuelle Kryptografie teilt Bilder in transparente Folien auf; additives Sharing verwendet XOR für n-of-n-Verfahren; Shamir unterstützt k-of-n. MPC verwendet additives Sharing mit Beaver-Tripeln für Multiplikationen. Als Nächstes folgen Schwellenwertsignaturen und Anwendungen in der Praxis.