Implementation of oblivious data structures

Abstract

Παρουσίαση των σημαντικότερων ιστορικών εξελίξεων στην Κρυπτογραφία που οδήγησαν στην ιδέα της Επιλήσμονος RAM (Oblivious RAM ή ORAM) των Goldreich και Ostrovsky το 1993. Σύντομη παρουσίαση της πρώτης τους αλγοριθμικής δομής, Hierarchical ORAM, ακολουθούμενη από την πολύ διαφορετική προσέγγιση Binary-tree based ORAM (Shi et al. 2011) και της βελτίωσής της για ασφαλή πολυμερή υπολογισμό (MPC), Circuit ORAM. Επίσης, γίνεται σε βάθος εξέταση του αλγόριθμου της Path-ORAM (Stefanov et al. 2012) και παρουσίαση της δικής μας υλοποίησης σε Python. Στη συνέχεια δίνεται ο ορισμός μιας Επιλήσμονος Δομής Δεδομένων (Oblivious Data Structure ή ODS) και η περιγραφή της τεχνικής pointer-based για τη διαχείριση τέτοιων δομών όπως προτάθηκε από την Elaine Shi με το ODS framework. Εξετάζεται την αρχιτεκτονική του framework και παρουσιάζεται η δική μας προγραμματιστική υλοποίηση σε γλώσσα Python. Κλείνοντας παρουσιάζονται τρεις βασικοί ODS αλγόριθμοι και οι υλοποιήσεις τους. Ειδικότερα οι: Oblivious Stack, Oblivious Queue και Oblivious Heap (priority queue).

We present the key historical advances in Cryptography that led to the concept of Oblivious RAM (ORAM) by Goldreich and Ostrovsky in 1993. We briefly present their first algorithmic construct, Hierarchical ORAM, followed by a very different approach, the Binary-tree based ORAM by Shi et al. (2011) and its improvement for secure Multi-Party Computation (MPC), Circuit ORAM. We thoroughly examine Path-ORAM algorithm by Stefanov et al. (2012) and we present our Python implementation of it. We move on to the definition of an Oblivious Data Structure (ODS) and the description of the pointer-based technique to handle Oblivious Data Structures proposed by Shi et al. along with their ODS framework. We examine the architecture of the framework and we present our python implementation. We finally present three basic ODS algorithms and their Python counterparts. Namely, Oblivious Stack, Oblivious Queue and Oblivious Heap (priority queue).