Questions tagged [oblivious-ram]
Oblivious RAM (O-RAM) is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications.
15
questions
1
vote
0
answers
58
views
What exactly is the RAM program runtime?
In my previous understanding, if a RAM program requires $T$ read/write operations to memory during its execution, then the runtime of this RAM program is $T$. However, as I have read some literature, ...
- 112
0
votes
0
answers
20
views
Is there any new progress on the issue of 2-server private information retrieval with secret shared index?
Recently, I encountered a secret retrieval problem. In my scenario, two parties each holds a secret share of index $i$, and they want to get $bucket_i$ together. I found that CCS17 paper Floram is ...
- 73
1
vote
0
answers
31
views
Is it possible to Publicly Query Privately Held Data with proof of Correctness?
We can secretly query inputs from a public DBs using what we call in the literature PIR. We can secretly query inputs from a privately held DB by means of Private Set Intersection (PSI). We can also ...
- 862
10
votes
0
answers
190
views
Is anyone using ORAM in practice?
Oblivious RAM has been around in theory for about 30 years at this point.
Is anyone using it in practice? Has it made its way into industry? (Including any variants such as MPC ORAM or ORAM that uses ...
- 399
2
votes
0
answers
46
views
Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?
Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost ...
- 21
2
votes
1
answer
106
views
Path ORAM asymptotics for arbitrary block sizes
The Path-ORAM construction assumes that the data outsourced into the ORAM scheme is split into blocks of size $\Omega(\log^2{n})$. With respect to this assumption the authors state that their storage ...
- 1,066
2
votes
1
answer
108
views
How is the re-encryption done in Path ORAM?
Path ORAM block headers store nonce that is used to re-encrypt the data on access. Every time a block is accessed, the nonce is ...
- 529
-1
votes
2
answers
107
views
Why is on-chip data considered to be secure in secure processor setting?
I was taking a look into the paper PHANTOM: Practical Oblivious Computation in a Secure Processor. The introduction says,
Confidentiality of data is a major concern for enterprises and
...
- 529
6
votes
2
answers
378
views
Efficiency of oblivious algorithms vs non-oblivious algorithms?
Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independednt ...
- 540
6
votes
2
answers
362
views
Are any of the practical implementations of ORAM being used in a real world system?
The concept of Oblivious RAM (ORAM) was first introduced by Oded Goldreich and Rafail Ostrovsky in 1996. However, in the past 5-10 years there has been a surge in the amount of research that looks ...
- 540
5
votes
2
answers
362
views
ORAM over Third Party DB
Oblivious Ram (ORAM) is a cryptographic technique that is used for secure DB querying without leakage on the access patterns. There are several schemes for ORAM, amongst the most popular ones, there ...
- 862
2
votes
1
answer
98
views
About ORAM initalization and running out of space
I have two questions about ORAM
Since at the beginning,the server allocates unused storage for ORAM cient,there are no user's data in the storage.if now client access the storage the server will know ...
- 151
2
votes
0
answers
62
views
PathORAM with read path eviction
I am currently trying to implement the pathORAM algorithm as describe in this paper:
https://eprint.iacr.org/2013/280.pdf
The paper states that with high probability, the stash size will be bounded ...
- 151
3
votes
1
answer
108
views
Optimal bandwidth cost for Oblivious RAM
Goldreich and Ostrovsky show that any ORAM algorithm must have bandwidth cost $\Omega(logN)$, where $N$ is the total number of blocks outsourced. This is in Theorem C of this paper. But they didn't ...
- 915
5
votes
2
answers
537
views
Which concrete applications benefit from Oblivious RAM constructions?
The main motivation for Oblivious RAM (ORAM) is that, for instance, in the "cloud" setting a client outsources his data to a server in the form of encrypted blocks. Later on, he wants to perform read ...
- 1,066