Journal articles on the topic 'Oblivious RAM (ORAM)'
To see the other types of publications on this topic, follow the link: Oblivious RAM (ORAM).
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 16 journal articles for your research on the topic 'Oblivious RAM (ORAM).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Wagh, Sameer, Paul Cuff, and Prateek Mittal. "Differentially Private Oblivious RAM." Proceedings on Privacy Enhancing Technologies 2018, no. 4 (October 1, 2018): 64–84. http://dx.doi.org/10.1515/popets-2018-0032.
Full textAbstract:
Abstract In this work, we investigate if statistical privacy can enhance the performance of ORAM mechanisms while providing rigorous privacy guarantees. We propose a formal and rigorous framework for developing ORAM protocols with statistical security viz., a differentially private ORAM (DP-ORAM). We present Root ORAM, a family of DP-ORAMs that provide a tunable, multi-dimensional trade-off between the desired bandwidth overhead, local storage and system security. We theoretically analyze Root ORAM to quantify both its security and performance. We experimentally demonstrate the benefits of Root ORAM and find that (1) Root ORAM can reduce local storage overhead by about 2× for a reasonable values of privacy budget, significantly enhancing performance in memory limited platforms such as trusted execution environments, and (2) Root ORAM allows tunable trade-offs between bandwidth, storage, and privacy, reducing bandwidth overheads by up to 2×-10× (at the cost of increased storage/statistical privacy), enabling significant reductions in ORAM access latencies for cloud environments. We also analyze the privacy guarantees of DP-ORAMs through the lens of information theoretic metrics of Shannon entropy and Min-entropy [16]. Finally, Root ORAM is ideally suited for applications which have a similar access pattern, and we showcase its utility via the application of Private Information Retrieval.
2
Gancher, Joshua, Adam Groce, and Alex Ledger. "Externally Verifiable Oblivious RAM." Proceedings on Privacy Enhancing Technologies 2017, no. 2 (April 1, 2017): 149–71. http://dx.doi.org/10.1515/popets-2017-0021.
Full textAbstract:
AbstractWe present the idea ofexternally verifiableoblivious RAM (ORAM). Our goal is to allow a client and server carrying out an ORAM protocol to have disputes adjudicated by a third party, allowing for the enforcement of penalties against an unreliable or malicious server. We give a security definition that guarantees protection not only against a malicious server but also against a client making false accusations. We then give modifications of the Path ORAM [15] and Ring ORAM [9] protocols that meet this security definition. These protocols both have the same asymptotic runtimes as the semi-honest original versions and require the external verifier to be involved only when the client or server deviates from the protocol. Finally, we implement externally verified ORAM, along with an automated cryptocurrency contract to use as the external verifier.
3
Gong, Yunping, Fei Gao, Wenmin Li, Hua Zhang, Zhengping Jin, and Qiaoyan Wen. "LPS-ORAM: Perfectly Secure Oblivious RAM with Logarithmic Bandwidth Overhead." Security and Communication Networks 2022 (August 12, 2022): 1–12. http://dx.doi.org/10.1155/2022/9032828.
Full textAbstract:
Oblivious Random Access Machine (ORAM) is a cryptographic tool used to obfuscate the access pattern. In this paper, we focus on perfect security of ORAM. A perfectly secure ORAM is an ORAM that can resist against an adversary with unlimited computing power, and the failure probability of ORAM is zero rather than negligible. Since all existing perfectly secure single-server ORAM solutions require at least sublinear worst-case bandwidth overhead, we pose a natural and open question: can we construct a perfectly secure single-server ORAM with logarithmic worst-case bandwidth overhead? In this paper, we propose the first tree-based perfectly secure ORAM scheme, named LPS-ORAM. To meet the requirements of perfectly secure ORAM, two techniques are presented. One technique is dynamic remapping associated with a mutable scope, and the other is dynamically balanced eviction. Their combined effect allows the root bucket to never fill up while maintaining its statistical security in tree-based ORAM. In the worst case, our solution achieves logarithmic bandwidth overhead. Therefore, our solution answers the open question in the affirmative. In terms of overhead for temporary storage on the client side, compared with the latest perfectly secure ORAM solution, our solution is reduced from sublinear to logarithmic, and even if the server storage overhead scales lightly, it is still at the same level of quantity as the state of the art. Finally, the evaluation results show that our LPS-ORAM has a significant advantage in terms of bandwidth overhead and overhead for temporary storage on the client side.
4
Chakraborti, Anrin, and Radu Sion. "SqORAM: Read-Optimized Sequential Write-Only Oblivious RAM." Proceedings on Privacy Enhancing Technologies 2020, no. 1 (January 1, 2020): 216–34. http://dx.doi.org/10.2478/popets-2020-0012.
Full textAbstract:
AbstractOblivious RAMs (ORAMs) allow a client to access data from an untrusted storage device without revealing the access patterns. Typically, the ORAM adversary can observe both read and write accesses. Write-only ORAMs target a more practical, multi-snapshot adversary only monitoring client writes – typical for plausible deniability and censorship-resilient systems. This allows write-only ORAMs to achieve significantly-better asymptotic performance. However, these apparent gains do not materialize in real deployments primarily due to the random data placement strategies used to break correlations between logical and physical names-paces, a required property for write access privacy. Random access performs poorly on both rotational disks and SSDs (often increasing wear significantly, and interfering with wear-leveling mechanisms).In this work, we introduce SqORAM, a new locality-preserving write-only ORAM that preserves write access privacy without requiring random data access. Data blocks close to each other in the logical domain land in close proximity on the physical media. Importantly, SqORAM maintains this data locality property over time, significantly increasing read throughput.A full Linux kernel-level implementation of SqORAM is 100x faster than non locality-preserving solutions for standard workloads and is 60-100% faster than the state-of-the-art for typical file system workloads.
5
Haider, Syed, and Marten van Dijk. "Flat ORAM: A Simplified Write-Only Oblivious RAM Construction for Secure Processors." Cryptography 3, no. 1 (March 25, 2019): 10. http://dx.doi.org/10.3390/cryptography3010010.
Full textAbstract:
Oblivious RAM (ORAM) is a cryptographic primitive which obfuscates the access patterns to a storage, thereby preventing privacy leakage. So far in the current literature, only ‘fully functional’ ORAMs are widely studied which can protect, at a cost of considerable performance penalty, against the strong adversaries who can monitor all read and write operations. However, recent research has shown that information can still be leaked even if only the write access pattern (not reads) is visible to the adversary. For such weaker adversaries, a fully functional ORAM turns out to be an overkill, causing unnecessary overheads. Instead, a simple ‘write-only’ ORAM is sufficient, and, more interestingly, is preferred as it can offer far better performance and energy efficiency than a fully functional ORAM. In this work, we present Flat ORAM: an efficient write-only ORAM scheme which outperforms the closest existing write-only ORAM called HIVE. HIVE suffers from performance bottlenecks while managing the memory occupancy information vital for correctness of the protocol. Flat ORAM introduces a simple idea of Occupancy Map (OccMap) to efficiently manage the memory occupancy information resulting in far better performance. Our simulation results show that, compared to HIVE, Flat ORAM offers 50 % performance gain on average and up to 80 % energy savings.
6
Ma, Qiumao, and Wensheng Zhang. "Octopus ORAM: An Oblivious RAM with Communication and Server Storage Efficiency." ICST Transactions on Security and Safety 6, no. 20 (April 29, 2019): 162405. http://dx.doi.org/10.4108/eai.29-4-2019.162405.
Full text
7
Gordon, Steven, Xinyi Huang, Atsuko Miyaji, Chunhua Su, Karin Sumongkayothin, and Komwut Wipusitwarakun. "Recursive Matrix Oblivious RAM: An ORAM Construction for Constrained Storage Devices." IEEE Transactions on Information Forensics and Security 12, no. 12 (December 2017): 3024–38. http://dx.doi.org/10.1109/tifs.2017.2730584.
Full text
8
Guo, Zhong-Yi, Yu-Chi Chen, and Hsiu-Ping Lin. "Oblivious Access for Decentralized Database Systems: A New Asymmetric Framework from Smart Contracts." Symmetry 14, no. 4 (March 25, 2022): 680. http://dx.doi.org/10.3390/sym14040680.
Full textAbstract:
With the rapid development of cloud servers, storing data on cloud servers has become a popular option. However, cloud servers are centralized. Storing data on centralized cloud servers may involve some risks. For example, the data access pattern may be revealed when accessing data on cloud servers. Therefore, protecting a user’s patterns has become a crucial concern. Oblivious RAM (ORAM) is a candidate solution to hide the data access pattern. However, it inherently induces some overhead of accessing data, and many blockchain-based applications also do not consider the access pattern leakage issues. In this paper, we address these issues above by proposing a decentralized database system with oblivious access in a (parallel) smart contract model. The interactions of oblivious access are asymmetric where the smart contract side is expected to put much effort into computation. The proposed system slightly reduces the overhead of ORAM and overcomes the issues stemming from the centralization of servers. The main techniques are to use the garbled circuits to reduce the cost of communication and to combine with the parallel smart contract model to (conceptually) improve the performance of smart contract execution on the blockchain.
9
Zhang, Jinsheng, Qiumao Ma, Wensheng Zhang, and Daji Qiao. "TSKT-ORAM: A Two-Server k-ary Tree Oblivious RAM without Homomorphic Encryption." Future Internet 9, no. 4 (September 27, 2017): 57. http://dx.doi.org/10.3390/fi9040057.
Full text
10
Tueno, Anselme, Florian Kerschbaum, and Stefan Katzenbeisser. "Private Evaluation of Decision Trees using Sublinear Cost." Proceedings on Privacy Enhancing Technologies 2019, no. 1 (January 1, 2019): 266–86. http://dx.doi.org/10.2478/popets-2019-0015.
Full textAbstract:
Abstract Decision trees are widespread machine learning models used for data classification and have many applications in areas such as healthcare, remote diagnostics, spam filtering, etc. In this paper, we address the problem of privately evaluating a decision tree on private data. In this scenario, the server holds a private decision tree model and the client wants to classify its private attribute vector using the server’s private model. The goal is to obtain the classification while preserving the privacy of both – the decision tree and the client input. After the computation, only the classification result is revealed to the client, while nothing is revealed to the server. Many existing protocols require a constant number of rounds. However, some of these protocols perform as many comparisons as there are decision nodes in the entire tree and others transform the whole plaintext decision tree into an oblivious program, resulting in higher communication costs. The main idea of our novel solution is to represent the tree as an array. Then we execute only d – the depth of the tree – comparisons. Each comparison is performed using a small garbled circuit, which output secret-shares of the index of the next node. We get the inputs to the comparison by obliviously indexing the tree and the attribute vector. We implement oblivious array indexing using either garbled circuits, Oblivious Transfer or Oblivious RAM (ORAM). Using ORAM, this results in the first protocol with sub-linear cost in the size of the tree. We implemented and evaluated our solution using the different array indexing procedures mentioned above. As a result, we are not only able to provide the first protocol with sublinear cost for large trees, but also reduce the communication cost for the large real-world data set “Spambase” from 18 MB to 1[triangleright]2 MB and the computation time from 17 seconds to less than 1 second in a LAN setting, compared to the best related work.
11
Liu, Lingtong, Yulong Shen, Shuiguang Zeng, and Zhiwei Zhang. "FO-Sketch: A Fast Oblivious Sketch for Secure Network Measurement Service in the Cloud." Electronics 10, no. 16 (August 20, 2021): 2020. http://dx.doi.org/10.3390/electronics10162020.
Full textAbstract:
Network measurements are the foundation for network applications. The metrics generated by those measurements help applications improve their performance of the monitored network and harden their security. As severe network attacks using leaked information from a public cloud exist, it raises privacy and security concerns if directly deployed in network measurement services in a third-party public cloud infrastructure. Recent studies, most notably OblivSketch, demonstrated the feasibility of alleviating those concerns by using trusted hardware and Oblivious RAM (ORAM). As their performance is not good enough, and there are certain limitations, they are not suitable for broad deployment. In this paper, we propose FO-Sketch, a more efficient and general network measurement service that meets the most stringent security requirements, especially for a large-scale network with heavy traffic volume and burst traffic. Let a mergeable sketch update the local flow statistics in each local switch; FO-Sketch merges (in an Intel SGX-created enclave) these sketches obliviously to form a global “one big sketch” in the cloud. With the help of Oblivious Shuffle, Divide and Conquer, and SIMD speedup, we optimize all of the critical routines in our FO-Sketch to make it 17.3x faster than a trivial oblivious solution. While keeping the same level of accuracy and packet processing throughput as non-oblivious Elastic Sketch, our FO-Sketch needs only ∼4.5 MB enclave memory space in total to record metrics and for PORAM to store the global sketch in the cloud. Extensive experiments demonstrate that, for the recommended setting, it takes only ∼ 0.6 s in total to rebuild those data during each measurement interval.
12
Zhao, Bo, Zhihong Chen, Hai Lin, and XiangMin Ji. "A Constant Round Write-Only ORAM." Applied Sciences 10, no. 15 (August 3, 2020): 5366. http://dx.doi.org/10.3390/app10155366.
Full textAbstract:
The write-only oblivious RAM (ORAM) is proposed to efficiently protect the privacy of applications such as cloud storage synchronization and encrypted hidden volumes. For N blocks with size B = Ω(log2N), the most efficient write-only ORAM, DetWoORAM, achieves O(B) communication complexity with O(logN) rounds per logical write. We propose a two-level write-only ORAM and achieve O(B) communication complexity with O(1) rounds. Similar to the traditional bucket-based ORAM schemes, we set a rate for the write operation to further reduce the communication complexity. The top-level stores data blocks in a flat array and the write pattern is protected by writing blocks uniformly at random. The second level employs a binary tree to store the position map of data blocks. To avoid recursive storage, a static position map for blocks in the second level is used. Both the analysis and experiments show that, besides the achieved low communication complexity and rounds, the stash sizes in the top level and the second level are bounded to O(B) and ω(B), respectively.
13
Alam, A. K. M. Mubashwir, Sagar Sharma, and Keke Chen. "SGX-MR: Regulating Dataflows for Protecting Access Patterns of Data-Intensive SGX Applications." Proceedings on Privacy Enhancing Technologies 2021, no. 1 (January 1, 2021): 5–20. http://dx.doi.org/10.2478/popets-2021-0002.
Full textAbstract:
AbstractIntel SGX has been a popular trusted execution environment (TEE) for protecting the integrity and confidentiality of applications running on untrusted platforms such as cloud. However, the access patterns of SGX-based programs can still be observed by adversaries, which may leak important information for successful attacks. Researchers have been experimenting with Oblivious RAM (ORAM) to address the privacy of access patterns. ORAM is a powerful low-level primitive that provides application-agnostic protection for any I/O operations, however, at a high cost. We find that some application-specific access patterns, such as sequential block I/O, do not provide additional information to adversaries. Others, such as sorting, can be replaced with specific oblivious algorithms that are more efficient than ORAM. The challenge is that developers may need to look into all the details of application-specific access patterns to design suitable solutions, which is time-consuming and error-prone. In this paper, we present the lightweight SGX based MapReduce (SGX-MR) approach that regulates the dataflow of data-intensive SGX applications for easier application-level access-pattern analysis and protection. It uses the MapReduce framework to cover a large class of data-intensive applications, and the entire framework can be implemented with a small memory footprint. With this framework, we have examined the stages of data processing, identified the access patterns that need protection, and designed corresponding efficient protection methods. Our experiments show that SGX-MR based applications are much more efficient than the ORAM-based implementations.
14
Riazi, M. Sadegh, Ebrahim M. Songhori, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. "Toward Practical Secure Stable Matching." Proceedings on Privacy Enhancing Technologies 2017, no. 1 (January 1, 2017): 62–78. http://dx.doi.org/10.1515/popets-2017-0005.
Full textAbstract:
Abstract The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on Yao’s garbled circuit protocol and Oblivious RAM (ORAM). Our scheme can securely compute a stable match for 8k pairs four orders of magnitude faster than the previously best known method. We achieve this by introducing a compact and efficient sub-linear size circuit. We even further decrease the computation cost by three orders of magnitude by proposing a novel technique to avoid unnecessary iterations in the SM algorithm. We evaluate our implementation for several problem sizes and plan to publish it as open-source.
15
Asharov, Gilad, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. "OptORAMa: Optimal Oblivious RAM." Journal of the ACM, October 6, 2022. http://dx.doi.org/10.1145/3566049.
Full textAbstract:
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω (log N ) amortized blowup in memory accesses is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security. A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with O (log N ) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O (log N · log log N ) amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O ( n ) algorithm improves the previously best known deterministic or randomized algorithms whose running time is O ( n · log n ) or O ( n · log log n ), respectively.
16
Chan, T.-H. Hubert, Kai-Min Chung, Bruce Maggs, and Elaine Shi. "Foundations of Differentially Oblivious Algorithms." Journal of the ACM, August 10, 2022. http://dx.doi.org/10.1145/3555984.
Full textAbstract:
It is well-known that a program’s memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program’s runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “(ϵ, δ )-differential obliviousness”. We separate the notion of (ϵ, δ )-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ϵ and δ , not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy “with little extra overhead”). On the other hand, we show that for very demanding choices of ϵ and δ , the same lower bounds for oblivious algorithms would be preserved for (ϵ, δ )-differential obliviousness.