Sichere Mehrparteienberechnung der Anzahl von 1s mal der Anzahl von 0s in einer gemeinsam genutzten Zeichenfolge

Angenommen, es gibt $N>2$ Parteien $p_j$ mit jeweils einem Bit . Ich möchte die Multiplikation der Anzahl von Einsen mit der von Nullen berechnen, dh . R = ( ∑ b j ) × ( N - ∑ b j$b_j\in{\{0,1\}}$$R=(\sum{b_j})\times(N-\sum{b_j})$

Die Berechnung sollte in dem Sinne sicher sein, dass keine Partei mehr als das Endergebnis lernen kann . Zum Beispiel ist es nicht in Ordnung, eine sichere Summe auszuführen, da dann bekannt wird und die Summe in meinem Problem empfindlich ist. Gibt es also ein sicheres Berechnungsprotokoll, das den Anforderungen entspricht?∑ b $R$$\sum{b_j}$

Bearbeiten: Die Zahl im Problem ist groß, mindestens über . Daher ist eine effiziente sichere Mehrparteienberechnung erforderlich. Ein sicheres Summenprotokoll könnte effizient sein, aber generische SMC-ähnliche Boolesche Schaltungen könnten zu rechenintensiv sein. Ich brauche also ein effizientes Protokoll.$N$$1000$

Bei dieser Antwort handelt es sich um praktikable Lösungen, die auf einer homomorphen Verschlüsselung basieren, die NICHT vollständig homomorph ist, da letztere äußerst ineffizient sein kann (wenn es effiziente vollständig homomorphe Kryptosysteme gibt, die hinsichtlich der Effizienz mit den unten angegebenen vergleichbar sind, würde ich mich freuen von ihnen hören).

Da Sie nur eine Multiplikation benötigen, gibt es Lösungen, die möglicherweise kostengünstiger sind als eine vollständig homomorphe Verschlüsselung: [1] und [2]. Letzteres funktioniert mit verschlüsselten Bitzerlegungen der Eingabe, sodass ein Bitzerlegungsprotokoll wie [3] und [6] erforderlich ist, ersteres jedoch mit ganzen Werten. Der Vollständigkeit halber wurde Ersteres in [4] auf die Operanden-Multiplikation ausgedehnt , obwohl das OP dies möglicherweise nicht benötigt. Diese Lösungen sind nicht interaktiv und sollten im Zwei-Parteien-Fall funktionieren.$d$

Wenn Sie mehr als zwei Parteien haben und sich eine Interaktion leisten könnten, bietet [5] ein "sicheres Multiplikationsgatter", das möglicherweise effizienter ist und eine unbegrenzte Anzahl von Multiplikationen ermöglicht. Es funktioniert im Wesentlichen, indem die homomorph verschlüsselten Werte in eine Art Geheimfreigabe konvertiert werden, das Ergebnis (interaktiv) multipliziert und dann wieder in homomorphe Verschlüsselung konvertiert wird.

[1] Auswertung von 2-DNF-Formeln für Chiffretexte

[2] Nicht interaktives Kryptocomputing für NC1

[3] Bedingungslos sichere Mehrparteienberechnung mit konstanten Runden für Gleichheit, Vergleich, Bits und Potenzierung

[4] Additiv homomorphe Verschlüsselung mit d-Operanden-Multiplikationen

[5] Mehrparteienberechnung aus homomorpher Schwellenwertverschlüsselung

[6] Effiziente binäre Konvertierung für Paillier-verschlüsselte Werte

Neue Antwort (24.10.): Ich denke, das folgende Papier bietet eine elegante und effiziente Lösung für Ihr Problem:

• Bewertung von 2-DNF-Formeln zu Chiffretexten , Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

Sie zeigen, wie ein Verschlüsselungsalgorithmus mit öffentlichem Schlüssel mit den folgenden zwei nützlichen Eigenschaften erstellt wird:$E(\cdot)$

• Additiv homomorph. Mit und E ( y ) kann jeder E ( x + y ) berechnen .$E(x)$$E(y)$$E(x+y)$

• Kann (einmal) multiplizieren. Mit und E ( y ) (von denen keines als Ergebnis einer Multiplikationsoperation erzeugt wurde) kann jeder E ( x ⋅ y ) berechnen . Sie können das Ergebnis in Additionsoperationen verwenden, aber Sie können es nicht in Multiplikationsoperationen verwenden (das Ergebnis einer Multiplikation ist fehlerhaft, und fehlerhafte Werte können nicht als Eingabe für eine andere Multiplikation verwendet werden).$E(x)$$E(y)$$E(x \cdot y)$

Die Folge ist, dass bei einem quadratischen multivariaten Polynom und bei E ( x 1 ) , … , E ( x n ) jeder eine Verschlüsselung von Ψ ( x 1 , … , berechnen kann ). x n ) . Dies ist sehr nützlich für Ihre Situation.$\Psi(x_1,\dots,x_n)$$E(x_1),\dots,E(x_n)$$\Psi(x_1,\dots,x_n)$

