@inproceedings{tople2017on,
author = {Tople, Shruti and Saxena, Prateek},
title = {On the Trade-Offs in Oblivious Execution Techniques},
booktitle = {Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA)},
year = {2017},
month = {July},
abstract = {To enable privacy-preserving computation on encrypted data,
a class of techniques for input-oblivious execution have surfaced. The
property of input-oblivious execution guarantees that an adversary observing
the interaction of a program with the underlying system learns
nothing about the sensitive input. To highlight the importance of oblivious
execution, we demonstrate a concrete practical attack — called a
logic-reuse attack — that leaks every byte of encrypted input if oblivious
techniques are not used. Next, we study the efficacy of oblivious
execution techniques and understand their limitations from a practical
perspective. We manually transform 30 common Linux utilities by applying
known oblivious execution techniques. As a positive result, we show
that 6 utilities perform input-oblivious execution without modification,
11 utilities can be transformed with O(1) performance overhead and 11
other show O(N) overhead. As a negative result, we show that theoretical
limitations of oblivious execution techniques do manifest in 2 real
applications in our case studies incurring a performance cost of O(2^N)
over non-oblivious execution.},
url = {http://approjects.co.za/?big=en-us/research/publication/on-the-trade-offs-in-oblivious-execution-techniques-2/},
}