Κοινή χρήση τεχνολογίας

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

Πόροι μάθησης:
Πλήρως ομομορφική κρυπτογράφηση I: Θεωρία και θεμελίωση (Δάσκαλος Yu Yu από το Πανεπιστήμιο Shanghai Jiao Tong)
Πλήρως Ομομορφική Κρυπτογράφηση II: Θεωρία και Κατασκευή Πλήρως Ομομορφικής Κρυπτογράφησης (Δάσκαλος Xiang Xie)

---

Σήμερα, τα σχήματα κρυπτογράφησης δεύτερης γενιάς (όπως BGV και BFV) και τρίτης γενιάς βασίζονται στο LWE.
Πρώτα σκεφτείτε, θέλουμε να κρυπτογραφήσουμε έναν αριθμό$\mu \iota \kappa \rho ό$, τώρα χρησιμοποιώντας μια σειρά από${έ\nu \alpha }_{{\rm E}\gamma ώ}$σωστά$\mu \iota \kappa \rho ό$Κρυπτογράφηση και λήψη${έ\nu \alpha }_{{\rm E}\gamma ώ}\mu \iota \kappa \rho ό$, στην πραγματικότητα, μπορεί να λυθεί λύνοντας τον μεγαλύτερο κοινό διαιρέτη GCD$\mu \iota \kappa \rho ό$ .Ωστόσο, εάν προστεθεί ένας τυχαίος θόρυβος${\mu \iota }_{{\rm E}\gamma ώ}$,παίρνω${έ\nu \alpha }_{{\rm E}\gamma ώ}\mu \iota \kappa \rho ό+{\mu \iota }_{{\rm E}\gamma ώ}$, τότε θα είναι δύσκολο να λυθεί$\mu \iota \kappa \rho ό$ αξία. Αυτή η διαδικασία είναι η απλή κατανόησή μου για το LWE Το λεγόμενο σφάλμα είναι ένας θόρυβος.

Η διαδικασία υπολογισμού της πλήρως ομομορφικής κρυπτογράφησης χωρίζεται σε τρία βήματα: δημιουργία κλειδιού KeyGen, κρυπτογράφηση Enc, ομομορφικός υπολογισμός Eval και αποκρυπτογράφηση Dec. ,

KeyGen:

Κατασκευάστε πρώτα την παραπάνω εξίσωση,$\mu \iota \kappa \rho ό\cdot {\rm E}{\rm N}{\rm A}+\mu \iota =\mu \iota \kappa \rho ό{\rm E}{\rm N}{\rm A}+\mu \iota$και, στη συνέχεια, λάβετε το δημόσιο κλειδί pk ($-{\rm E}{\rm N}{\rm A}$και$\mu \iota \kappa \rho ό{\rm E}{\rm N}{\rm A}+\mu \iota$μάτισμα), και το ιδιωτικό κλειδί sk ($\mu \iota \kappa \rho ό$ και 1 μάτισμα). Επομένως, προκύπτει ότι το αποτέλεσμα του πολλαπλασιασμού μεταξύ pk και sk είναι τυχαίος θόρυβος e (κοντά στο 0).

Enc：

Το δημόσιο κλειδί pk που χρησιμοποιείται για την κρυπτογράφηση, το r είναι ένα τυχαίο διάνυσμα που περιέχει μόνο 0 ή 1, και το m είναι η πληροφορία που πρέπει να κρυπτογραφηθεί (βάλτε το χαμηλότερο bit του διανύσματος).

Δεκ:

Αφού υπολογίσετε το εσωτερικό γινόμενο του ιδιωτικού κλειδιού sk που χρησιμοποιείται για την αποκρυπτογράφηση και το ct, βρείτε το mod 2 για να λάβετε το αποτέλεσμα αποκρυπτογράφησης.

Απόδειξη ορθότητας:

Πολλαπλασιάστε το sk και το pk για να λάβετε 2e (η συνθήκη που πληροί το KeyGen) και στη συνέχεια κάντε το εσωτερικό γινόμενο με το r για να λάβετε έναν μικρό ομοιόμορφο θόρυβο. Λάβετε το αποτέλεσμα αποκρυπτογράφησης m. Αυτός είναι ο λόγος για τον οποίο ο κατασκευασμένος θόρυβος είναι 2e, όχι e Καταλαβαίνω ότι με την κατασκευή ζυγού τυχαίου θορύβου, είναι βολικό να χρησιμοποιήσετε το mod 2 για την εξάλειψη του θορύβου κατά την αποκρυπτογράφηση.

Απόδειξη ασφάλειας:

Όταν το pk είναι ψευδοτυχαίο και το r έχει αρκετά υψηλή εντροπία (δηλαδή, η τυχαιότητα είναι ισχυρή;), τόσο το pk όσο και το pk επί r είναι ψευδοτυχαία. Μετά την προσθήκη φυσικών και διανυσμάτων με m, το αποτέλεσμα κρυπτογράφησης είναι επίσης ψευδοτυχαίο.

Ακολουθεί η τυπική περιγραφή του δασκάλου Xiang Xie:
Τύπος κρυπτογράφησης: κρυπτογραφημένο κείμενο c = δημόσιο κλειδί pk ✖️ τυχαίο r + απλό κείμενο m
Τύπος αποκρυπτογράφησης: απλό κείμενο m = <κρυπτογραφημένο κείμενο sk, ιδιωτικό κλειδί sk> mod q mod 2

Σε αυτή τη βάση, το mod 2 μπορεί να χρησιμοποιηθεί για την αποκρυπτογράφηση της τιμής του απλού κειμένου m. Εφόσον ο θόρυβος είναι αρκετά μικρός, η ακρίβεια μπορεί να είναι εγγυημένη.
Εδώ πρέπει να ξεχωρίσουμε κάτι: το παραπάνω$\Pi \kappa =({\rm E}{\rm N}{\rm A},\sigma \iota ={\rm E}{\rm N}{\rm A}{\mu \iota \kappa \rho ό}^{\prime }+2\mu \iota )$είναι η λύση BGV και το BFV είναι$\Pi \kappa =({\rm E}{\rm N}{\rm A},\sigma \iota ={\rm E}{\rm N}{\rm A}{\mu \iota \kappa \rho ό}^{\prime }+\mu \iota )$, η διαφορά είναι ότι το BGV κωδικοποιεί πληροφορίες σε χαμηλά bit, ενώ το BFV κωδικοποιεί μηνύματα σε υψηλά bit (θα εξηγηθεί κατά την εκμάθηση του BFV).

Eval (προσθετικός ομομορφισμός και πολλαπλασιαστικός ομομορφισμός):

Σημειώστε ότι η ομομορφική προσθήκη ή πολλαπλασιασμός θα επιφέρει σημαντική συσσώρευση θορύβου και ο πολλαπλασιασμός έχει τετραγωνική τάση ανάπτυξης.
Στη συνέχεια, ας μιλήσουμε για το πώς να αποκρυπτογραφήσουμε το αποτέλεσμα του ομομορφικού πολλαπλασιασμού. Μπορείτε να δείτε τον ακόλουθο τύπο: Ο πολλαπλασιασμός δύο κρυπτογραφημένων κειμένων ισοδυναμεί με την εκτέλεση του τανυστικού γινόμενου του κρυπτογραφημένου κειμένου και του ιδιωτικού κλειδιού αντίστοιχα. Προφανώς, τόσο το κρυπτογραφημένο κείμενο όσο και το ιδιωτικό κλειδί έχουν διπλασιαστεί σε μέγεθος. Παράδειγμα είναι μια απόδειξη ισοδυναμίας.

Το ερώτημα λοιπόν είναι, πώς να επαναφέρετε το μέγεθος κρυπτογραφημένου κειμένου και το μέγεθος του ιδιωτικού κλειδιού μετά από ομομορφικό πολλαπλασιασμό; Αυτό είναι το πρόβλημα που λύνει το Key Switching.

Ακολουθεί η περιγραφή του δασκάλου Xiang Xie:

Εναλλαγή κλειδιού

Ο στόχος είναι να επαναφέρετε το μέγεθος του κρυπτογραφημένου κειμένου και του ιδιωτικού κλειδιού σε γραμμικό μέγεθος.

Τώρα βρείτε τον πολλαπλασιασμό των κρυπτογραφημένων κειμένων c1 και c2:

Η παραπάνω διαδικασία βασίζεται στην έννοια της αποσύνθεσης bit:

Ακολουθεί η περιγραφή του δασκάλου Xiang Xie:

Ο στόχος της εναλλαγής κλειδιών: μετατροπή του ιδιωτικού κλειδιού$\widetilde{\mu \iota \kappa \rho ό}$κάτω$\widetilde{\nu \tau o}$ Μετατροπή σε ιδιωτικό κλειδί$\mu \iota \kappa \rho ό$κάτω$\nu \tau o$,και$\widetilde{\nu \tau o}$και$\nu \tau o$Είναι όλα κρυπτογραφημένα με το ίδιο απλό κείμενο.
Μια βασική ιδέα εδώ είναι το Key Switching Key (KSK), που σημαίνει τη χρήση ιδιωτικού κλειδιού$\mu \iota \kappa \rho ό$να κρυπτογραφήσει$\widetilde{\mu \iota \kappa \rho ό}$。

