Secret-Sharing

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 (zum Beispiel Militär, Zertifizierungsunternehmen, Banken, …) sinnvoll.

Es kann jedoch auch verwendet werden, wenn der Dealer eine Bestätigung möchte, dass ein Ereignis eingetreten ist, und alle Spieler dies bestätigen. So könnte er eine hinreichend große Zahl verteilen, und nur, wenn alle kooperieren, also der Meinung sind, das Ereignis trat ein, die Nummer generieren und übermitteln. Auf diesem Wege sind auch kryptologische Testamente möglich, bei denen der Testamentstext öffentlich verschlüsselt wird, aber nur alle zusammen beschließen können, ihn zu lesen, was die Gefahr unbefugten Zugriffs reduziert.

Verfahren

Einfaches Secret-Sharing

Ein einfaches (additives) Sharing-Verfahren sieht folgendermaßen aus:

• Sei $s$ das Geheimnis
• Wähle die Teilgeheimnisse $s_{i},i\in \{1,\ldots ,n\}$ und einen Modulus p so, dass gilt:
  • $s=(s_{1}+s_{2}+\dots +s_{n})\%p$
  • Rekonstruktion von $s$ nur möglich, wenn alle $s_{i}$ kombiniert werden
  • Für p wird in der Regel eine Primzahl verwendet

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_{1}$ wird derart gewählt, dass die Bedingung erfüllt wird.

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.

Erweiterte Secret-Sharing-Verfahren

Zwei bekannte Secret-Sharing-Verfahren stammen von Adi Shamir: Shamir’s Secret Sharing und die Visuelle Kryptographie.

Ein weiteres Verfahren ist das Verifiable Secret Sharing, bei dem es dem Dealer nicht möglich ist, falsche Shares an die Spieler zu verteilen. Um diese Sicherheit zu gewährleisten, werden Commitment-Verfahren 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.

Siehe auch

• Shared Secret