Schwellwert-Kryptosystem

Ein Kryptosystem wird Schwellwert-Kryptosystem genannt, wenn mehrere Parteien (mehr als ein bestimmter Schwellwert) kooperieren müssen, um eine verschlüsselte Nachricht zu entschlüsseln. Die Nachricht wird mit einem öffentlichen Schlüssel verschlüsselt, und der entsprechende private Schlüssel wird unter den Teilnehmern geteilt. Sei ${\displaystyle n}$ die Zahl der Parteien. Solch ein System wird ${\displaystyle (t,n)}$-Schwellwert genannt, wenn wenigstens ${\displaystyle t}$ dieser Parteien den Geheimtext effizient entschlüsseln können, während weniger als ${\displaystyle t}$ keine nützliche Information erhalten. Ähnlich ist es möglich, ein ${\displaystyle (t,n)}$-Signaturschema zu definieren, in dem wenigstens ${\displaystyle t}$ Parteien zusammenarbeiten müssen, um eine Signatur herzustellen.

Schwellwert-Versionen von Kryptosystemen können für viele öffentlicher-Schlüssel-Systeme konstruiert werden. Das naheliegende Ziel solcher Entwicklungen ist es, dieselbe Sicherheit zu bieten wie das ursprüngliche System. Solche Schwellwert-Varianten wurden definiert für:

• RSA^[1]
• Paillier-Kryptosystem^[2][3]
• Damgård-Jurik-Kryptosystem^[4][5]
• ElGamal-Kryptosystem

Anwendung

Die häufigste Anwendung ist die Speicherung von Geheimnissen an mehreren Orten, um zu verhindern, dass der Geheimtext bekannt wird und anschließend eine Kryptanalyse durchgeführt wird. Oft ist das Geheimnis, das „aufgeteilt“ wird, der geheime Schlüssel eines Schlüsselpaars in der Public-Key-Kryptographie oder der Schlüsseltext gespeicherter Passwort-Hashes. Bei elektronischen Wahlsystemen bieten solche Systeme, wenn sie gleichzeitig homomorph verschlüsseln, die Möglichkeit, die Auszählung der abgegebenen Stimmen unter der Verschlüsselung durchzuführen, so dass das Wahlgeheimnis gewahrt bleibt.

Geschichtlich haben nur Organisationen mit sehr wertvollen Geheimnissen, etwa Zertifizierungsstellen, Militärs oder Regierungen solchen Techniken eingesetzt. Als im Oktober 2012 die verschlüsselten Passwörter einer großen Zahl von Websites kompromittiert wurden, hat RSA Security angekündigt, Software zur Verfügung zu stellen, die diese Technik der Öffentlichkeit zugänglich macht.^[6]

Siehe auch

• Secret-Sharing
• verteiltes Rechnen
• High-bandwidth Digital Content Protection

Einzelnachweise

1. H.L. Nguyen: RSA Threshold Cryptography. 4. Mai 2005 (englisch, Department of Computer Science, University of Bristol [PDF]). 
2. Ivan Damgård, Mads Jurik und Jesper Buus Nielsen: A generalization of Paillier’s public-key system with applications to electronic voting. 1. Dezember 2012, doi:10.1007/s10207-010-0119-9 (Massachusetts Institute of Technology [PDF]). 
3. Paillier Threshold Encryption Toolbox. 23. Oktober 2010 (englisch, University of Texas, Dallas [PDF]). 
4. Ivan Damgård, Mads Jurik: A Length-Flexible Threshold Cryptosystem with Applications. In: ACISP, 2003, S. 350–364
5. Ivan Damgård, Mads Jurik: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Public Key Cryptography, 2001, S. 119–136
6. Tom Simonite: To Keep Passwords Safe from Hackers, Just Break Them into Bits In: Technology Review, 9. Oktober 2012