Paper 2017/885

PermuteRam: Optimizing Oblivious Computation for Efficiency

Shruti Tople, Hung Dang, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
oblivious executionpermutation
Contact author(s)
shruti90 @ comp nus edu sg
History
2017-09-17: received
Short URL
https://ia.cr/2017/885
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/885,
      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{https://eprint.iacr.org/2017/885}},
      url = {https://eprint.iacr.org/2017/885}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.