Βελτίωση Πολυπλοκότητας Επικοινωνίας Κβαντικών Κρυπτογραφικών Πρωτοκόλλων

Abstract

Στην παρούσα διπλωματική εργασία, μελετάμε την πολυπλοκότητα επικοινωνίας των κβαντικών σχημάτων πλήρως ομομορφικής κρυπτογράφησης (QFHE) και των συστημάτων μηδενικής γνώσης (ZK) για την κλάση QMA (το κβαντικό ανάλογο της NP). Θεωρώντας την κβαντική δυσκολία του learning with errors προβλήματος (LWE) για τα πρώτα, και την οιονεί-πολυωνυμική (quasi-polynomial) κβαντική δυσκολία του LWE για τα δεύτερα, έχουμε τα παρακάτω αποτελέσματα: - Κβαντικό Σχήμα Πλήρως Ομομορφικής Κρυπτογράφησης Ρυθμού-1, που επιτρέπει στην Alice να στείλει στον Bob το κβαντικό της μήνυμα \ket{\psi} κρυπτογραφημένο, ώστε ο Bob, έχοντας ένα κύκλωμα $C$, να μπορεί να υπολογίσει το $C(\ket{\psi})$ χωρίς να χρειάζεται να αποκτυπτογραφήσει το μήνυμα. Επιτυγχάνουμε πολυπλοκότητα (|\ket{\psi}| + |C(\ket{\psi})|) \cdot (1 + o(1)), που είναι σχεδόν βέλτιστη. - Πρωτόκολλό στατιστικής Μηδενικής Γνώσης 4 γύρων για την κλάση QMA στο απλό μοντέλο. Αυτό είναι το πρώτο πρωτόκολλο που επιτυγχάνει \emph{στατιστική} μηδενική γνώση σε σταθερό αριθμό γύρων για την κλάση QMA. - Πρωτόκολλο υπολογιστικής (αντ. στατιστικής) Μηδενικής Γνώσης 2 γύρων στο χρονικό μοντέλο, θεωρώντας επιπλέον την ύπαρξη μετακβαντικών μη-παραλληλοποιήσιμων συναρτήσεων (αντ. time-lock puzzles).

Όλα τα παραπάνω πρωτόκολλα επιτυγχάνουν την βέλτιστη πολυπλοκότητα επικοινωνίας των αντίστοιχων NP πρωτοκόλλων με ασφάλεια έναντι σε κλασσικούς αντιπάλους.