Quantum Fair Exchange

Abstract

Μελετάμε το κβαντικό ανάλογο του κρυπτογραφικού προβλήματος της δίκαιης ανταλλαγής.Σε μία δίκαιη ανταλλαγή θέλουμε να εξασφαλίσουμε ότι δύο πρόσωπα είτε θα ανταλλάξουν ταμυστικά τους, είτε κανείς από τους δύο δε θα μάθει το μυστικό του άλλου. Πιο συγκεκριμένατα δύο αυτά πρόσωπα, έστω η Αλίκη και ο Βασίλης (Α και Β), αλληλεπιδρούν μεταξύ τουςτρέχοντας ένα πρωτόκολλο δίκαιης ανταλλαγής. Απαιτούμε δύο βασικές ιδιότητες:1. Ορθότητα: Οταν και οι δύο παίκτες παίζουν τίμια (ακολουθούν το πρωτόκολλο) τότεστο τέλος μαθαίνουν και οι δύο το μυστικό.2. Πληρότητα: Οταν ένας από τους δύο παίκτες (έστω η Αλίκη) αποκλίνει αυθαίρετααπό το πρωτόκολλο (δηλαδή κλέβει με οποιοδήποτε τρόπο), τότε είτε θα πρέπει και οιδύο να μάθουν το μυστικό, είτε να μην το μάθει κανείς. Με άλλα λόγια, ακόμη κι ανκλέβει η Αλίκη, να μη βρεθεί σε μειονεκτική θέση ο Βασίλης.Προτείνουμε δύο διαφορετικές προσεγγίσεις για τη λύση του προβλήματος.Στην πρώτη προσέγγιση, δίνουμε έναν παραπλήσιο ορισμό, αυτόν της ταυτόχρονης ανταλ-λαγής. Σε ένα τέτοιο πρωτόκολλο, απαιτούμε το εξής: σε κάθε στιγμή του πρωτοκόλλου, ηπιθανότητα η Αλίκη να μαντέψει το μυστικό του Βασίλη είναι σχεδόν ίδια με την πιθανότη-τα ο Βασίλης να μαντέψει το μυστικό της Αλίκης. Σε αυτήν την περίπτωση μπορούμε ναεξασφαλίσουμε ασφάλεια από πληροφοριοθεωρητικής σκοπιάς: κατασκευάζουμε κβαντικόπρωτόκολλο τέτοιο ώστε ακόμα και ένας υπολογιστικά παντοδύναμος παίχτης να μην μπο-ρεί να το παραβιάσει. Τονίζουμε ότι με τις κλασσικές μεθόδους είναι αδύνατο να επιτύχουμεαπόλυτη ασφάλεια.Στη δεύτερη προσέγγιση χρησιμοποιούμε έναν αρκετά διαφορετικό ορισμό, αυτόν του CoinRipping. Εδώ, η Αλίκη θέλει να ανταλλάξει χρήματα με κάποιο προϊόν. Χρησιμοποιώνταςκάποια πρόσφατα αποτελέσματα όπως ασφαλή κβαντικά νομίσματα δημοσίου κλειδιού καιαποδείξεις μηδενικής γνώσης ασφαλείς ενάντια σε κβαντικούς αντιπάλους δημιουργούμε έναπρωτόκολλο τέτοιο ώστε:1. Αν η Αλίκη κλέψει τότε το καλύτερο που μπορεί να πετύχει είναι να πάρει το προϊόν καινα αποτρέψει τον Βασίλη από το να πληρωθεί, αλλά η ίδια θα το χάσει το χαρτονόμισμάτης.2. Αν ο Βασίλης κλέψει τότε το καλύτερο που μπορεί να πετύχει είναι να αναγκάσει τηνΑλίκη να χάσει το χαρτονόμισμά της, αλλά ο ίδιος δε θα το αποκτήσει.Με άλλα λόγια, δεν υπάρχει στρατηγική που να τους ευνοήσει αλλά υπάρχει στρατηγικήπου μπορεί να βλάψει τον αντίπαλο. Σε αυτήν την περίπτωση μπορούμε να εξασφαλίσουμευπολογιστική ασφάλεια: ένας πολυωνυμικά φραγμένος κβαντικός αντίπαλος έχει αμελητέαπιθανότητα να το παραβιάσει. Τονίζουμε ότι με τις κλασσικές μεθόδους δεν μπορούμε ναεπιτύχουμε κάτι τέτοιο καθώς δεν υπάρχει σχήμα που να εξασφαλίζει την δημόσια επα-λήθευση ενός νομίσματος (είναι απαραίτητη η χρήση κάποια έμπιστης αρχής που θα μπορείνα επαληθεύσει τη γνησιότητα των νομισμάτων).