Paper 2017/885

PermuteRam: Optimizing Oblivious Computation for Efficiency

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


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.

Available format(s)
Cryptographic protocols
Publication info
oblivious executionpermutation
Contact author(s)
shruti90 @ comp nus edu sg
2017-09-17: received
Short URL
Creative Commons Attribution


      author = {Shruti Tople and Hung Dang and Prateek Saxena and Ee-Chien Chang},
      title = {{PermuteRam}: Optimizing Oblivious Computation for Efficiency},
      howpublished = {Cryptology ePrint Archive, Paper 2017/885},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.