Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18554
Title: Αποδείξεις Μηδενικής Γνώσης για Προβλήματα Τετραγωνικού Χρόνου
Authors: Μαραβίτσας, Παναγιώτης
Παγουρτζής Αριστείδης
Keywords: Cryptography
Fine-Grained Complexity
Average-Case Hardness
Zero Knowledge Arguments
Issue Date: 22-Nov-2022
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 από την υπολογιστική γεωμετρία.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18554
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
maravitsas_thesis.pdf499.57 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.