Insbesondere können wir in Ihrer Situation das Polynom Beachten Sie, dass dies ein quadratisches multivariates Polynom ist. Wenn also alle E ( b i ) gegeben sind, kann jeder E berechnen ( Ψ ( b 1 , … , b N )

Dies schlägt ein natürliches Protokoll für Ihr Problem vor, bei dem eine Schwellenwertversion des Verschlüsselungsschemas in dem oben genannten Dokument verwendet wird:

• Jeder generiert gemeinsam ein öffentliches / privates Schlüsselpaar für eine Schwellenwertversion dieses Schemas, sodass der öffentliche Schlüssel allen bekannt ist, der private Schlüssel jedoch von allen gemeinsam genutzt wird (es erfordert die Zusammenarbeit aller Parteien, um einen unter diesem öffentlichen Schlüssel verschlüsselten Chiffretext zu entschlüsseln ). Der öffentliche Schlüssel wird an alle N Teilnehmer gesendet .$N$$N$
• Jeder Teilnehmer berechnet E ( b i ) und sendet E ( b i ) an alle anderen Teilnehmer. Jeder überprüft, ob dies ehrlich getan wurde.$i$$E(b_i)$$E(b_i)$
• Jeder Teilnehmer berechnet Verwendung der homomorphen Eigenschaften dieses Verschlüsselungsschemas und der Kenntnis von E ( b 1 ) , … , E ( b N ) . Jeder prüft, ob er den gleichen Wert hat.$E(R) = E(\Psi(b_1,\dots,b_N))$$E(b_1),\dots,E(b_N)$
• Die Teilnehmer verwenden gemeinsam das Schwellenwertentschlüsselungsprotokoll, um R von E ( R ) wiederherzustellen . (Beachten Sie, dass sie das Schwellenwert-Entschlüsselungsprotokoll nur auf diesen einen Chiffretext anwenden. Die ehrlichen Teilnehmer werden sich weigern, an der Entschlüsselung anderer Chiffretexte teilzunehmen.)$N$$R$$E(R)$
• Jeder beweist irgendwie (vielleicht durch ZK-Beweise), dass er jeden Schritt korrekt ausgeführt hat.

Sie müssten einige Details eingeben, aber ich wette, Sie könnten diese Skizze / Gliederung erweitern, um ein Protokoll zu erhalten, das Ihr Problem effizient und sicher löst.

Meine alte Antwort:

Ich würde mir noch ein sicheres Mehrparteienprotokoll für die Berechnung der Summe ansehen .$S = \sum_j b_j$

$S<N/2$

$S$$R$$S$$R$$Q$$S \in \{Q,N-Q\}$

$i,j$$E(c_{i,j})$$c_{i,j} = b_i \oplus b_j$$\oplus$$E$$\sum_{i<j} c_{i,j}=R$davon. Es müssen einige Details herausgearbeitet werden, und das Bedrohungsmodell entspricht möglicherweise nicht Ihren Erwartungen, aber es ist möglich, dass Sie in der Lage sind, so etwas zum Laufen zu bringen.