Μία Επισκόπηση των Μηδενικής-Γνώσης Συνοπτικών Μη-Διαλογικών Επιχειρημάτων με προεπεξεργασία

Σε αυτή τη διπλωματική εργασία μελετάμε την έννοια των μηδενικής-γνώσεις συνοπτικών μη-διαλογικών επιχειρημάτων (zkSNARGs) με προεπεξεργασία. Δοθέντος ενός αριθμητικού κυκλώματος C, δημόσιας εισόδου x, ιδιωτικής εισόδου w και δημόσιας εξόδου y, ένα zkSNARG αποτελεί ένα πρωτόκολλο το οποίο επιτρέπει σε ένα υπολογιστικά φραγμένο συμμετέχοντα, ονόματι αποδεικνύοντας, να πείσει έναν άλλο, ονόματι επαληθευτής, ότι C(x, w) = y, δηλαδή ότι το κύκλωμα με εισόδους x, w αποτιμάται σε y, χωρίς ο επαληθευτής να αποκομμίσει οποιαδήποτε πληροφορία πέρα από την εγκυρότητα του υπολογισμού. Επιπλέον, ο αποδεικνύοντας δεν απαιτήται να αλληλεπιδράσει με οποιονδήποτε για τη δημιουργία της απόδειξης που ο επαληθευτής θα ελέγξει, ενώ η παραγώμενη απόδειξη είναι συνοπτική, δηλαδή μικρής χωρητικότητας και γρήγορα επαληθεύσιμη. Τέλος, τα πρωτόκολλα αυτά είναι καθολικά, υπό την έννοια ότι δουλεύουν για οποιοδήποτε κύκλωμα εώς ένα προκαθορισμένο όριο στο μέγεθος του, ενώ είναι επίσης επικαιροποιήσιμα, εννοώντας ότι τα SRS τους μπορούν να επικαιροποιηθούν μέσω ενός επαληθεύσιμου τρόπου από οποιονδήποτε χρήστη. Παρουσιάζουμε το τρέχον τοπίο της θεωρίας των καθολικών και επικαιροποιήσιμων zkSNARGs με προεπεξεργασία, το οποίο συνηγορεί για την κατασκευή τους με αρθρωτό τρόπο, διαχωρίζοντας το πληροφοριοθεωρητικό σκέλος της κατασκευής από το κρυπτογραφικό θεμελιακό στοιχείο που χρησιμοποιείται κατά τη σύνταξη. Το πληροφοριοθεωρητικό κομμάτι είναι μια πολυωνυμική ολογραφική απόδειξη  για την NP-πλήρη γλώσσα των Βαθμού 1 Συστημάτων Περιορισμών, ενώ το κρυπτογραφικό θεμελιακό στοιχείο είναι ένα σχήμα πολυωνυμικών δεσμέυσεων. Επιπρόσθετα, εξετάζουμε το υπολογιστικό κώλυμα των πρόσφατων κατασκευών, ονόματι ελέγξιμη δειγματοληψία υποχώρου, ξεχωριστά και δίνουμε κατασκευές αυτού που επιτυγχάνουν διαφορετικούς συμβιβασμούς απόδοσης. Τέλος, παρουσιάζουμε το Basilisk, το οποίο επιτυγχάνει το μικρότερο μέγεθος απόδειξης στη βιβλιογραφία.