Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

1. Problemstellung

Die Arbeit adressiert eine fundamentale Einschränkung im Bereich des Homomorphen Verschlüsselung (HE), speziell im CKKS-Schema (Cheon-Kim-Kim-Song), welches für approximative Rechnungen mit reellen Zahlen optimiert ist.

• Fehlende Nicht-Linearität: CKKS unterstützt nativ nur Addition und Multiplikation. Viele kryptographische Primitive und Datenverarbeitungsaufgaben erfordern jedoch diskontinuierliche Operationen wie die Modulo-Funktion ($x \mod p$).
• Schwierigkeit der Approximation: Die Modulo-Funktion ist periodisch und weist Sprungstellen auf. Bestehende Methoden zur polynomialen Approximation (z. B. basierend auf Sinus-Funktionen oder Taylor-Reihen) liefern nur in begrenzten Teilbereichen des Eingabedomänen genaue Ergebnisse. Für den gesamten Eingabebereich (insbesondere bei kleinen ganzen Zahlen) fehlt bisher eine präzise, globale Approximation.
• Ineffizienz bei der Dateneingabe: In ressourcenbeschränkten Umgebungen (IoT, Smart Home) ist die Verschlüsselung und das Hochladen vieler kleiner Datenpunkte ineffizient, da jedes Element oft einen eigenen Verschlüsselungstext (Ciphertext) benötigt oder die Slots (Platz im Ciphertext) nicht optimal genutzt werden.

2. Methodik

Die Autoren schlagen einen mehrstufigen Ansatz vor, der von einer mathematischen Approximation bis hin zu praktischen Packungsschemata reicht.

A. Präzise Modulo-Approximation

Statt die Modulo-Funktion über trigonometrische Reihen zu approximieren, nutzen die Autoren Polynominterpolation in Kombination mit Chebyshev-Reihen.

• Diskrete Stichproben: Da die Anwendung auf ganzzahlige Eingaben beschränkt ist, werden diskrete Punkte $(i, i \mod p)$ für $i \in [0, B]$ als Trainingsdaten verwendet.
• Chebyshev-Basis: Um das Runge-Phänomen (Oszillationen bei hohen Polynomgraden) zu vermeiden und die numerische Stabilität zu gewährleisten, wird die Funktion als Summe von Chebyshev-Polynomen $T_n(x)$ dargestellt.
• Koeffizienten-Optimierung: Ein lineares Gleichungssystem wird mittels der Least-Squares-Methode gelöst. Um die Stabilität in CKKS zu gewährleisten (da große Koeffizienten das Rauschen verstärken), wird ein Skalierungsfaktor $\delta$ eingeführt, der sicherstellt, dass alle Koeffizienten und Zwischenergebnisse während der homomorphen Auswertung unter 1 bleiben.
• Effiziente Auswertung: Für die Auswertung hoher Polynomgrade wird die Paterson-Stockmeyer-Methode (adaptiert für Chebyshev-Basen) verwendet, um die multiplikative Tiefe zu minimieren.

B. Daten-Packungsschemata (Data Packing)

Basierend auf der homomorphen Modulo-Operation werden zwei neue Schemata entwickelt, um kleine Ganzzahlen effizient in einem einzigen Ciphertext zu packen und später wieder zu entpacken:

1. BitStack:

   • Prinzip: Daten werden binär dargestellt und wie Bits in einem großen Integer „gestapelt" (z. B. $x = a_1 + a_2 \cdot 2^{l_1} + \dots$).
   • Entpacken: Erfolgt sequenziell durch wiederholte Anwendung der homomorphen Modulo-Operation ($ModP(x, 2^{l_1})$) und Subtraktion.
   • Vorteil: Sehr kompakte Struktur, keine Redundanz.
   • Nachteil: Sequenzielle Entpackung erfordert hohe multiplikative Tiefe; Fehler akkumulieren sich von Schicht zu Schicht.

2. CRTStack (Chinesischer Restsatz):

   • Prinzip: Daten werden als Restklassensystem modulo paarweise teilerfremder Moduli $P_i$ kodiert ($x \equiv a_i \mod P_i$).
   • Entpacken: Kann parallel erfolgen, da jede Schicht nur eine einzelne Modulo-Operation benötigt ($a_i = x \mod P_i$).
   • Vorteil: Parallele Entpackung, keine Fehlerakkumulation zwischen Schichten.
   • Nachteil: Benötigt eine breitere Approximationsrange für die Modulo-Funktion, was höhere Polynomgrade erfordert.

