Cryptographic Protocols For Secure Second-Price Auctions

Τα τελευταία χρόνια οι δημοπρασίες έχουν γίνει όλο και περισσότερο σημαντικές στον τομέα των multiagent συστημάτων ως χρήσιμοι μηχανισμοί για τη διανομή των πόρων, την ανάθεση καθηκόντων και το ηλεκτρονικό εμπόριο. Σε πολλές περιπτώσεις η δημοπρασία Vickrey (ασφαλής προσφορά δεύτερης τιμής) χρησιμοποιείται ως ένα πρωτόκολλο το οποίο καθορίζει πως οι διάφοροι ανεξάρτητοι αντιπρόσωποι (agents) πρέπει να αλληλεπιδράσουν με σκοπό να φτάσουν σε συμφωνία. Οι κύριοι λόγοι επιλογής του πλειστηριασμού Vickrey είναι η ύπαρξη μιας κυρίαρχης στρατηγικής ισορροπίας, το μικρό εύρος ζώνης και η κατανάλωση χρόνου εξαιτίας του μόλις ενός γύρου προσφοράς και της (θεωρητικής) μυστικότητας των προσφορών. Η παρούσα εργασία αναφέρει λεπτομερώς ιδιότητες οι οποίες είναι απαραίτητες για να διαβεβαιώσουν την ακριβή και μυστική εκτέλεση των πλειστηριασμών Vickrey και προβάλει μια κατηγοριοποίηση διαφορετικών μορφών συνομωσιών. Προσεγγίζουμε τις δύο σημαντικότερες δραστηριότητες του πλειστηριασμού Vickrey ως εξής: στην τρωτότητα ενός ψεύτη πλειστηριαστή και την απροθυμία αυτών που υποβάλλουν τις προσφορές (συμμετεχόντων στη δημοπρασία) να αποκαλύψουν την προσωπική τους εκτίμηση. Τότε, προτείνουμε μία καινούρια τεχνική η οποία επιτρέπει την εκπλήρωση με ασφάλεια δημοπρασιών δεύτερης τιμής (second-price). Κάτι τέτοιο επιτυγχάνεται με την αναγγελία κρυπτογραφημένων δυαδικών λιστών προσφορών σε έναν πίνακα. Τεχνικές αναζήτησης όπως top-down, bottom-up και δυαδική χρησιμοποιούνται για να βρεθεί βήμα-βήμα με αλληλεπίδραση η δεύτερη μεγαλύτερη προσφορά, χωρίς να αποκαλυφθούν περιττές πληροφορίες.

Η περιοχή των multiagent συστημάτων, η οποία αφορά συστήματα τα οποία αποτελούνται από τεχνικές οντότητες οι οποίες ονομάζονται agents και αλληλεπιδρούν και κατά μία έννοια μπορούμε να πούμε ότι είναι έξυπνες και αυτόνομες, τα τελευταία χρόνια έχει εγείρει την προσοχή όλο και περισσότερων ερευνητών. Το ηλεκτρονικό εμπόριο, η αυτόματη κατανομή των πόρων και η ανάθεση δραστηριοτήτων είναι θέματα με μεγάλο ενδιαφέρον στην κοινωνία των agent. Καθώς οι δημοπρασίες είναι πολύ ευέλικτα και αποτελεσματικά εργαλεία τα οποία μπορούν να χρησιμοποιηθούν για να δηλώσουν αυτά τα προβλήματα, αποτελεί κοινή πρακτική να χρησιμοποιούμε πολύ γνωστά αποτελέσματα και γνώσεις της θεωρίας πλειστηριασμών και πλήρως κατανοητά πρωτόκολλα δημοπρασίας όπως η αγγλική δημοπρασία, η εκπτωτική δημοπρασία και η δημοπρασία Vickrey. Μεταξύ των διαφόρων πρωτοκόλλων, η δημοπρασία Vickrey (αλλιώς γνωστή ως second-price δημοπρασία ασφαλούς προσφοράς) έχει αποσπάσει ιδιαίτερη προσοχή εντός της multiagent κοινωνίας εξαιτίας τριών κυρίως χαρακτηριστικών:

• Απαιτεί μικρό εύρος ζώνης και κατανάλωση χρόνου
• Κατέχει μία κυρίαρχη στρατηγική στην προσφορά της αληθινής αξιολόγησης κάποιου
• Αποτελεί δημοπρασία ασφαλούς προσφοράς, οι προσφορές (οι οποίες εκφράζουν ιδιωτικές τιμές) παραμένουν μυστικές

Αυτά τα χαρακτηριστικά κάνουν το Vickrey πρωτόκολλο δημοπρασίας να έχει ιδιαίτερη απήχηση από τη σκοπιά του αυτοματισμού. Η δημοπρασία Vickrey, στην αρχική της μορφή και όπως χρησιμοποιείται για την πώληση αγαθών ή την κατανομή των πόρων, δουλεύει ως εξής: κάθε ένας κάνει μια ασφαλή προσφορά εκφράζοντας το ποσό το οποίο είναι πρόθυμος να πληρώσει και αυτός που υποβάλλει τη μεγαλύτερη προσφορά κερδίζει τη δημοπρασία. Το ποσό το οποίο θα καταβληθεί από το νικητή είναι ίσο με τη δεύτερη μεγαλύτερη προσφορά. Σε σενάρια ανάθεσης δραστηριοτήτων, η Vickrey δημοπρασία δουλεύει ακριβώς αντίθετα (και γι’ αυτό το λόγο συχνά αναφέρεται ως ανάστροφη δημοπρασία Vickrey): καθένας που είναι πρόθυμος να φέρει σε πέρας μια δραστηριότητα υποβάλλει μια προσφορά εκφράζοντας το ποσό το οποίο επιθυμεί αυτός να πληρωθεί για την ολοκλήρωση της δραστηριότητας. Ο νικητής λαμβάνει ένα ποσό ίσο με τη δεύτερη χαμηλότερη προσφορά (και η πληρωμή του είναι η δεύτερη χαμηλότερη προσφορά μείον το βασικό κόστος για την ολοκλήρωση της δραστηριότητας). Αν υπάρχουν περισσότερες από μία νικήτριες προσφορές, ο τελικός νικητής ανακηρύσσεται τυχαία (ένας από αυτούς με τη χαμηλότερη προσφορά). Καθώς η τυπική και η ανάστροφη δημοπρασία είναι πλήρως αναλογικές, όλες οι παρουσιαζόμενες θεωρήσεις και τεχνικές αφορούν και τους δύο τύπους της Vickrey δημοπρασίας.

Παρ’ όλες τις εντυπωσιακές θεωρητικές της ιδιότητες, η Vickrey δημοπρασία σπανίως χρησιμοποιείται στην πράξη. Αυτό το πρόβλημα έχει παρουσιαστεί πολλές φορές και είναι αδιαφιλονίκητο γεγονός ότι η σπανιότητα χρήσης της Vickrey δημοπρασίας οφείλεται σε δύο βασικούς λόγους. Πρώτος λόγος είναι ότι η αξιοπρεπής εκτέλεση της Vickrey δημοπρασίας εξαρτάται από την τιμιότητα του πλειστηριαστή. Αυτός που υποβάλει τη μεγαλύτερη προσφορά πρέπει να εμπιστεύεται τον πλειστηριαστή όταν αυτός ανακοινώνει τη δεύτερη μεγαλύτερη προσφορά. Υπάρχει μεγάλος κίνδυνος ενός ανειλικρινούς πλειστηριαστή ο οποίος να μεγαλώνει τη δεύτερη μεγαλύτερη προσφορά με σκοπό να κερδίσει περισσότερα χρήματα (για τον εαυτό του ή για τον πελάτη του, τον πωλητή). Δεύτερος λόγος είναι ότι αυτοί που υποβάλλουν μια προσφορά είναι συνήθως απρόθυμοι να αποκαλύψουν τις αληθινές προσωπικές τιμές όπως απαιτείται από την κυρίαρχη στρατηγική. Σε πολλά σενάρια οι δημοπρασίες δεν είναι απομονωμένα γεγονότα, αλλά τμήματα μιας σειράς διαπραγματεύσεων. Η τιμολόγηση αγαθών ή δραστηριοτήτων είναι ευαίσθητες πληροφορίες τις οποίες οι agents σκοπεύουν να κρατήσουν ιδιωτικές. Ακόμα και αν η μεταφορά ασφαλών προσφορών είναι πλήρως προστατευμένη με τεχνικές κρυπτογραφίας, παραμένει άγνωστο πως ο πλειστηριαστής μεταχειρίζεται αυτές τις εμπιστευτικές πληροφορίες. Η μυστικότητα ασφαλών προσφορών είναι επίσης σημαντικό θέμα στους κανονικούς πλειστηριασμούς πρώτης τιμής (first-price), αλλά πολλές φορές είναι περισσότερο σημαντικό στους πλειστηριασμούς δεύτερης τιμής (second-price) αφού οι προσφορές αναπαριστούν μη εναλλακτικές ιδιωτικές τιμές. Η συγκεκριμένη εργασία παρουσιάζει επίσης την κρίσιμη αδυναμία της δημοπρασίας Vickrey. Παρουσιάζουμε μια τεχνική η οποία βεβαιώνει την αδυναμία του πλειστηριαστή να διαχειριστεί την κατάληξη της δημοπρασίας και επεξηγούμε μεθόδους οι οποίες μειώνουν στο ελάχιστο τη γνώση του πλειστηριαστή σχετικά με τις προσφορές με σκοπό να αδυνατίσουν τη θέση του για συνωμοτικές συμφωνίες.

