Garbled circuits for multi-input boolean functions

Abstract

Multiparty computation is an area of cryptography which provides methods that two or more parties may use in order to jointly compute a function while keeping their inputs private. Garbled circuits, attributed to Andrew C. Yao, is a cryptographic technique used in secure multiparty computation. Any function can be represented into a garbled boolean circuit and, with the help of Oblivious Transfer, a protocol can be built which allows parties to securely evaluate a function without exposing their inputs.

The naive implementation of Yao's Garbled Circuit Protocol is impractical for complex functions. Researchers come up with methods that aim to reduce the communication overhead and computational complexity of the protocol. Nowadays, cryptographic operations are supported by hardware and as a result the main bottleneck in garbling is considered to be communication.

This work introduces Yao's protocol and reviews several existent techniques which attempt to reduce the aforementioned costs, with a main focus on methods that aim to lessen the total number of ciphertexts needed to garble a function. Furthermore, it extends the recent and well established half gates method. Specifically, this work demonstrates that if half gates are combined and garbling is done on polynomials, then a 25% to 50% reduction in the amount of ciphertexts needed to garble portions of the circuit can be expected.

Η από κοινού υπολογιστική είναι ένας τομέας της κρυπτογραφίας ο οποίος παρέχει μεθόδους τις οποίες δύο ή περισσότερα μέρη μπορούν να χρησιμοποιήσουν ώστε να υπολογίσουν από κοινού μια συνάρτηση με ταυτόχρονη εξασφάλιση της ιδιωτικότητας των εισόδων τους. Τα κωδικοποιημένα κυκλώματα αποτελούν μια κρυπτογραφική τεχνική η οποία προτάθηκε από τον Άντρεου Γιάο και χρησιμοποιείται στην ασφαλή από κοινού υπολογιστική. Κάθε συνάρτηση μπορεί να αναπαρασταθεί από ένα κωδικοποιημένο κύκλωμα και, με τη χρήση της τεχνικής της εν αγνοία μεταφοράς, υπάρχει η δυνατότητα να κατασκευαστεί ένα πρωτόκολλο επικοινωνίας το οποίο επιτρέπει σε πολλά μέρη να υπολογίσουν με ασφαλή τρόπο μια συνάρτηση χωρίς να αποκαλύψουν τις εισόδους τους. Ωστόσο η απλοϊκή υλοποίηση του πρωτοκόλλου των κωδικοποιημένων κυκλωμάτων του Γιάο είναι πρακτικά μη εφαρμόσιμη για περίπλοκες συναρτήσεις. Αυτό έχει οδηγήσει τους ερευνητές στην πρόταση μεθόδων οι οποίες στοχεύουν στη μείωση του επικοινωνιακού κόστους και της υπολογιστικής πολυπλοκότητας του πρωτοκόλλου. Στις μέρες μας οι κρυπτογραφικοί υπολογισμοί υποστηρίζονται όλο και περισσότερο από το υλικό των υπολογιστών κι αυτό έχει ως συνέπεια το επικοινωνιακό κόστος να θεωρείται το κυριότερο εμπόδιο στην υλοποίηση του πρωτοκόλλου. Στην παρούσα εργασία παρουσιάζεται το πρωτόκολλο του Γιάο και γίνεται ανασκόπηση των τεχνικών οι οποίες αποσκοπούν στη μείωση του επικοινωνιακού κόστους, με μια ιδιαίτερη έμφαση σε εκείνες τις μεθόδους που στοχεύουν στη μείωση των συνολικών κρυπτοκειμένων τα οποία χρειάζονται για την κωδικοποίηση μιας συνάρτησης. Επιπρόσθετα, στην παρούσα εργασία επεκτείνεται η καινοτόμα και καλά καθιερωμένη μέθοδος των ημι-πυλών. Συγκεκριμένα, στην παρούσα εργασία αποδεικνύεται ότι ο συνδυασμός των ημι-πυλών με σκοπό την κωδικοποίηση πολυωνύμων μπορεί να οδηγήσει σε μείωση κατά 25% ως 50% των κρυπτοκειμένων που απαιτούνται για την κωδικοποίηση τμημάτων των λογικών κυκλωμάτων που περιγράφουν μια συνάρτηση.