Cryptology ePrint Archive: Report 2017/885

PermuteRam: Optimizing Oblivious Computation for Efficiency

Shruti Tople and Hung Dang and Prateek Saxena and Ee-Chien Chang

Abstract: Privacy preserving computation is gaining importance. Along with secure computation guarantees, it is essential to hide information leakage through access patterns. Input-oblivious execution is a security property that is crucial to guarantee complete privacy preserving computation. In this work, we present an algorithm-specific approach to achieve input-oblivious execution. We call this class of algorithms PermuteRam. PermuteRam algorithms satisfy a specific patterns in their execution profile called Perpató patterns that can be realized using permutation as a primitive. Next, we claim that algorithms having Perpat pattern execute in an input-oblivious manner. Further, we show that PermuteRam is expressive and includes various categories of algorithms like sorting, clustering, operating on tree data structures and so on. PermuteRam algorithms incur only an additive overhead of O(N) and a private storage of O(sqrt(N)). Hence, PermuteRam algorithms demonstrate optimal performance for linear or super-linear complexities.

Category / Keywords: cryptographic protocols / oblivious execution, permutation

Date: received 13 Sep 2017

Contact author: shruti90 at comp nus edu sg

Available format(s): PDF | BibTeX Citation

Version: 20170917:161845 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]