Μέσω της διαδικασίας Key Switching, το ιδιωτικό κλειδί μπορεί να προέρχεται από$\mu \iota \kappa \rho ό\otimes \mu \iota \kappa \rho ό$έγινε γραμμική$\mu \iota \kappa \rho ό$, ενώ το κρυπτογραφημένο κείμενο αλλάζει από$\widetilde{\nu \tau o}$έγινε γραμμική$\nu \tau o$ .Και μπορεί να φανεί από την τελευταία γραμμή του τύπου ότι μετά το Key Switching$⟨\nu \tau o,\mu \iota \kappa \rho ό⟩$και το πρωτότυπο$⟨\widetilde{\nu \tau o},\mu \iota \kappa \rho ό\otimes \mu \iota \kappa \rho ό⟩$Υπάρχει διαφορά θορύβου μεταξύ$2{\widetilde{\nu \tau o}}^{{\rm T}}\widetilde{\mu \iota }$ , αυτό το μέρος μπορεί να είναι πολύ μεγάλο! Επομένως, δεν υπάρχει ακόμα τρόπος να εφαρμοστεί η εναλλαγή κλειδιών εδώ.

Ένας πίνακας Gadget G παρουσιάζεται εδώ:

Επομένως, η διαδικασία της εναλλαγής κλειδιού γίνεται ως εξής:

Σε αυτό το σημείο, το προστιθέμενο σφάλμα είναι πολύ μικρό.
Για να συνοψίσουμε, μέσω Key Switching, το αρχικό ιδιωτικό κλειδί$\widetilde{\mu \iota \kappa \rho ό}=\mu \iota \kappa \rho ό\otimes \mu \iota \kappa \rho ό$κάτω$\widetilde{\nu \tau o}=\nu \tau o\otimes \nu \tau o$, μετατρέπεται σε ιδιωτικό κλειδί$\mu \iota \kappa \rho ό$κάτω$\nu \tau o$, δώστε προσοχή στο κλειδί μετά την εναλλαγή κλειδιού$\mu \iota \kappa \rho ό,\nu \tau o$Δεν είναι οι αρχικές τιμές (διπλός έλεγχος).

Για το BGV, ο θόρυβος της πρόσθεσης αυξάνεται γραμμικά και ο θόρυβος του πολλαπλασιασμού αυξάνεται πλήρως είναι επίσης πολύ μεγάλο. Επομένως, αυτός ο θόρυβος πρέπει να μειωθεί περαιτέρω.

Μείωση συντελεστή

Σε αυτό το σημείο, οι υπολογισμοί ομομορφικού πολλαπλασιασμού και πρόσθεσης με μικρό βάθος έχουν εφαρμοστεί μέσω της αλλαγής κλειδιού για κάθε στρώμα, ωστόσο, καθώς το βάθος υπολογισμού βαθαίνει, η επέκταση του θορύβου είναι εκρηκτική. FHE (μπορεί να υπολογίσει FHE σε καθορισμένο βάθος).
Τώρα ελπίζουμε να εφαρμόσουμε ένα FHE που μπορεί να υπολογίσει ένα συγκεκριμένο βάθος χωρίς τη χρήση bootstrapping, το οποίο απαιτεί μετατροπή modulo.

Δεν καταλαβαίνω ακριβώς τη διαδικασία στη μέση, είναι ο μετασχηματισμός του κρυπτογραφημένου κειμένου c από τον τομέα modulo q στον τομέα modulo p (p<.
Εδώ είναι ένα συγκεκριμένο παράδειγμα:
Εάν δεν εκτελεστεί η Μείωση Modulus, ο θόρυβος θα αυξηθεί με διπλή εκθετική τάση καθώς το βάθος βαθαίνει και θα προκύψουν σφάλματα αποκρυπτογράφησης μετά το επίπεδο >= 3.

Εάν εκτελείται μείωση συντελεστή σε κάθε επίπεδο, ο θόρυβος θα διατηρείται επίσης εντός ενός εύρους απόλυτης τιμής, με κόστος συνεχούς μείωσης του συντελεστή.

Έτσι, εάν θέλετε να εφαρμόσετε ένα επίπεδο FHE, μπορείτε να ορίσετε ένα συντελεστή${\sigma \iota }^{\rho \epsilon }$, τότε μπορείτε να υπολογίσετε ένα βάθος$\rho \epsilon$κύκλωμα (όπου$\sigma \iota$ είναι το άνω όριο του θορύβου του ανανεωμένου κρυπτογραφημένου κειμένου).Υπολογίστηκε$\rho \epsilon$Μετά το βάθος, ο συντελεστής πρέπει να μειωθεί σε$\sigma \iota$ , για να βεβαιωθείτε ότι δεν υπάρχει σφάλμα στην αποκρυπτογράφηση αυτή τη στιγμή. Το BGV είναι ένα ισοπεδωμένο FHE.