On the Trade-Offs in Oblivious Execution Techniques

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.