Geheimnisteilung

Unter Geheimnisteilung (geteiltes Geheimnis) oder Secret Sharing versteht man eine Technik, ein Geheimnis (meist eine Zahl) unter einer gewissen Anzahl von so genannten Spielern aufzuteilen. Keine der Personen kann ohne die anderen das Geheimnis rekonstruieren. Je nach System ist nur eine Teilmenge der Spieler notwendig, um das Geheimnis zu bestimmen. Als Dealer wird derjenige bezeichnet, der die Aufteilung vornimmt.

Ein typisches Geheimnis ist der geheime Schlüssel des RSA-Kryptosystems. Wenn er auf mehrere Personen aufgeteilt wird, kann keine Person alleine eine Signatur erstellen. Auch die Kompromittierung eines Teilnehmers (und dessen Teilschlüssels) führt nicht zur Kompromittierung des gesamten Schlüssels. Solch eine Aufteilung ist in Hochsicherheitsbereichen (z. B. Militär, Zertifizierungsunternehmen, Banken, …) sinnvoll.

Verfahren

Einfaches Secret-Sharing

Ein einfaches Sharing-Verfahren sieht folgendermaßen aus.

• Sei s das Geheimnis
• Wähle die Teilgeheimnisse $s_i, i \in \{ 1, \ldots, n \}$ so, dass gilt:
  • $s = s_1 + s_2 + \dots + s_n$
  • Rekonstruktion von s nur möglich, wenn alle s_i kombiniert werden

Dieses Verfahren ist ein (n,n)-Schwellwert-Schema (sprich: n-aus-n-Schwellwert-Schema), da alle n Teilgeheimnisse zur Rekonstruktion benötigt werden. Die $s_i, i=2 \dots n$ müssen zufällig gewählt werden. s₁ wird derart gewählt, dass die Bedingung erfüllt wird. Da die $s_i, i=2 \dots n$ zufällig sind, ist auch s₁ zufällig.

Eine zweite Möglichkeit kann realisiert werden, indem die Addition durch die Exklusiv-Oder-Verknüpfung ($\oplus$) ersetzt wird:

• Sei s das Geheimnis (binär dargestellte Zahl)
• Wähle die Teilgeheimnisse s_i folgendermaßen:
  • $s = s_1 \oplus s_2 \oplus \dots \oplus s_n$
  • Rekonstruktion von s nur möglich, wenn alle s_i kombiniert werden

Dieses Verfahren ist wiederum ein (n,n)-Schwellwert-Schema. Die Bedingungen für die s_i sind so wie im zuvor beschriebenen Verfahren.

Shamir's Secret Sharing

siehe Shamirs Secret Sharing. Ein weiteres von Adi Shamir entwickeltes Secret-Sharing-Verfahren ist die Visuelle Kryptographie.

Blackley's Secret Sharing

Verifiable Secret Sharing

Beim VSS wird das Secret Sharing derart erweitert, dass es dem Dealer nicht möglich ist, falsche Shares an die Spieler zu verteilen. Um diese Sicherheit zu gewährleisten, werden Commitments eingesetzt, mit denen sich der Dealer unwiderruflich auf die Shares festlegt.

Einsatzgebiete

Secret Sharing (vor allem VSS) wird bei vielen Varianten der verteilten Schlüssel-Generierung benötigt, um den Schlüssel unter den Teilnehmern zu verteilen.