Show simple item record

dc.contributor.advisorKatz, Jonathanen_US
dc.contributor.advisorShi, Elaineen_US
dc.contributor.authorNayak, Kartik Ravidasen_US
dc.date.accessioned2018-09-15T05:36:18Z
dc.date.available2018-09-15T05:36:18Z
dc.date.issued2018en_US
dc.identifierhttps://doi.org/10.13016/M26W96D17
dc.identifier.urihttp://hdl.handle.net/1903/21403
dc.description.abstractThe rapid increase in the amount of data stored by cloud servers has resulted in growing privacy concerns for users. First, although keeping data encrypted at all times is an attractive approach to privacy, encryption may preclude mining and learning useful patterns from data. Second, companies are unable to distribute proprietary programs to other parties without risking the loss of their private code when those programs are reverse engineered. A challenge underlying both those problems is that how data is accessed — even when that data is encrypted — can leak secret information. Oblivious RAM is a well studied cryptographic primitive that can be used to solve the underlying challenge of hiding data-access patterns. In this dissertation, we improve Oblivious RAMs and oblivious algorithms asymptotically. We then show how to apply our novel oblivious algorithms to build systems that enable privacy-preserving computation on encrypted data and program obfuscation. Specifically, the first part of this dissertation shows two efficient Oblivious RAM algorithms: 1) The first algorithm achieves sub-logarithmic bandwidth blowup while only incurring an inexpensive XOR computation for performing Private Information Retrieval operations, and 2) The second algorithm is the first perfectly-secure Oblivious Parallel RAM with $O(\log^3 N )$ bandwidth blowup, $O((\log m + \log \log N)\log N)$ depth blowup, and $O(1)$ space blowup when the PRAM has $m$ CPUs and stores $N$ blocks of data. The second part of this dissertation describes two systems — HOP and GraphSC — that address the problem of computing on private data and the distribution of proprietary programs. HOP is a system that achieves simulation-secure obfuscation of RAM programs assuming secure hardware. It is the first prototype implementation of a provably secure virtual black-box (VBB) obfuscation scheme in any model under any assumptions. GraphSC is a system that allows cloud servers to run a class of data-mining and machine-learning algorithms over users’ data without learning anything about that data. GraphSC brings efficient, parallel secure computation to programmers by allowing them to express computation tasks using the GraphLab abstraction. It is backed by the first non-trivial parallel oblivious algorithms that outperform generic Oblivious RAMs.en_US
dc.language.isoenen_US
dc.titleEfficient Data-Oblivious Computationen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledOblivious Algorithmsen_US
dc.subject.pquncontrolledOblivious Computationen_US
dc.subject.pquncontrolledOblivious RAMen_US
dc.subject.pquncontrolledSecure Multi-Party Computationen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record