Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Lernmittel:
Vollständig homomorphe Verschlüsselung I: Theorie und Grundlagen (Lehrer Yu Yu von der Shanghai Jiao Tong University)
Vollständig homomorphe Verschlüsselung II: Theorie und Konstruktion der vollständig homomorphen Verschlüsselung (Lehrer Xiang Xie)

---

Heutzutage basieren die vollständig homomorphen Verschlüsselungsschemata der zweiten Generation (wie BGV und BFV) und der dritten Generation alle auf LWE. Jetzt basieren auch die erweiterten vollständig homomorphen Schemata auf LWE, daher fasst dieser Artikel das Grundwissen von LWE zusammen.
Bedenken Sie zunächst, wir möchten eine Nummer verschlüsseln$S$, jetzt mit einer Reihe von$A_{ichchchchch}$Rechts$S$Verschlüsseln und abrufen$A_{ichchchchch}S$Tatsächlich kann es durch Lösen des größten gemeinsamen Teilers GCD gelöst werden$S$ .Wenn jedoch ein zufälliges Rauschen hinzugefügt wird$t_{ichchchchch}$,erhalten$A_{ichchchchch}S+t_{ichchchchch}$, dann wird es schwierig zu lösen sein$S$ Wert. Dieser Prozess ist mein einfaches Verständnis von LWE. Der sogenannte Fehler ist ein Rauschen.

Der Berechnungsprozess der vollständig homomorphen Verschlüsselung ist in drei Schritte unterteilt: Schlüsselgenerierung KeyGen, Verschlüsselung Enc, homomorphe Berechnung Eval und Entschlüsselung Dec. ,

KeyGen:

Konstruieren Sie zunächst die obige Gleichung,$S\cdot A+t=SA+t$, und holen Sie sich dann den öffentlichen Schlüssel pk ($-A$Und$SA+t$Spleißen) und der private Schlüssel sk ($S$ und 1 Spleißen). Daher wird erhalten, dass das Ergebnis der Multiplikation zwischen pk und sk ein Zufallsrauschen e (nahe 0) ist.

Enc:

Der für die Verschlüsselung verwendete öffentliche Schlüssel pk, r ist ein Zufallsvektor, der nur 0 oder 1 enthält, und m ist die zu verschlüsselnde Information (in das unterste Bit des Vektors eingefügt).

Dez:

Nachdem Sie das innere Produkt des für die Entschlüsselung verwendeten privaten Schlüssels sk und ct berechnet haben, suchen Sie nach Mod 2, um das Entschlüsselungsergebnis zu erhalten.

Nachweis der Richtigkeit:

Multiplizieren Sie sk und pk, um 2e zu erhalten (die von KeyGen erfüllte Bedingung), und bilden Sie dann das innere Produkt mit r, um ein kleines gleichmäßiges Rauschen zu erhalten. Das Endergebnis ist m+ ein kleines gleichmäßiges Rauschen, sodass das Rauschen durch Mod 2 eliminiert werden kann. Holen Sie sich das Entschlüsselungsergebnis m. Aus diesem Grund ist das konstruierte Rauschen 2e und nicht e. Nach meinem Verständnis ist es praktisch, Mod 2 zu verwenden, um das Rauschen während der Entschlüsselung zu eliminieren.

Sicherheitsnachweis:

Wenn pk pseudozufällig ist und r eine ausreichend hohe Entropie aufweist (d. h. die Zufälligkeit ist stark?), sind sowohl pk als auch pk mal r pseudozufällig. Nach der Addition von natürlichen und Vektoren mit m ist das Verschlüsselungsergebnis ebenfalls pseudozufällig.

Das Folgende ist die formelhafte Beschreibung von Lehrer Xiang Xie:
Verschlüsselungsformel: Chiffretext c = öffentlicher Schlüssel pk ✖️ Zufall r + Klartext m
Entschlüsselungsformel: Klartext m = <Chiffretext sk, privater Schlüssel sk> mod q mod 2

Auf dieser Basis kann Mod 2 verwendet werden, um den Wert von Klartext m zu entschlüsseln. Solange das Rauschen gering genug ist, kann die Genauigkeit garantiert werden.
Hier gibt es etwas, das unterschieden werden muss: das oben Genannte$PK=(A,B=A{S}^{\prime }+2t)$ist die BGV-Lösung und BFV ist$PK=(A,B=A{S}^{\prime }+t)$Der Unterschied besteht darin, dass BGV Informationen in niedrigen Bits codiert, während BFV Nachrichten in hohen Bits codiert (wird beim Erlernen von BFV erklärt).

Eval (additiver Homomorphismus und multiplikativer Homomorphismus):

Beachten Sie, dass homomorphe Additionen oder Multiplikationen zu einer erheblichen Rauschakkumulation führen und die Multiplikation einen quadratischen Wachstumstrend aufweist.
Lassen Sie uns dann darüber sprechen, wie das Ergebnis der homomorphen Multiplikation entschlüsselt wird. Sie können die folgende Formel sehen: Die Multiplikation zweier Chiffretexte entspricht der Berechnung des Tensorprodukts des Chiffretexts bzw. des privaten Schlüssels und der anschließenden Berechnung des inneren Produkts. Offensichtlich haben sich also sowohl der Chiffretext als auch der private Schlüssel verdoppelt. Beispiel ist ein Äquivalenzbeweis.

