Secret-Sharing-Algorithmen

25/03/2008 - 13:34 von Peter Fetzer | Report spam
Hallo zusammen,

für den praktischen Einsatz in einer Kryptographieanwendung bin ich auf der
Suche nach einem guten Secret-Sharing-Algorithmus
((m,n)-Schwellenwertverfahren).

An George Blakleys Vektorverfahren gefàllt mir nicht, dass das bekannt sein
von < m Teilschlüsseln den möglichen Passwortraum des Geheimnisses bereits
drastisch einschrànkt.

Die Polynominterpolation von Adi Shamir (Shamir's secret-sharing scheme)
macht einen ganz guten Eindruck und ist bisher mein Favorit.

Asmuth-Bloom scheint bei RSA Verwendung zu finden. Wirklich viele
Informationen dazu konnte ich aber leider nicht finden.

Karnin-Greene-Hellman stehe ich etwas skeptisch gegenüber, da der
Algorithmus meiner Meinung nach die selbe Schwàche wie das Vektorverfahren
aufweist.

Für ein paar Hinweise wàre ich sehr dankbar.


Viele Grüße
Peter
 

Lesen sie die antworten

#1 Christopher Creutzig
26/03/2008 - 22:50 | Warnen spam
Peter Fetzer wrote:

Karnin-Greene-Hellman stehe ich etwas skeptisch gegenüber, da der
Algorithmus meiner Meinung nach die selbe Schwàche wie das Vektorverfahren
aufweist.



Über einem Körper? IBTD. Um die Namen festzulegen, kurze Beschreibung:

Wàhle n+1 Vektoren der Lànge m, V_0 bis V_n, über dem Körper k, so dass
jede m-elementige Teilmenge von {V_0, ..., V_n} linear unabhàngig ist.
Diese Vektoren seien allgemein bekannt. Um nun das Geheimnis M aus k zu
verschlüsseln, wàhle zufàllig einen Vektor U, so dass das Sakalarprodukt
<U, V_0>=M ist. Für jedes i ist s_i=<U, V_i> der Teil i des geteilten
Geheimnisses.

Kommen nun m der (V_i, s_i) zusammen, ergibt sich ein eindeutig
lösbares LGS für U und daraus làsst sich <U, V_0>=M rekonstruieren.

Kommen nur m-1 der (V_i, s_i) zusammen, so làsst sich U auf einen
eindimensionalen linear-affinen Raum einschrànken. Im Gegensatz zu
Blakleys Vektorverfahren liefert dieser Raum aber keine Informationen
über M: OBdA nehmen wir an, U sei bis auf seine letzte Komponente
bekannt. (Alle anderen Situationen lassen sich durch Basiswechsel darauf
transformieren.) Dann kennen wir M'=M-(V_0)_m*(U)_m, wobei (V_0)_m, die
m-te Komponente von V_0, bekannt ist. Da wir über (U)_m aber exakt gar
keine Information haben, nützt uns das überhaupt nichts, da nach wie vor
alle Werte von M möglich sind.

Über bspw. den ganzen Zahlen wàre das in der Tat anders, da würde M',
den Wert von M schon in eine Restklasse modulo (V_0)_m einschrànken.

Für ein paar Hinweise wàre ich sehr dankbar.



Von den àlteren Verfahren nicht aufgezàhlt hast Du mindestens
Asmuth-Bloom und die ganzen Anwendungen von Fehlerkorrekturcodes. Wenn
ich bei portal.acm.org nach “secret sharing” suche, bekomme ich noch
eine riesige Liste weiterer Verfahren. die Crypto- und
EUROCRYPT-Proceedings enthalten auch immer wieder neue Vorschlàge. Es
gibt auch nette Verfahren, die mit Schummlern klar kommen. Je nach
Anwendung kann es auch wichtig sein, dass die Dekodierung nur schwer
durch timing attacks oder Analyse des Stromverbrauchs zu beobachten ist
etc. Aber das hàngt davon ab, was für eine Anwendung Dir genau
vorschwebt. (Und ich habe die Entwicklung auch nicht gerade aufmerksam
verfolgt.)

if all this stuff was simple, we'd
probably be doing something else. -- Daniel Lichtblau, s.m.symbolic

Ähnliche fragen