Αποδείξεις Μηδενικής Γνώσης για Προβλήματα Τετραγωνικού Χρόνου

Abstract

Σε αυτή τη διπλωματική εργασία, κατασκευάζουμε μία νέα οικογένεια πολυωνύμων, την οποία ονομάζουμε FEIP τα οποία δεν μπορούν να υπολογιστούν σε πραγματικά υποτετραγωνικό χρόνο στη μέση περίπτωση εφόσον η Ισχυρή Υπόθεση Εκθετικού Χρόνου (SETH) ισχύει. Η δυσκολία μέσης περίπτωσης των πολυωνύμων μας βασίζεται στην ισχυρότερη υπόθεση πως το πρόβλημα ΑΚΡΙΒΕΣ ΕΣΩΤΕΡΙΚΟ ΓΙΝΟΜΕΝΟ (EIP) δεν μπορεί να λυθεί σε πραγματικά υποτετραγωνικό χρόνο στη χειρότερη περίπτωση. Το πρόβλημα EIP δέχεται σαν είσοδο δύο σύνολα διανυσμάτων U,V και ζητά την εύρεση δύο διανυσμάτων u,v (που ανήκουν στα σύνολα U,V αντίστοιχα) τέτοια ώστε <u,v>=t για κάποιο ακέραιο t>0. To EIP είναι τουλάχιστον τόσο δύσκολο όσο το Πρόβλημα των Ορθογώνιων Διανυσμάτων (OV), αλλά δεν γνωρίζουμε αν είναι ισοδύναμα στην περίπτωση που για τη διάσταση d των διανυσμάτων ισχύει d=ω(logn), που είναι μία συνηθισμένη υπόθεση. Αυτό καθιστά την FEIP μία πιο υποσχόμενη οικογένεια δύσκολων συναρτήσεων στη μέση περίπτωση από την FOV η οποία έχει οριστεί παλιότερα με παρόμοιο τρόπο. Παρουσιάζουμε μία λεπτομερή αναγωγή από το OV στο EIP, μία λεπτομερή αναγωγή από το EIP στη FEIP και μία λεπτομερή αναγωγή χειρότερης-προς-μέσης περίπτωσης από τη FEIP στον εαυτό της. Στη συνέχεια κατασκευάζουμε ένα MA πρωτόκολλο για την FEIP με έναν πραγματικά υποτετραγωνικό επαληθευτή και το χρησιμοποιούμε μαζί με την απόδειξη δυσκολίας υπολογισμού της FEIP για να κατασκευάσουμε μία λεπτομερή Απόδειξη Εργασίας. Για το υπόλοιπο της διπλωματικής αυτής εργασίας, μελετάμε την έννοια της μηδενικής γνώσης στο περιβάλλον της λεπτομερούς κρυπτογραφίας. Αρχικά ορίζουμε τις αποδείξεις μηδενικής γνώσης με τέτοιο τρόπο ώστε να να μπορούν να χρησιμοποιηθούν για προβλήματα επιλύσιμα σε πολυωνυμικό χρόνο με κοινώς αποδεκτά κάτω φράγματα. Στη συνέχεια κατασκευάζουμε αποδείξεις μηδενικής γνώσης για τα κυριότερα προβλήματα της λεπτομερούς πολυπλοκότητας, το OV και το 3SUM τα οποία είναι εύκολα επιλύσιμα σε τετραγωνικό χρόνο. Για τις αποδείξεις αυτές θεωρούμε ότι ο τετραγωνικός χρόνος είναι υπολογιστικά απρόσιτος, οπότε απαιτούμε τόσο ο αποδείκτης όσο και ο επαληθευτής να είναι αλγόριθμοι πραγματικά υποτετραγωνικού χρόνου. Τέλος δείχνουμε πώς τα πρωτόκολλά μας μπορούν να χρησιμοποιηθούν για να κατασκευάσουμε νέα πρωτόκολλα μηδενικής γνώσης για περισσότερα προβλήματα τετραγωνικού χρόνου μέσω λεπτομερών αναγωγών. Σαν παράδειγμα, χρησιμοποιούμε το πρόβλημα GeomBase από την υπολογιστική γεωμετρία.