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
-
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},
url = {https://eprint.iacr.org/2017/885}
}