C. Weitere Anwendungen

• Homomorphes Runden: Durch Kombination von Modulo mit Multiplikation können Floor-, Ceil- und Round-Funktionen präzise implementiert werden.
• Umwandlung von Secret Shares: Ein neuer Ansatz zur Umwandlung von additiven Geheimnisanteilen (Secret Shares) direkt in CKKS-Ciphertexts ohne Änderung des Secret-Sharing-Schemas. Dies überbrückt die Lücke zwischen Secure Multi-Party Computation (MPC) und HE.

3. Wichtige Beiträge

1. Globale Modulo-Approximation: Entwicklung einer Methode, die die Modulo-Funktion über den gesamten Eingabebereich ganzer Zahlen mit hoher Genauigkeit approximiert (im Gegensatz zu bisherigen Teilbereichslösungen).
2. BitStack & CRTStack: Zwei effiziente Packungsschemata, die die Auslastung des CKKS-Plaintext-Raums drastisch verbessern und das Hochladen verschlüsselter Daten beschleunigen.
3. Präzises Runden: Implementierung einer homomorphen Rundungsfunktion mit Fehlern bis zu $10^{-10}$.
4. Secret-Share-zu-HE-Konvertierung: Der erste vollständige Konvertierungsschema von additiven Secret Shares zu CKKS-Ciphertexts, das ausschließlich auf CKKS-Operationen basiert.

4. Ergebnisse und Evaluation

Die Experimente wurden auf einer Intel Xeon Gold CPU unter Verwendung der OpenFHE-Bibliothek durchgeführt.

• Approximationsgenauigkeit: Die vorgeschlagene Methode erreicht eine durchschnittliche absolute Fehlergröße von bis zu $10^{-8}$ (bei Polynomgraden > 45). Dies ist signifikant genauer als bestehende Methoden (z. B. Lee et al. [LLL+21]), die bei weiten Eingabebereichen Fehler von ca. 2,0 aufweisen.
• Daten-Packung:
  • Die neuen Schemata reduzieren die Verschlüsselungszeit auf der Client-Seite und die Upload-Datenmenge (Traffic) um bis zu zwei Größenordnungen im Vergleich zur Standard-CKKS-Verschlüsselung.
  • Vergleich mit Transcipher (Rubato): Das vorgeschlagene Schema ist bei moderaten Bandbreiten (400–600 KB/s) schneller als der Transcipher-Ansatz. Die Entpackzeit ist ca. 1,6-mal schneller als bei Rubato, und der Fehler ist um eine Größenordnung geringer.
• Runden: Die Floor-Funktion erreicht Fehler in der Größenordnung von $10^{-10}$.
• Secret Shares: Die Umwandlung von Secret Shares zu HE ist erfolgreich, wobei die Fehler auch bei vielen Parteien (Parties) bei ca. $10^{-8}$ bleiben.

5. Bedeutung und Fazit

Die Arbeit löst ein langjähriges Problem in der Anwendung von CKKS auf diskrete Daten: die effiziente und präzise Handhabung der Modulo-Operation.

• Praktische Relevanz: Die Methode ermöglicht die effiziente Verarbeitung kleiner ganzer Zahlen (z. B. genomische Daten, Bildpixel, Sensorwerte) in homomorphen Umgebungen, was für IoT und Edge-Computing entscheidend ist.
• Ressourceneffizienz: Durch die verbesserte Slot-Auslastung (Packing) wird der Kommunikations-Overhead massiv reduziert, was die Skalierbarkeit von HE-Anwendungen in der Praxis erhöht.
• Neue Möglichkeiten: Die Fähigkeit, Secret Shares direkt in HE umzuwandeln, eröffnet neue Wege für hybride MPC-HE-Protokolle, bei denen Daten sicher zwischen verschiedenen kryptographischen Paradigmen transferiert werden können.

Obwohl die Methode derzeit auf kleine Eingabebereiche (typischerweise einige hundert Werte) beschränkt ist, bietet sie einen robusten Baustein für zukünftige privacy-preserving Anwendungen, die auf ganzzahligen oder diskreten Daten basieren.