Η παρούσα εργασία δομείται ως εξής: Το τμήμα 2 συνοψίζει τις υπάρχουσες προσπάθειες στον τομέα των ασφαλών Vickrey δημοπρασιών και εξηγεί γιατί περιορίζουμε τους εαυτούς μας σε έναν μοναδικό πλειστηριαστή. Το τμήμα 3 ερμηνεύει ζωτικά χαρακτηριστικά τα οποία βεβαιώνουν μια ομαλή διαδικασία πλειστηριασμού και καθορίζει σημαντικούς τύπους συνωμοσιών. Η θεμελίωση του νέου πρωτοκόλλου ασφαλούς πλειστηριασμού παρουσιάζεται στο τμήμα 4 και το τμήμα 5 παρουσιάζει και αναλύει τρεις μεθόδους οι οποίες κρύβουν πληροφορίες τις οποίες δεν χρειάζεται ο πλειστηριαστής. Τέλος, στο τμήμα 6 παρουσιάζονται τα πλεονεκτήματα και τα μειονεκτήματα της προτεινόμενης μεθόδου.

Download project

Read more »

Data Structures, Algorithms and Applications - Search Engine

Μηχανή Αναζήτησης

• Μηχανή αναζήτησης λέξεων – φράσεων σε κείμενα: Επιστρέφει το αρχείο στο οποίο υπάρχει η λέξη
• Εισαγωγή αρχείων κειμένου στο πρόγραμμα και τη μηχανή αναζήτησης
• Αποθήκευση εσωτερικών δομών σε αρχείο στο δίσκο για γρήγορη επανεκκίνηση του προγράμματος
• Ανάκτηση του αρχείου που δημιουργήθηκε στο προηγούμενο βήμα
• Χρήση τελεστών: παρενθέσεις, AND, OR, NOT
• Απεικόνιση της λίστας των λέξεων ταξινομημένης
• Εισαγωγή – Αφαίρεση αρχείου κειμένου από την αναζήτηση
• Απεικόνιση στοιχείων σχετικών με την δομή δεδομένων π.χ. στατιστικών, μέγεθος δομής σε bytes κλπ, καθώς απεικόνιση στοιχείων επιδόσεων του αλγόριθμου

Περιγραφή

