Kann ich die Punkte in Shamirs Secret Sharing-Algorithmus vordefinieren?

  • Mit kann Shamir heimlich getauscht werden . die vom Algorithmus zurückgegebenen Punkte definieren?

    Der Einfachheit halber habe ich (k, n) mit k = 2 und n = 4 und ich habe die Punkte X, Y, Z und Q. Kann ich die Koeffizienten so erstellen, dass X, Y, Z und Q die vom Algorithmus zurückgegebenen Punkte sind.

    Wenn ja, ist es immer noch sicher (oder sicher genug)

    Bearbeiten:

    Ändern Sie mein Beispiel in k = 2 anstelle von k = 1, um zu verhindern, dass die Kommentare in eine Diskussion über die Vorteile fallen, wenn nur ein einziges Wissen benötigt wird, um auf das Geheimnis zuzugreifen.

    26 July 2012
    CodesInChaosgrieve
3 answers
  • Nein, im Allgemeinen können Sie keine beliebigen Punkte $ X, Y, Z $ und $ Q $ auswählen, die in einem Shamir-Secret-Sharing-Schema funktionieren würden (es sei denn, $ k \ ge4 $.)

    Warum? Shamirs Schema geht davon aus, dass sich die Punkte auf einem Polynom mit einem Grad von $ k-1 $ oder weniger befinden. für $ k = 2 $ bedeutet dies, dass die Punkte alle Lösungen einer linearen Gleichung $ y = a_1 x + a_0 $ für einige Konstanten $ a_1, a_0 $ sein müssen. Es wird normalerweise keine solchen Konstanten geben, die gleichzeitig für alle vier Punkte funktionieren, und daher wird Shamirs Schema nicht funktionieren.

    BTW: Welches Problem versuchen Sie zu lösen? Sie erwähnen "Sicherheit"; Was meinst du damit? Wenn Sie verhindern möchten, dass jemand etwas unternimmt, was ist das?

    19 June 2012
    poncho
  • Mit Shamirs geheimem Teilen für den Fall von $ k $ aus $ n $ konstruieren Sie ein zufälliges Polynom mit dem Grad $ k-1 $, da $ l $ -Punkte ein Polynom mit dem Grad $ k- eindeutig identifizieren. 1 $.

    Der übliche Weg zur Konstruktion des Polynoms besteht darin, die Koeffizienten $ a_1 $ bis $ a_ {k-1} $ einheitlich zu wählen und $ a_0 = s $ zu setzen.

    Es gibt eine Alternative dazu, indem Sie zufällig einheitlich $ k-1 $ Punkte wählen. Der $ k $ -te Punkt ist dann $ (0, s) $. Sie können das durch diese Punkte definierte Polynom und dann die verbleibenden $ n- (k-1) $ -Punkte berechnen. Es gibt absolut keinen Unterschied zwischen die beiden Ansätze.

    Also zusammenfassend: Nein, das ist nicht möglich. Sie können maximal $ k-1 $ Aktien frei wählen. Damit die Sicherheit erhalten bleibt, müssen diese nach dem Zufallsprinzip ausgewählt werden.

    19 June 2012
    Maeher
  • Wie Poncho und Maeher festgestellt haben, ist dies mit dem direkten Teilen von Shamir nicht möglich.

    Tatsächlich ist es ziemlich offensichtlich, wenn Sie darüber nachdenken, Es gibt keine Möglichkeit, im Voraus mehr als $ k $ -Anteile unabhängig voneinander zu wählen und mit any ein konsistentes Geheimnis aus ihnen herauszuholen; Selbst wenn Sie zulassen, dass das Geheimnis zufällig ist.

    Stellen Sie sich insbesondere vor, Sie hätten $ k + 1 $ unabhängig voneinander gewählte Freigaben $ s_1, s_2, \ dotsc, s_ {k + 1 } $. Per Definition reicht eines der $ k $ -Tupel $ (s_1, s_2, \ dotsc, s_k) $ und $ (s_2, s_3, \ dotsc, s_ {k + 1}) $ aus, um das Geheimnis vollständig zu rekonstruieren Allein das $ k-1 $ -Tuple $ (s_2, s_3, \ dotsc, s_k) $ liefert nein Informationen über die Freigabe. Dies bedeutet, dass für jedes Paar von Geheimnissen $ S $ und $ S '$ und für gegebene $ k-1 $ -Anteile $ s_2, s_3, \ dotsc, s_k $ Aktien $ s_1 vorhanden sein müssen $ und $ s_ {k + 1} $, so dass $ (s_1, s_2, \ dotsc, s_k) $ das geheime $ S $ ergibt, während $ (s_2, s_3, \ dotsc, s_ {k + 1}) $ $ ergibt S '$.

    Alles in allem gibt es jedoch eine einfache Möglichkeit, das geheime Freigabeschema von Shamir so zu ändern, dass die Freigaben unabhängig voneinander ausgewählt werden können advance.

    Geben Sie nämlich an, dass $ s_1, s_2, \ dotsc, s_n $ die im Voraus ausgewählten Anteile bezeichnen, und lassen Sie $ S $ das Geheimnis sein, das Sie teilen möchten. Berechnen Sie nun $ n $ "Auxiliary" -Anteile $ a_1, a_2, \ dotsc, a_n $ unter Verwendung der üblichen Shamirs geheimen Freigabe von $ S $, und fügen Sie sie den entsprechenden vorgewählten Freigaben hinzu, um $$ p_i: = a_i \ oplus s_i zu erhalten $$ für alle $ i \ in \ {1, 2, \ dotsc, n \} $, wobei $ \ oplus $ den Zusatz im endlichen Feld bezeichnet, zu dem die Freigaben gehören.

    Veröffentlichen Sie schließlich die Ergebnisse $ p_1, p_2, \ dotsc, p_n $.

    Jetzt können alle $ k $ -Teilnehmer ihren Anteil abziehen, um das geheime $ S $ zu rekonstruieren $ s_i $ aus dem öffentlichen $ p_i $ (oder enthüllen Sie einfach ihre $ s_i $ und lassen Sie andere es mit $ p_i $ kombinieren), um die entsprechenden Hilfsaktien $ a_i $ und zu erhalten

    27 July 2012
    Ilmari Karonen