Your browser does not fully support modern features. Please upgrade for a smoother experience.
Submitted Successfully!
+1 credit
Thank you for your contribution! You can also upload a video entry or images related to this topic.
For video creation, please contact our Academic Video Service.
| Version | Summary | Created by | Modification | Content Size | Created at | Operation |
|---|---|---|---|---|---|---|
| 1 | Vivi Li | -- | 3065 | 2022-12-02 01:44:00 |
Video Upload Options
We provide professional Academic Video Service to translate complex research into visually appealing presentations. Would you like to try it?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Oblivious Ram. Encyclopedia. Available online: https://encyclopedia.pub/entry/37776 (accessed on 30 September 2026).
HandWiki. Oblivious Ram. Encyclopedia. Available at: https://encyclopedia.pub/entry/37776. Accessed September 30, 2026.
HandWiki. "Oblivious Ram" Encyclopedia, https://encyclopedia.pub/entry/37776 (accessed September 30, 2026).
HandWiki. (2022, December 02). Oblivious Ram. In Encyclopedia. https://encyclopedia.pub/entry/37776
HandWiki. "Oblivious Ram." Encyclopedia. Web. 02 December, 2022.
Copy Citation
An Oblivious RAM (ORAM) simulator is a compiler that transforms algorithms in such a way that the resulting algorithms preserve the input-output behavior of the original algorithm but the distribution of memory access pattern of the transformed algorithm is independent of the memory access pattern of the original algorithm. The definition of ORAMs is motivated by the fact that an adversary can obtain nontrivial information about the execution of a program and the nature of the data that it is dealing with, just by observing the pattern in which various locations of memory are accessed during its execution. An adversary can get this information even if the data values are all encrypted. The definition suits equally well to the settings of protected programs running on unprotected shared memory as well as a client running a program on its system by accessing previously stored data on a remote server. The concept was formulated by Oded Goldreich in 1987.
original algorithm
shared memory
oram
References
- Nicholas Pippenger and Michael J. Fischer. 1979. Relations among complexity measures. Journal of ACM. DOI = http://dl.acm.org/citation.cfm?id=322138
- Kai-Min Chung and Rafael Pass. 2013. A simple ORAM. IACR Cryptology ePrint Archive. DOI = http://eprint.iacr.org/2013/243
- Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 182-194. doi:10.1145/28395.28416 https://doi.org/10.1145%2F28395.28416
- Rafail Ostrovsky. Efficient computation on oblivious rams. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13–17, 1990.
- Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. Journal of ACM.1996
- Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. On the (in) security of hash-based oblivious ram and a new balancing scheme. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. 2012
- Rafail Ostrovsky and Victor Shoup. Private information storage (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing. 1997.
- Elaine Shi, T-H Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious ram with [math]\displaystyle{ O((\log n)^3) }[/math] worst-case cost. In Advances in Cryptology. ASIACRYPT 2011.
- Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Oblivious ram simulation with efficient worst-case access overhead. In Proceedings of the 3rd ACM workshop on Cloud computing security workshop. 2011.
- Kai-Min Chung, Zhenming Liu, and Rafael Pass. Statistically-secure ORAM with [math]\displaystyle{ \tilde(\log^2 n) }[/math] overhead. In Advances in Cryptology - ASIACRYPT 2014.
- Miklos Ajtai. Oblivious rams without cryptographic assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC. 2010
- Ivan Damgard, Sigurd Meldgaard, and Jesper Buus Nielsen. Perfectly secure oblivious RAM without random oracles. In Theory of Cryptography Conference, TCC. 2011
- Elette Boyle and Moni Naor. Is there an oblivious RAM lower bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. 2016.
More
Information
Subjects:
Computer Science, Theory & Methods
Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:
View Times:
862
Entry Collection:
HandWiki
Revision:
1 time
(View History)
Update Date:
02 Dec 2022
Table of Contents
Notice
You are not a member of the advisory board for this topic. If you want to update advisory board member profile, please contact office@encyclopedia.pub.
OK
Confirm
Only members of the Encyclopedia advisory board for this topic are allowed to note entries. Would you like to become an advisory board member of the Encyclopedia?
Yes
No
${ textCharacter }/${ maxCharacter }
Submit
Cancel
Back
Comments
${ item }
|
${ item.createdUser.fullName }
${ item.createdAt }
${ item.vote }
${ item.reply }
Delete
${ reply.createdUser.fullName }
${ reply.createdAt }
${ reply.vote }
Delete
There is no reply to this comment~
${ item.replyTextCharacter }/${ item.replyMaxCharacter }
Submit
Cancel
More
No more~
There is no comment~
${ textCharacter }/${ maxCharacter }
Submit
Cancel
${ selectedItem.replyTextCharacter }/${ selectedItem.replyMaxCharacter }
Submit
Cancel
Confirm
Are you sure to Delete?
Yes
No