Στόχος του project είναι η κατασκευή μιας απλής μηχανής αναζήτησης (search engine). Η μηχανή αυτή θα λαμβάνει ως είσοδο μία λίστα από αρχεία κειμένου (ASCII Text files), θα βρίσκει τις λέξεις που περιέχουν και χρησιμοποιώντας δομές στη μνήμη του υπολογιστή, θα διατηρεί όλη την απαραίτητη πληροφορία. Στη συνέχεια, ο χρήστης θα εισάγει στην εφαρμογή μέσα από το command line της εφαρμογής μία λέξη (π.χ. δάσος) και η εφαρμογή θα τον πληροφορεί σε ποια αρχεία βρίσκεται η λέξη αυτή. Επίσης για τη διευκόλυνση της αναζήτησης θα πρέπει να υπάρχει η δυνατότητα εισαγωγής από το χρήστη λογικών εκφράσεων (τουλάχιστον με τον τελεστή ΚΑΙ), δηλ λέξη1 ΚΑΙ λέξη2 που θα επιστρέφει τα αρχεία που περιέχουν και τις δύο λέξεις. Περισσότεροι τελεστές (π.χ. OR, NOT) καθώς και η υποστήριξη παρενθέσεων είναι θεμιτοί και επιθυμητοί!

Υλοποίηση

Το project του μαθήματος έγινε μετά από μελέτη των μεθόδων εύρεσης και αποθήκευσης δεδομένων οι οποίες παρουσιάστηκαν στις διαλέξεις του μαθήματος, κυρίως ως προς την ταχύτητα της κάθε μιας. Έτσι χρησιμοποιήθηκε η μέθοδος της συνάρτησης κατακερματισμού (hash function) για την τοποθέτηση των καταχωρήσεων σε πίνακα. Σύμφωνα με αυτή, τα δεδομένα τοποθετούνται σε συγκεκριμένες θέσεις ενός μονοδιάστατου πίνακα μέσω μιας έτοιμης συνάρτησης από τη βιβλιογραφία. Η μέθοδος αυτή προτιμήθηκε από το δέντρο (Binary Search Tree) γιατί έχουμε ταχύτερη αναζήτηση. Συγκεκριμένα, με τη συνάρτηση κατακερματισμού πετυχαίνουμε εύρεση καταχώρησης σε χρόνο Ο(1) ενώ με το B.S.T. σε χρόνο Ο(h), όπου h είναι το ύψος του δέντρου. Η αντιμετώπιση των συγκρούσεων έγινε με τη χρήση απλά συνδεδεμένης λίστας. Δηλαδή κάθε φορά που αντιστοιχούσαν περισσότερες της μίας λέξης σε μία θέση του πίνακα, τότε δημιουργούνταν ένας νέος κόμβος για την τοποθέτηση της συγκρουόμενης λέξης. Για να έχουμε το μικρότερο αριθμό συγκρούσεων, προσπαθήσαμε να έχουμε διπλάσιες διαθέσιμες θέσεις στον πίνακα από τον αριθμό των στοιχείων τα οποία έχουμε προς αποθήκευση. Επιπλέον, το πρόγραμμα δεν κάνει πολλαπλές καταχωρήσεις, απλώς μετράει πόσες φορές εμφανίζεται η κάθε καταχώρηση. Μετράει ακόμα το χρόνο φόρτωσης των καταχωρήσεων από αρχεία, το χρόνο αναζήτησης της κάθε λέξης και το αρχείο στο οποίο υπάρχει η λέξη που αναζητάμε. Η συνάρτηση κατακερματισμού βρέθηκε στη βιβλιογραφία και συγκεκριμένα στο βιβλίο “Compilers: Principles,Techniques and Tools” από Aho, Sethi και Ullman. Σε γενικές γραμμές, δίνονται τέσσερις επιλογές στο χρήστη του προγράμματος: εισαγωγή καταχωρήσεων από αρχείο, διαγραφή των καταχωρήσεων ενός αρχείου, προβολή των καταχωρήσεων και αναζήτηση μιας καταχώρησης. Το πρόγραμμα παίρνει κάθε λέξη από το εκάστοτε αρχείο και την τοποθετεί σε μία θέση του πίνακα ανάλογα με το hash value. Βέβαια, αφαιρούνται οι ειδικοί χαρακτήρες που βρίσκονται σε κάθε αρχείο κειμένου.

Ως γλώσσα υλοποίησης χρησιμοποιείται η C σε λειτουργικό σύστημα winxp.

Κατέβασμα αρχείων και εκτελέσιμου

Read more »