Die Frage ist also, wie man die Chiffretextgröße und die Größe des privaten Schlüssels nach der homomorphen Multiplikation wiederherstellen kann. Dies ist das Problem, das Key Switching löst.

Das Folgende ist die Beschreibung von Lehrer Xiang Xie:

Tastenumschaltung

Ziel ist es, die Größe des Chiffretexts und des privaten Schlüssels wieder auf lineare Größe zu bringen.

Finden Sie nun die Multiplikation der Chiffretexte c1 und c2:

Der obige Prozess basiert auf dem Konzept der Bitzerlegung:

Das Folgende ist die Beschreibung von Lehrer Xiang Xie:

Das Ziel des Key Switching: den privaten Schlüssel umwandeln$\tilde{S}$runter$\tilde{C}$ In privaten Schlüssel umwandeln$S$runter$C$,Und$\tilde{C}$Und$C$Sie sind alle mit demselben Klartext verschlüsselt.
Ein Kernkonzept hierbei ist der Key Switching Key (KSK), also die Verwendung eines privaten Schlüssels$S$zu verschlüsseln$\tilde{S}$。

Durch den Key Switching-Prozess kann der private Schlüssel abgeleitet werden$S\otimes S$wurde linear$S$, während sich der Chiffretext von ändert$\tilde{C}$wurde linear$C$ .Und aus der letzten Zeile der Formel ist ersichtlich, dass nach dem Schlüsselwechsel$⟨C,S⟩$und das Original$⟨\tilde{C},S\otimes S⟩$Es gibt einen Geräuschunterschied zwischen$2{\tilde{C}}^T\tilde{t}$ , dieser Teil kann sehr groß sein! Daher gibt es hier noch keine Möglichkeit, Key Switching zu implementieren.

Hier wird eine Gadget-Matrix G vorgestellt:

Daher sieht der Vorgang des Schlüsselwechsels wie folgt aus:

Zu diesem Zeitpunkt ist der zusätzliche Fehler sehr gering.
Zusammenfassend lässt sich sagen, dass durch Key Switching der ursprüngliche private Schlüssel erhalten wird$\tilde{S}=S\otimes S$runter$\tilde{C}=C\otimes C$, wird in einen privaten Schlüssel umgewandelt$S$runter$C$Achten Sie nach dem Schlüsselwechsel auf den Schlüssel$S,C$Es handelt sich nicht um die Originalwerte (doppelte Prüfung).

Bei BGV nimmt das Rauschen der Addition linear zu, und das Rauschen der Multiplikation nimmt zwar direkt zu, wodurch die Multiplikation (wodurch sk extrem groß wird) unterstützt wird, ist das Rauschen tatsächlich ein sehr kleines Rauschen, das zum ursprünglichen Multiplikationsrauschen addiert wird ist auch sehr groß. Daher muss dieser Lärm weiter reduziert werden.

Modulreduzierung

Zu diesem Zeitpunkt wurden homomorphe Multiplikations- und Additionsberechnungen mit geringer Tiefe durch LWE implementiert. Bei der Schlüsselumschaltung wird für jede Schicht ein neuer Schlüssel verwendet. Mit zunehmender Berechnungstiefe ist die Ausweitung des Rauschens jedoch explosionsartig, sodass sie noch nicht ausgeglichen ist . FHE (kann FHE in einer bestimmten Tiefe berechnen).
Jetzt hoffen wir, einen FHE zu implementieren, der eine bestimmte Tiefe berechnen kann, ohne Bootstrapping zu verwenden, das eine Modulo-Konvertierung erfordert.

Ich verstehe den Prozess in der Mitte nicht ganz. Kurz gesagt, es geht darum, den Chiffretext c vom Domänenmodulo q in den Domänenmodulo p (p<) umzuwandeln
Hier ist ein konkretes Beispiel:
Wenn keine Modulreduzierung durchgeführt wird, nimmt das Rauschen mit zunehmender Tiefe in einem doppelt exponentiellen Trend zu, und nach Level >= 3 treten Entschlüsselungsfehler auf.

Wenn die Modulreduzierung auf jeder Ebene durchgeführt wird, wird das Rauschen ebenfalls innerhalb eines Absolutwertbereichs gehalten, auf Kosten einer kontinuierlichen Modulreduzierung.

Wenn Sie also einen abgestuften FHE implementieren möchten, können Sie einen Modul festlegen$B^D$, dann können Sie eine Tiefe von berechnen$D$Schaltung (wo$B$ ist die Rauschobergrenze des aktualisierten Chiffretexts).Berechnet$D$Nach der Tiefe sollte der Modul auf reduziert werden$B$ , um sicherzustellen, dass zu diesem Zeitpunkt kein Entschlüsselungsfehler vorliegt. BGV ist ein abgestufter FHE.