Circuit OPRAM: Unifying Statistically and Computationally Secure ORAMs and OPRAMs
An Oblivious Parallel RAM (OPRAM) provides a general method to simulate any Parallel RAM (PRAM) program, such that the resulting memory access patterns leak nothing about secret inputs. OPRAM was originally proposed by Boyle et al. as the natural parallel
- PDF / 439,528 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 190 Views
The University of Hong Kong, Pokfulam, Hong Kong [email protected] 2 Cornell University, Ithaca, USA
Abstract. An Oblivious Parallel RAM (OPRAM) provides a general method to simulate any Parallel RAM (PRAM) program, such that the resulting memory access patterns leak nothing about secret inputs. OPRAM was originally proposed by Boyle et al. as the natural parallel counterpart of Oblivious RAM (ORAM), which was shown to have broad applications, e.g., in cloud outsourcing, secure processor design, and secure multi-party computation. Since parallelism is common in modern computing architectures such as multi-core processors or cluster computing, OPRAM is naturally a powerful and desirable building block as much as its sequential counterpart ORAM is. Although earlier works have shown how to construct OPRAM schemes with polylogarithmic simulation overhead, in comparison with best known sequential ORAM constructions, all existing OPRAM schemes are (poly-)logarithmic factors more expensive. In this paper, we present a new framework in which we construct both statistically secure and computationally secure OPRAM schemes whose asymptotical performance matches the best known ORAM schemes in each setting. Since an OPRAM scheme with simulation overhead χ directly implies an ORAM scheme with simulation overhead χ, our result can be regarded as providing a unifying framework in which we can subsume all known results on statistically and computationally secure ORAMs and OPRAMs alike. Particularly for the case of OPRAMs, we also improve the state-of-theart scheme by superlogarithmic factors. To achieve the aforementioned results requires us to combine a variety of techniques involving (1) efficient parallel oblivious algorithm design; and (2) designing tight randomized algorithms and proving measure concentration bounds about the rather involved stochastic process induced by the OPRAM algorithm. Keywords: Oblivious parallel RAM computational security
1
· Oblivious RAM · Statistical and
Introduction
Oblivious RAM (ORAM), initially proposed by Goldreich and Ostrovsky [17,18], is a powerful primitive that allows oblivious accesses to sensitive data, such that Online eprint version [6] of this paper: https://eprint.iacr.org/2016/1084. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 72–107, 2017. https://doi.org/10.1007/978-3-319-70503-3_3
Circuit OPRAM
73
access patterns during the computation reveal no secret information. Since its original proposal [18], ORAM has been shown to be promising in various application settings including secure processors [11,13,14,25,30], cloud outsourced storage [19,32,33,40] and secure multi-party computation [15,16,20,22,24,37]. Although ORAM is broadly useful, it is inherently sequential and does not support parallelism. On the other hand, parallelism is universal in modern architectures such as cloud platforms and multi-core processors. Motivated by this apparent discrepancy, in a recent seminal work [3], Boyle et al.
Data Loading...
