Recent compilers allow a general-purpose program (written in a conventional programming language) that handles private data to be translated into secure distributed implementation of the corresponding functionality. The resulting program is then guaranteed to provably protect private data using secure multi-party computation techniques. The goals of such compilers are generality, usability, and efficiency, but the complete set of features of a modern programming language has not been supported to date by the existing compilers. In particular, recent compilers PICCO and the two-party ANSI C compiler strive to translate any C program into its secure multi-party implementation, but currently lack support for pointers and dynamic memory allocation, which are important components of many C programs. In this work, we mitigate the limitation and add support for pointers to private data and consequently dynamic memory allocation to the PICCO compiler, enabling it to handle a more diverse set of programs over private data. Because doing so opens up a new design space, we investigate the use of pointers to private data (with known as well as private locations stored in them) in programs and report our findings. Besides dynamic memory allocation, we examine other important topics associated with common pointer use such as reference by pointer address, casting, and building various data structures in the context of secure multi-party computation. This results in enabling the compiler to automatically translate a user program that uses pointers to private data into its distributed implementation that provably protects private data throughout the computation. We empirically evaluate the constructions and report on performance of representative programs.
An algorithm is called data-oblivious if its control flow and memory access pattern do not depend on its input data. Data-oblivious algorithms play a significant role in secure cloud computing, since programs that are run on secret data—as in fully homomorphic encryption or secure multiparty computation—must be data-oblivious. In this paper, we formalize three definitions of data-obliviousness that have appeared implicitly in the literature, explore their implications, and show separations. We observe that data-oblivious algorithms often compose well when viewed as data structures. Using this approach, we construct data-oblivious stacks, queues, and priority queues that are considerably simpler than existing constructions, as well as improving constant factors. We also establish a new upper bound for oblivious data compaction, and use this result to show that an “oine” variant of the Oblivious RAM problem can be solved with O(logn log logn) expected amortized time per operation— as compared with O(log 2 n log logn), the best known upper bound for the standard online formulation. 1998 ACM Subject Classification D.4.6 Security and Protection, E.1 Data Structures, F.1.1 Models of Computation, F.1.2 Modes of Computation  This work considers data structures based on multi-party computation (MPC) primitives: structuring secret (e.g. secret shared and potentially unknown) data such that it can both be queried and updated efficiently. Implementing an oblivious RAM (ORAM) using MPC allows any existing data structure to be realized using MPC primitives, however, by focusing on a specific example -- a priority queue -- it is shown that it is possible to achieve much better results than the generic solutions can provide. Moreover, the techniques differ significantly from existing ORAM constructions. Indeed it has recently been shown that any information theoretically secure ORAM with n memory locations requires at least log n random bits per read write to hide the access pattern. In contrast, the present construction achieves security with a completely deterministic access pattern. We present oblivious implementations of several data structures for secure multiparty computation (MPC) such as arrays, dictionaries, and priority queues. The resulting oblivious data structures have only polylogarithmic overhead compared with their classical counterparts. To achieve this, we give secure multiparty protocols for the ORAM of (Asiacrypt ‘11) and the Path ORAM scheme of (CCS ‘13), and we compare the resulting implementations. We subsequently use our oblivious priority queue for secure computation of Dijkstra’s shortest path algorithm on general graphs, where the graph structure is secret. To the best of our knowledge, this is the first implementation of a non-trivial graph algorithm in multiparty computation with polylogarithmic overhead.