Shared register emulations on top of message- passing systems provide an illusion of a simpler shared memory system which can make the task of a system designer easier. Numerous shared register applications have a considerably high read to write ratio. Thus having algorithms that make reads more efficient than writes is a fair trade-off.
Typically such algorithms for reads and writes are asymmetric and sacrifice the stringent consistency condition atomicity as it is impossible to have fast reads for multi-writer atomicity. Safety is a consistency condition has has gathered interest from both the systems and theory community as it is weaker than atomicity yet provides strong enough guarantees like “strong consistency” or read-my-write consistency. One requirement that is assumed by many researchers is that of the reliable broadcast (RB) primitive, which ensures the all or none property during a broadcast. One drawback is that such a primitive takes 1.5 rounds to complete.
This paper implements an efficient multi-writer multi-reader safe register without using a reliable broadcast primitive. More- over, we provide fast reads or one-shot reads – our read operation can be completed in one round of client-to-server communication. Of course, this comes with the price of requiring more servers when compared to prior solutions assuming reliable broadcast. However, we show that this increased number of servers is indeed necessary as we prove a tight bound on the number of servers required to implement Byzantine-fault tolerant safe registers in a system without reliable broadcast.
We extend our results to data stored using erasure coding as well. We present an emulation of single-writer multi-reader safe register based on MDS code. The usage of MDS code reduces storage cost and communication cost. On the negative side, we also show that to use MDS code and achieve one-shot read at the same time, we need even more servers.
more »
« less
A Lower Bound for One-Round Oblivious RAM
We initiate a fine-grained study of the round complexity of Oblivious RAM (ORAM). We prove that any one-round balls-in-bins ORAM that does not duplicate balls must have either 𝛺(𝑁‾‾√) bandwidth or 𝛺(𝑁‾‾√) client memory, where N is the number of memory slots being simulated. This shows that such schemes are strictly weaker than general (multi-round) ORAMs or those with server computation, and in particular implies that a one-round version of the original square-root ORAM of Goldreich and Ostrovksy (J. ACM 1996) is optimal. We prove this bound via new techniques that differ from those of Goldreich and Ostrovksy, and of Larsen and Nielsen (CRYPTO 2018), which achieved an 𝛺(log𝑁) bound for balls-in-bins and general multi-round ORAMs respectively. Finally we give a weaker extension of our bound that allows for limited duplication of balls, and also show that our bound extends to multiple-round ORAMs of a restricted form that include the best known constructions.
more »
« less
- Award ID(s):
- 1453132
- NSF-PAR ID:
- 10252063
- Date Published:
- Journal Name:
- IACR Theory of Cryptography Conference: TCC 2020
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Oblivious Random Access Machine (ORAM) enables a client to access her data without leaking her access patterns. Existing client-efficient ORAMs either achieve O(log N) client-server communication blowup without heavy computation, or O(1) blowup but with expensive homomorphic encryptions. It has been shown that O(log N) bandwidth blowup might not be practical for certain applications, while schemes with O(1) communication blowup incur even more delay due to costly homomorphic operations. In this paper, we propose a new distributed ORAM scheme referred to as Shamir Secret Sharing ORAM (S3ORAM), which achieves O(1) client-server bandwidth blowup and O(1) blocks of client storage without relying on costly partial homomorphic encryptions. S3ORAM harnesses Shamir Secret Sharing, tree-based ORAM structure and a secure multi-party multiplication protocol to eliminate costly homomorphic operations and, therefore, achieves O(1) clientserver bandwidth blowup with a high computational efficiency. We conducted comprehensive experiments to assess the performance of S3ORAM and its counterparts on actual cloud environments, and showed that S3ORAM achieves three orders of magnitude lower end-to-end delay compared to alternatives with O(1) client communication blowup (Onion-ORAM), while it is one order of magnitude faster than Path-ORAM for a network with a moderate bandwidth quality. We have released the implementation of S3ORAM for further improvement and adaptation.more » « less
-
Shlomi Dolev, Ehud Gudes (Ed.)Data-dependent accesses to memory are necessary for many real-world applications, but their cost remains prohibitive in secure computation. Prior work either focused on minimizing the need for data-dependent access in these applications, or reduced its cost by improving oblivious RAM for secure computation (SC-ORAM). Despite extensive efforts to improve SC-ORAM, the most concretely efficient solutions still require ≈ 0.7 s per access to arrays of 230 entries. This plainly precludes using MPC in a number of settings. In this work, we take a pragmatic approach, exploring how concretely cheap MPC RAM access could be made if we are willing to allow one of the participants to learn the access pattern. We design a highly efficient Shared-Output Client-Server ORAM (SOCS-ORAM ) that has constant overhead, uses one round-trip of interaction per access, and whose access cost is independent of array size. SOCS-ORAM is useful in settings with hard performance constraints, where one party in the computation is more trust-worthy and is allowed to learn the RAM access pattern. Our SOCS-ORAM is assisted by a third helper party that helps initialize the protocol and is designed for the honest-majority semi-honest corruption model. We implement our construction in C++ and report its performance. For an array of length 230 with 4B entries, we communicate 13B per access and take essentially no overhead beyond network latency.more » « less
-
more » « less
Oblivious Random Access Machine (ORAM) allows a client to hide the access pattern when accessing sensitive data on a remote server. It is known that there exists a logarithmic communication lower bound on any passive ORAM construction, where the server only acts as the storage service. This overhead, however, was shown costly for some applications. Several active ORAM schemes with server computation have been proposed to overcome this limitation. However, they mostly rely on costly homomorphic encryptions, whose performance is worse than passive ORAM. In this article, we propose S3ORAM, a new multi-server ORAM framework, which features
O (1) client bandwidth blowup and low client storage without relying on costly cryptographic primitives. Our key idea is to harness Shamir Secret Sharing and a multi-party multiplication protocol on applicable binary tree-ORAM paradigms. This strategy allows the client to instruct the server(s) to perform secure and efficient computation on his/her behalf with a low intervention thereby, achieving a constant client bandwidth blowup and low server computational overhead. Our framework can also work atop a generalk -ary tree ORAM structure (k ≥ 2). We fully implemented our framework, and strictly evaluated its performance on a commodity cloud platform (Amazon EC2). Our comprehensive experiments confirmed the efficiency of S3ORAM framework, where it is approximately 10× faster than the most efficient passive ORAM (i.e., Path-ORAM) for a moderate network bandwidth while being three orders of magnitude faster than active ORAM withO (1) bandwidth blowup (i.e., Onion-ORAM). We have open-sourced the implementation of our framework for public testing and adaptation. -
Abstract Let Ω ⊂ ℝ n + 1 {\Omega\subset\mathbb{R}^{n+1}} , n ≥ 2 {n\geq 2} , be a 1-sided non-tangentially accessible domain (aka uniform domain), that is, Ω satisfies the interior Corkscrew and Harnack chain conditions, which are respectively scale-invariant/quantitative versions of openness and path-connectedness. Let us assume also that Ω satisfies the so-called capacity density condition, a quantitative version of the fact that all boundary points are Wiener regular. Consider L 0 u = - div ( A 0 ∇ u ) {L_{0}u=-\mathrm{div}(A_{0}\nabla u)} , L u = - div ( A ∇ u ) {Lu=-\mathrm{div}(A\nabla u)} , two real (non-necessarily symmetric) uniformly elliptic operators in Ω, and write ω L 0 {\omega_{L_{0}}} , ω L {\omega_{L}} for the respective associated elliptic measures. The goal of this program is to find sufficient conditions guaranteeing that ω L {\omega_{L}} satisfies an A ∞ {A_{\infty}} -condition or a RH q {\mathrm{RH}_{q}} -condition with respect to ω L 0 {\omega_{L_{0}}} . In this paper we establish that if the discrepancy of the two matrices satisfies a natural Carleson measure condition with respect to ω L 0 {\omega_{L_{0}}} , then ω L ∈ A ∞ ( ω L 0 ) {\omega_{L}\in A_{\infty}(\omega_{L_{0}})} . Additionally, we can prove that ω L ∈ RH q ( ω L 0 ) {\omega_{L}\in\mathrm{RH}_{q}(\omega_{L_{0}})} for some specific q ∈ ( 1 , ∞ ) {q\in(1,\infty)} , by assuming that such Carleson condition holds with a sufficiently small constant. This “small constant” case extends previous work of Fefferman–Kenig–Pipher and Milakis–Pipher together with the last author of the present paper who considered symmetric operators in Lipschitz and bounded chord-arc domains, respectively. Here we go beyond those settings, our domains satisfy a capacity density condition which is much weaker than the existence of exterior Corkscrew balls. Moreover, their boundaries need not be Ahlfors regular and the restriction of the n -dimensional Hausdorff measure to the boundary could be even locally infinite. The “large constant” case, that is, the one on which we just assume that the discrepancy of the two matrices satisfies a Carleson measure condition, is new even in the case of nice domains (such as the unit ball, the upper-half space, or non-tangentially accessible domains) and in the case of symmetric operators. We emphasize that our results hold in the absence of a nice surface measure: all the analysis is done with the underlying measure ω L 0 {\omega_{L_{0}}} , which behaves well in the scenarios we are considering. When particularized to the setting of Lipschitz, chord-arc, or 1-sided chord-arc domains, our methods allow us to immediately recover a number of existing perturbation results as well as extend some of them.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-64375-1_16
