Vitalik Buterin μέσω του Ιστολόγιο Vitalik Buterin
Αυτός είναι ένας καθρέφτης της ανάρτησης στο https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Προειδοποίηση ενεργοποίησης: μαθηματικά.
Ένα από τα βασικά κρυπτογραφικά πρωτόγονα πίσω από διάφορες κατασκευές, συμπεριλαμβανομένων των ντετερμινιστικών υπογραφών κατωφλίου, των zk-SNARK και άλλων απλούστερων μορφών αποδείξεων μηδενικής γνώσης είναι το ζεύγος ελλειπτικής καμπύλης. Τα ζεύγη ελλειπτικών καμπυλών (ή «διγραμμικοί χάρτες») είναι μια πρόσφατη προσθήκη σε μια 30ετή ιστορία χρήσης ελλειπτικών καμπυλών για κρυπτογραφικές εφαρμογές, συμπεριλαμβανομένης της κρυπτογράφησης και των ψηφιακών υπογραφών. Τα ζεύγη εισάγουν μια μορφή «κρυπτογραφημένου πολλαπλασιασμού», επεκτείνοντας σε μεγάλο βαθμό αυτό που μπορούν να κάνουν τα πρωτόκολλα που βασίζονται σε ελλειπτικές καμπύλες. Ο σκοπός αυτού του άρθρου θα είναι να εξετάσει λεπτομερώς τα ζεύγη ελλειπτικών καμπυλών και να εξηγήσει μια γενική περιγραφή του τρόπου λειτουργίας τους.
Δεν αναμένεται να καταλάβετε τα πάντα εδώ την πρώτη φορά που θα το διαβάσετε ή ακόμα και τη δέκατη φορά. αυτό το πράγμα είναι πραγματικά δύσκολο. Αλλά ελπίζουμε ότι αυτό το άρθρο θα σας δώσει τουλάχιστον μια ιδέα για το τι συμβαίνει κάτω από την κουκούλα.
Οι ίδιες οι ελλειπτικές καμπύλες είναι ένα πολύ μη τετριμμένο θέμα για κατανόηση, και αυτό το άρθρο γενικά θα υποθέσει ότι γνωρίζετε πώς λειτουργούν. αν δεν το κάνετε, προτείνω αυτό το άρθρο εδώ ως εκκίνηση: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Ως σύντομη περίληψη, η κρυπτογραφία ελλειπτικής καμπύλης περιλαμβάνει μαθηματικά αντικείμενα που ονομάζονται «σημεία» (αυτά είναι κυριολεκτικά δισδιάστατα σημεία με συντεταγμένες (�,�)), με ειδικούς τύπους για την πρόσθεση και την αφαίρεση τους (δηλ. για τον υπολογισμό των συντεταγμένων του �= �+�), και μπορείτε επίσης να πολλαπλασιάσετε ένα σημείο με έναν ακέραιο (δηλ. �⋅�=�+�+…+�, αν και υπάρχει πολύ πιο γρήγορος τρόπος να το υπολογίσετε εάν το � είναι μεγάλο).
Δείτε πώς φαίνεται γραφικά η προσθήκη σημείων.
Υπάρχει ένα ειδικό σημείο που ονομάζεται "σημείο στο άπειρο" (�), το ισοδύναμο του μηδενός σε αριθμητική σημείο. συμβαίνει πάντα ότι �+�=�. Επίσης, μια καμπύλη έχει ένα "τάξη"; υπάρχει ένας αριθμός � τέτοιος ώστε �⋅�=� για οποιοδήποτε � (και φυσικά, �⋅(�+1)=�,��⋅(7⋅�+5)=�⋅5, και ούτω καθεξής). Υπάρχει επίσης κάποιο κοινά αποδεκτό «σημείο γεννήτριας» �, το οποίο εννοείται ότι κατά κάποιο τρόπο αντιπροσωπεύει τον αριθμό 1. Θεωρητικά, οποιοδήποτε σημείο σε μια καμπύλη (εκτός από το �) μπορεί να είναι �. το μόνο που έχει σημασία είναι ότι � είναι τυποποιημένο.
Τα ζεύγη προχωρούν ένα βήμα παραπέρα καθώς σας επιτρέπουν να ελέγξετε ορισμένα είδη πιο περίπλοκων εξισώσεων σε ελλειπτικά σημεία καμπύλης — για παράδειγμα, εάν �=�⋅�,�=�⋅� και �=�⋅�, μπορείτε να ελέγξετε αν ή όχι �⋅�=�, έχοντας μόνο �,� και � ως εισόδους. Αυτό μπορεί να φαίνεται ότι οι θεμελιώδεις εγγυήσεις ασφαλείας των ελλειπτικών καμπυλών έχουν παραβιαστεί, καθώς οι πληροφορίες σχετικά με το � διαρρέουν μόνο από τη γνώση του P, αλλά αποδεικνύεται ότι η διαρροή περιορίζεται σε μεγάλο βαθμό — συγκεκριμένα, η αποφασιστικό πρόβλημα Diffie Hellman είναι εύκολο, αλλά το υπολογιστικό πρόβλημα Diffie Hellman (γνωρίζοντας τα � και � στο παραπάνω παράδειγμα, χρήση υπολογιστή �=�⋅�⋅�) και το πρόβλημα διακριτού λογάριθμου (ανάκτηση � από �) παραμένουν υπολογιστικά ανέφικτα (τουλάχιστον, αν ήταν πριν).
Ένας τρίτος τρόπος για να δούμε τι κάνουν τα ζεύγη, και που είναι ίσως πιο διαφωτιστικός για τις περισσότερες περιπτώσεις χρήσης που αναφερόμαστε, είναι ότι αν δείτε τα ελλειπτικά σημεία καμπύλης ως μονόδρομους κρυπτογραφημένους αριθμούς (δηλαδή, ���� ���(�)=�⋅�=�), τότε ενώ τα μαθηματικά της παραδοσιακής ελλειπτικής καμπύλης σάς επιτρέπουν να ελέγξετε γραμμικός περιορισμοί στους αριθμούς (π.χ. εάν �=�⋅�,�=�⋅� και �=�⋅�, ο έλεγχος 5⋅�+7⋅�=11⋅� είναι πραγματικά ελέγχοντας ότι 5⋅�+7⋅�=11⋅�), τα ζεύγη σάς επιτρέπουν να ελέγξετε τετραγωνικός περιορισμοί (π.χ. έλεγχος �(�,�)⋅�(�,�⋅5)=1 είναι πραγματικά ελέγχοντας ότι �⋅�+5=0). Και η μετάβαση στο τετράγωνο είναι αρκετή για να μας αφήσει να δουλέψουμε με ντετερμινιστικές υπογραφές κατωφλίου, τετραγωνικά αριθμητικά προγράμματα και όλα αυτά τα άλλα καλά πράγματα.
Τώρα, τι είναι αυτός ο αστείος �(�,�) τελεστής που παρουσιάσαμε παραπάνω; Αυτό είναι το ζευγάρωμα. Οι μαθηματικοί το αποκαλούν επίσης μερικές φορές α διγραμμικός χάρτης; η λέξη "διγραμμικό" εδώ βασικά σημαίνει ότι ικανοποιεί τους περιορισμούς:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Σημειώστε ότι τα + και ⋅ μπορούν να είναι αυθαίρετοι τελεστές. όταν δημιουργείτε φανταχτερά νέα είδη μαθηματικών αντικειμένων, η αφηρημένη άλγεβρα δεν ενδιαφέρεται για το πώς είναι το + και το ⋅ ορίζεται, αρκεί να είναι συνεπείς με τους συνήθεις τρόπους, π.χ. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) και (�⋅�)+(�⋅�)=(�+�)⋅�.
Αν τα �, �, � και � ήταν απλά αριθμοί, τότε η δημιουργία ενός απλού ζευγαρώματος είναι εύκολη: μπορούμε να κάνουμε �(�,�)=2��. Τότε, μπορούμε να δούμε:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Είναι διγραμμικό!
Ωστόσο, τέτοια απλά ζεύγη δεν είναι κατάλληλα για κρυπτογραφία, επειδή τα αντικείμενα στα οποία εργάζονται είναι απλοί ακέραιοι αριθμοί και είναι πολύ εύκολο να αναλυθούν. Οι ακέραιοι διευκολύνουν τη διαίρεση, τον υπολογισμό λογαρίθμων και την πραγματοποίηση διαφόρων άλλων υπολογισμών. Οι απλοί ακέραιοι αριθμοί δεν έχουν έννοια «δημόσιο κλειδί» ή «μονόδρομη συνάρτηση». Επιπλέον, με τη σύζευξη που περιγράφεται παραπάνω μπορείτε να πάτε προς τα πίσω – γνωρίζοντας � και γνωρίζοντας �(�,�), μπορείτε απλά να υπολογίσετε μια διαίρεση και έναν λογάριθμο για να προσδιορίσετε το �. Θέλουμε μαθηματικά αντικείμενα που να είναι όσο το δυνατόν πιο κοντά στα «μαύρα κουτιά», όπου μπορείτε να προσθέσετε, να αφαιρέσετε, να πολλαπλασιάσετε και να διαιρέσετε, αλλά να μην κάνεις τίποτα άλλο. Εδώ μπαίνουν οι ελλειπτικές καμπύλες και τα ζεύγη ελλειπτικών καμπυλών.
Αποδεικνύεται ότι είναι δυνατό να γίνει ένας διγραμμικός χάρτης πάνω από ελλειπτικά σημεία καμπύλης — δηλαδή, να βρεθεί μια συνάρτηση �(�,�) όπου οι είσοδοι � και � είναι ελλειπτικά σημεία καμπύλης και όπου η έξοδος είναι αυτό που ονομάζεται (��)12 στοιχείο (τουλάχιστον στη συγκεκριμένη περίπτωση που θα καλύψουμε εδώ· οι λεπτομέρειες διαφέρουν ανάλογα με τις λεπτομέρειες της καμπύλης, περισσότερα για αυτό αργότερα), αλλά τα μαθηματικά πίσω από αυτό είναι αρκετά περίπλοκα.
Αρχικά, ας καλύψουμε τα κύρια πεδία και τα πεδία επέκτασης. Η όμορφη ελλειπτική καμπύλη στην εικόνα νωρίτερα σε αυτήν την ανάρτηση φαίνεται έτσι μόνο εάν υποθέσετε ότι η εξίσωση καμπύλης ορίζεται χρησιμοποιώντας κανονικούς πραγματικούς αριθμούς. Ωστόσο, εάν χρησιμοποιούμε πραγματικά κανονικούς πραγματικούς αριθμούς στην κρυπτογραφία, τότε μπορείτε να χρησιμοποιήσετε λογάριθμους για να "πηγετε προς τα πίσω" και όλα χαλάνε. Επιπλέον, ο χώρος που απαιτείται για την πραγματική αποθήκευση και αναπαράσταση των αριθμών μπορεί να αυξηθεί αυθαίρετα. Ως εκ τούτου, χρησιμοποιούμε αντ' αυτού αριθμούς στο α πρωταρχικό πεδίο.
Ένα πρώτο πεδίο αποτελείται από το σύνολο των αριθμών 0,1,2…�−1, όπου το � είναι πρώτος και οι διάφορες πράξεις ορίζονται ως εξής:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�-�) % �
�/�:(��⋅���−2) % �
Βασικά, όλα τα μαθηματικά γίνονται modulo � (βλ εδώ για μια εισαγωγή στα αρθρωτά μαθηματικά). Η διαίρεση είναι μια ειδική περίπτωση. κανονικά, το 32 δεν είναι ακέραιος, και εδώ θέλουμε να ασχοληθούμε μόνο με ακέραιους αριθμούς, οπότε αντ' αυτού προσπαθούμε να βρούμε τον αριθμό � έτσι ώστε �⋅2=3, όπου ⋅ φυσικά αναφέρεται στον αρθρωτό πολλαπλασιασμό όπως ορίζεται παραπάνω. Χάρη σε Το μικρό θεώρημα του Φερμά, το τέχνασμα εκθέσεως που φαίνεται παραπάνω κάνει τη δουλειά, αλλά υπάρχει επίσης ένας πιο γρήγορος τρόπος για να το κάνετε, χρησιμοποιώντας το Εκτεταμένος Ευκλείδειος Αλγόριθμος. Ας υποθέσουμε ότι �=7; εδώ είναι μερικά παραδείγματα:
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
Αν παίζετε με αυτό το είδος μαθηματικών, θα παρατηρήσετε ότι είναι απολύτως συνεπή και ικανοποιεί όλους τους συνήθεις κανόνες. Τα δύο τελευταία παραδείγματα παραπάνω δείχνουν πώς (�/�)⋅�=�; μπορείτε επίσης να δείτε ότι (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, και όλες οι άλλες αλγεβρικές ταυτότητες γυμνασίου που γνωρίζετε και αγαπάτε συνεχίζονται να ισχύει επίσης. Στις ελλειπτικές καμπύλες στην πραγματικότητα, τα σημεία και οι εξισώσεις υπολογίζονται συνήθως σε πρωτεύοντα πεδία.
Τώρα, ας μιλήσουμε πεδία επέκτασης. Πιθανότατα έχετε ήδη δει ένα πεδίο επέκτασης στο παρελθόν. το πιο συνηθισμένο παράδειγμα που συναντάτε στα σχολικά βιβλία μαθηματικών είναι το πεδίο των μιγαδικών αριθμών, όπου το πεδίο των πραγματικών αριθμών «επεκτείνεται» με το πρόσθετο στοιχείο −1=�. Βασικά, τα πεδία επέκτασης λειτουργούν λαμβάνοντας ένα υπάρχον πεδίο, στη συνέχεια «εφευρίσκοντας» ένα νέο στοιχείο και ορίζοντας τη σχέση μεταξύ αυτού του στοιχείου και των υπαρχόντων στοιχείων (σε αυτήν την περίπτωση, �2+1=0), διασφαλίζοντας ότι αυτή η εξίσωση δεν ισχύει για οποιονδήποτε αριθμό που βρίσκεται στο αρχικό πεδίο και κοιτάζοντας το σύνολο όλων των γραμμικών συνδυασμών στοιχείων του αρχικού πεδίου και του νέου στοιχείου που μόλις δημιουργήσατε.
Μπορούμε επίσης να κάνουμε επεκτάσεις πρώτων πεδίων. για παράδειγμα, μπορούμε να επεκτείνουμε το mod7 του πρώτου πεδίου που περιγράψαμε παραπάνω με � και, στη συνέχεια, μπορούμε να κάνουμε:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Αυτό το τελευταίο αποτέλεσμα μπορεί να είναι λίγο δύσκολο να καταλάβουμε. Αυτό που συνέβη εκεί ήταν ότι πρώτα αποσυνθέσαμε το γινόμενο σε 4�⋅2+4�⋅�, που δίνει 8�−4, και μετά επειδή εργαζόμαστε σε μαθηματικά mod7 που γίνονται �+3. Για να διαιρέσουμε, κάνουμε:
�/�:(�⋅�(�2−2)) % �
Σημειώστε ότι ο εκθέτης για το μικρό θεώρημα του Φερμά είναι τώρα �2 αντί για �, αν και για άλλη μια φορά, αν θέλουμε να είμαστε πιο αποτελεσματικοί, μπορούμε επίσης να επεκτείνουμε τον Εκτεταμένο Ευκλείδειο Αλγόριθμο για να κάνει τη δουλειά. Σημειώστε ότι ��2−1=1 για οποιοδήποτε � σε αυτό το πεδίο, επομένως ονομάζουμε �2−1 τη «τάξη της πολλαπλασιαστικής ομάδας στο πεδίο».
Με πραγματικούς αριθμούς, το Θεμελιώδες Θεώρημα Άλγεβρας διασφαλίζει ότι η τετραγωνική επέκταση που ονομάζουμε μιγαδικούς αριθμούς είναι "πλήρη" — δεν μπορείτε να την επεκτείνετε περαιτέρω, γιατί για οποιαδήποτε μαθηματική σχέση (τουλάχιστον, οποιαδήποτε μαθηματική σχέση που ορίζεται από έναν αλγεβρικό τύπο) που μπορείτε να βρείτε μεταξύ κάποιου νέου στοιχείου � και με τους υπάρχοντες μιγαδικούς αριθμούς, είναι δυνατό να καταλήξουμε σε τουλάχιστον έναν μιγαδικό αριθμό που να ικανοποιεί ήδη αυτή τη σχέση. Με τα πρώτα πεδία, ωστόσο, δεν έχουμε αυτό το ζήτημα, και έτσι μπορούμε να προχωρήσουμε παραπέρα και να κάνουμε κυβικές επεκτάσεις (όπου η μαθηματική σχέση μεταξύ κάποιου νέου στοιχείου � και υπαρχόντων στοιχείων πεδίου είναι κυβική εξίσωση, άρα τα 1,� και �2 είναι όλα γραμμικά ανεξάρτητα μεταξύ τους), επεκτάσεις υψηλότερης τάξης, επεκτάσεις επεκτάσεων κ.λπ. Και είναι αυτά τα είδη υπερφορτισμένων αρθρωτών μιγαδικών αριθμών πάνω στα οποία βασίζονται τα ζεύγη ελλειπτικών καμπυλών.
Για όσους ενδιαφέρονται να δουν τα ακριβή μαθηματικά που απαιτούνται για τη σύνταξη όλων αυτών των πράξεων σε κώδικα, τα πρώτα πεδία και οι επεκτάσεις πεδίων υλοποιούνται εδώ: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Τώρα, στα ζεύγη ελλειπτικών καμπυλών. Ένα ζευγάρωμα ελλειπτικών καμπυλών (ή μάλλον, η συγκεκριμένη μορφή σύζευξης που θα εξερευνήσουμε εδώ· υπάρχουν και άλλοι τύποι ζευγών, αν και η λογική τους είναι αρκετά παρόμοια) είναι ένας χάρτης �2×��1→��, όπου:
- Το �1 είναι μια ελλειπτική καμπύλη, όπου τα σημεία ικανοποιούν μια εξίσωση της μορφής �2=�3+�, και όπου και οι δύο συντεταγμένες είναι στοιχεία του �� (δηλαδή είναι απλοί αριθμοί, εκτός από το ότι η αριθμητική γίνεται με modulo κάποιου πρώτου αριθμού)
- Το �2 είναι μια ελλειπτική καμπύλη, όπου τα σημεία ικανοποιούν την ίδια εξίσωση με το �1, εκτός από όπου οι συντεταγμένες είναι στοιχεία του (��)12 (δηλ. είναι οι υπερφορτισμένοι μιγαδικοί αριθμοί για τους οποίους μιλήσαμε παραπάνω· ορίζουμε έναν νέο «μαγικό αριθμό ” �, το οποίο ορίζεται από ένα πολυώνυμο 12ου βαθμού όπως �12−18⋅�6+82=0)
- �� είναι ο τύπος αντικειμένου στο οποίο πηγαίνει το αποτέλεσμα της ελλειπτικής καμπύλης. Στις καμπύλες που εξετάζουμε, το �� είναι (��) 12 (ο ίδιος υπερφορτισμένος μιγαδικός αριθμός όπως χρησιμοποιείται στο �2)
Η κύρια ιδιότητα που πρέπει να ικανοποιεί είναι η διγραμμικότητα, που σε αυτό το πλαίσιο σημαίνει ότι:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Υπάρχουν δύο άλλα σημαντικά κριτήρια:
- Αποτελεσματική υπολογισιμότητα (π.χ. μπορούμε να κάνουμε μια εύκολη σύζευξη παίρνοντας απλώς τους διακριτούς λογάριθμους όλων των σημείων και πολλαπλασιάζοντάς τους μαζί, αλλά αυτό είναι υπολογιστικά τόσο δύσκολο όσο το σπάσιμο της κρυπτογραφίας ελλειπτικής καμπύλης εξαρχής, οπότε δεν μετράει)
- Μη εκφυλισμός (σίγουρα, θα μπορούσατε απλώς να ορίσετε �(�,�)=1, αλλά αυτό δεν είναι ιδιαίτερα χρήσιμο ζευγάρωμα)
Πώς θα το κάνουμε αυτό;
Τα μαθηματικά πίσω από το γιατί λειτουργούν οι συναρτήσεις σύζευξης είναι αρκετά δύσκολα και περιλαμβάνουν αρκετή προηγμένη άλγεβρα που ξεπερνά ακόμη και αυτό που έχουμε δει μέχρι τώρα, αλλά θα δώσω μια περίληψη. Πρώτα απ 'όλα, πρέπει να ορίσουμε την έννοια του α διαιρών, βασικά ένας εναλλακτικός τρόπος αναπαράστασης συναρτήσεων σε ελλειπτικά σημεία καμπύλης. Ένας διαιρέτης μιας συνάρτησης βασικά μετράει τα μηδενικά και τα άπειρα της συνάρτησης. Για να δούμε τι σημαίνει αυτό, ας δούμε μερικά παραδείγματα. Ας διορθώσουμε κάποιο σημείο �=(��,��) και ας εξετάσουμε την ακόλουθη συνάρτηση:
�(�,�)=����
Ο διαιρέτης είναι [�]+[−�]−2⋅[�] (οι αγκύλες χρησιμοποιούνται για να αντιπροσωπεύσουν το γεγονός ότι αναφερόμαστε την παρουσία του σημείου � στο σύνολο των μηδενικών και των απείρων της συνάρτησης, όχι το ίδιο το σημείο P. [�]+[�] είναι δεν το ίδιο πράγμα με [�+�]). Το σκεπτικό έχει ως εξής:
- Η συνάρτηση είναι ίση με μηδέν στο �, αφού � is ��, άρα �−��=0
- Η συνάρτηση είναι ίση με μηδέν στο −�, αφού τα −� και � μοιράζονται την ίδια συντεταγμένη
- Η συνάρτηση πηγαίνει στο άπειρο καθώς το � πηγαίνει στο άπειρο, οπότε λέμε ότι η συνάρτηση είναι ίση με το άπειρο στο �. Υπάρχει ένας τεχνικός λόγος για τον οποίο αυτό το άπειρο πρέπει να μετρηθεί δύο φορές, οπότε το � προστίθεται με ένα «πολλαπλάσιο» −2 (αρνητικό επειδή είναι άπειρο και όχι μηδέν, δύο λόγω αυτής της διπλής μέτρησης).
Ο τεχνικός λόγος είναι περίπου αυτός: επειδή η εξίσωση της καμπύλης είναι �3=�2+�,� πηγαίνει στο άπειρο «1.5 φορές γρηγορότερα» από το � για να συμβαδίσει το �2 με το �3. Επομένως, εάν μια γραμμική συνάρτηση περιλαμβάνει μόνο το � τότε αναπαρίσταται ως άπειρο της πολλαπλότητας 2, αλλά εάν περιλαμβάνει το � τότε αναπαρίσταται ως ένα άπειρο του πλήθους 3.
Τώρα, σκεφτείτε μια "συνάρτηση γραμμής":
��+��+�=0
Όπου τα �, � και � επιλέγονται προσεκτικά έτσι ώστε η ευθεία να διέρχεται από τα σημεία � και �. Λόγω του τρόπου με τον οποίο λειτουργεί η πρόσθεση της ελλειπτικής καμπύλης (δείτε το διάγραμμα στην κορυφή), αυτό σημαίνει επίσης ότι διέρχεται από −���. Και ανεβαίνει στο άπειρο ανάλογα με το � και το �, οπότε ο διαιρέτης γίνεται [�]+[�]+[−�−�]−3⋅[�].
Γνωρίζουμε ότι κάθε «ορθολογική συνάρτηση» (δηλ. μια συνάρτηση που ορίζεται μόνο χρησιμοποιώντας έναν πεπερασμένο αριθμό +,−,⋅ και / πράξεων στις συντεταγμένες του σημείου) αντιστοιχεί μοναδικά σε κάποιον διαιρέτη, μέχρι τον πολλαπλασιασμό με μια σταθερά (δηλ. αν δύο συναρτήσεις � και � έχουν τον ίδιο διαιρέτη, τότε �=�⋅� για κάποια σταθερά �).
Για οποιεσδήποτε δύο συναρτήσεις � και �, ο διαιρέτης του �⋅� ισούται με τον διαιρέτη του � συν τον διαιρέτη του � (στα σχολικά βιβλία μαθηματικών, θα δείτε (�⋅�)=(�)+(�)), έτσι για παράδειγμα αν �(�,�)=����, τότε (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; Τα � και −� είναι «τριπλά μετρημένα» για να εξηγήσουν το γεγονός ότι το �3 προσεγγίζει το 0 σε αυτά τα σημεία «τρεις φορές πιο γρήγορα» με μια συγκεκριμένη μαθηματική έννοια.
Σημειώστε ότι υπάρχει ένα θεώρημα που δηλώνει ότι εάν "αφαιρέσετε τις αγκύλες" από έναν διαιρέτη μιας συνάρτησης, τα σημεία πρέπει να αθροιστούν σε �([�]+[�]+[−�−�]−3⋅[ Το �] ταιριάζει ξεκάθαρα, ως �+������−3⋅�=�), και κάθε διαιρέτης που έχει αυτήν την ιδιότητα είναι ο διαιρέτης μιας συνάρτησης.
Τώρα, είμαστε έτοιμοι να δούμε τα ζευγάρια Tate. Εξετάστε τις ακόλουθες συναρτήσεις, που ορίζονται μέσω των διαιρετών τους:
- (��)=�⋅[�]−�⋅[�], όπου � είναι η τάξη του �1, δηλ. �⋅�=� για οποιαδήποτε �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Τώρα, ας δούμε το προϊόν ��⋅��⋅��. Ο διαιρέτης είναι:
�⋅[�]−.
Το οποίο απλοποιεί τακτοποιημένα σε:
�⋅[�+�]−�⋅[�]
Παρατηρήστε ότι αυτός ο διαιρέτης έχει ακριβώς την ίδια μορφή με τον διαιρέτη για τα �� και �� παραπάνω. Ως εκ τούτου, ��⋅���⋅��=��+�.
Τώρα, εισάγουμε μια διαδικασία που ονομάζεται βήμα «τελικής εκθέσεως», όπου παίρνουμε το αποτέλεσμα των συναρτήσεών μας παραπάνω (��,��, κ.λπ.) και το ανεβάζουμε στην ισχύ �=(�12−1)/�, όπου �12−1 είναι η σειρά της πολλαπλασιαστικής ομάδας στο (��)12 (δηλ. για κάθε �∈(��)12,�(�12−1)=1). Παρατηρήστε ότι εάν εφαρμόσετε αυτήν την εκτόξευση σε οποιοδήποτε αποτέλεσμα που έχει ήδη αν αυξηθεί στη δύναμη του �, λαμβάνετε μια εκθετική δύναμη στη δύναμη του �12−1, οπότε το αποτέλεσμα μετατρέπεται σε 1. Επομένως, μετά την τελική εκτίμηση, το �� ακυρώνεται και παίρνουμε ����⋅����=( ��+�)�. Υπάρχει κάποια διγραμμικότητα για εσάς.
Τώρα, αν θέλετε να φτιάξετε μια συνάρτηση που είναι διγραμμική και στα δύο ορίσματα, πρέπει να πάτε σε πιο τρομακτικά μαθηματικά, όπου αντί να παίρνετε �� μιας τιμής απευθείας, παίρνετε �� από ένα διαιρών, και από εκεί προέρχεται το πλήρες "Tate pairing". Για να αποδείξετε περισσότερα αποτελέσματα, πρέπει να αντιμετωπίσετε έννοιες όπως «γραμμική ισοδυναμία» και «αμοιβαιότητα Weil», και η τρύπα του κουνελιού συνεχίζεται από εκεί. Μπορείτε να βρείτε περισσότερο υλικό ανάγνωσης για όλα αυτά εδώ και εδώ.
Για μια υλοποίηση μιας τροποποιημένης έκδοσης του ζευγαρώματος Tate, που ονομάζεται βέλτιστη ανάλυση Ate, Δες εδώ. Ο κώδικας υλοποιεί Ο αλγόριθμος του Miller, το οποίο απαιτείται για τον πραγματικά υπολογισμό ��.
Σημειώστε ότι το γεγονός ότι τα ζεύγη όπως αυτό είναι δυνατά είναι κάπως μια μικτή ευλογία: αφενός, σημαίνει ότι όλα τα πρωτόκολλα που μπορούμε να κάνουμε με τα ζεύγη γίνονται δυνατά, αλλά σημαίνει επίσης ότι πρέπει να είμαστε πιο προσεκτικοί σχετικά με το ποιες ελλειπτικές καμπύλες χρησιμοποιούμε.
Κάθε ελλειπτική καμπύλη έχει μια τιμή που ονομάζεται an βαθμός ενσωμάτωσης; ουσιαστικά, το μικρότερο � τέτοιο ώστε το ��-1 να είναι πολλαπλάσιο του � (όπου � είναι ο πρώτος που χρησιμοποιείται για το πεδίο και � είναι η σειρά καμπύλης). Στα παραπάνω πεδία, �=12, και στα πεδία που χρησιμοποιούνται για το παραδοσιακό ECC (δηλ. όπου δεν μας ενδιαφέρουν τα ζεύγη), ο βαθμός ενσωμάτωσης είναι συχνά εξαιρετικά μεγάλος, σε σημείο που οι ζεύξεις είναι υπολογιστικά αδύνατες να υπολογιστούν. Ωστόσο, αν δεν είμαστε προσεκτικοί, τότε μπορούμε να δημιουργήσουμε πεδία όπου �=4 ή ακόμα και 1.
Εάν �=1, τότε το πρόβλημα «διακριτού λογάριθμου» για ελλειπτικές καμπύλες (ουσιαστικά, η ανάκτηση � γνωρίζοντας μόνο το σημείο �=�⋅�, το πρόβλημα που πρέπει να λύσετε για να «σπάσετε» ένα ιδιωτικό κλειδί ελλειπτικής καμπύλης) μπορεί να μειωθεί σε ένα παρόμοιο μαθηματικό πρόβλημα πάνω από ��, όπου το πρόβλημα γίνεται πολύ πιο εύκολο (αυτό ονομάζεται Επίθεση MOV) Η χρήση καμπυλών με βαθμό ενσωμάτωσης 12 ή υψηλότερο διασφαλίζει ότι αυτή η μείωση είτε δεν είναι διαθέσιμη είτε ότι η επίλυση του προβλήματος του διακριτού αρχείου καταγραφής σε σχέση με τα αποτελέσματα σύζευξης είναι τουλάχιστον τόσο δύσκολη όσο η ανάκτηση ενός ιδιωτικού κλειδιού από ένα δημόσιο κλειδί «με τον κανονικό τρόπο» (δηλ. υπολογιστικά ανέφικτο). Μην ανησυχείς; Όλες οι τυπικές παράμετροι καμπύλης έχουν ελεγχθεί διεξοδικά για αυτό το ζήτημα.
Μείνετε συντονισμένοι για μια μαθηματική εξήγηση του τρόπου με τον οποίο λειτουργούν τα zk-SNARK, σύντομα.
Ιδιαίτερες ευχαριστίες στον Christian Reitwiessner, τον Ariel Gabizon (από το Zcash) και τον Alfred Menezes για την κριτική και τις διορθώσεις.
- SEO Powered Content & PR Distribution. Ενισχύστε σήμερα.
- PlatoData.Network Vertical Generative Ai. Ενδυναμώστε τον εαυτό σας. Πρόσβαση εδώ.
- PlatoAiStream. Web3 Intelligence. Ενισχύθηκε η γνώση. Πρόσβαση εδώ.
- PlatoESG. Ανθρακας, Cleantech, Ενέργεια, Περιβάλλον, Ηλιακός, Διαχείριση των αποβλήτων. Πρόσβαση εδώ.
- PlatoHealth. Ευφυΐα βιοτεχνολογίας και κλινικών δοκιμών. Πρόσβαση εδώ.
- BlockOffsets. Εκσυγχρονισμός της περιβαλλοντικής αντιστάθμισης ιδιοκτησίας. Πρόσβαση εδώ.
- πηγή: Νοημοσύνη δεδομένων Πλάτωνα.