More Web Proxy on the site http://driver.im/

research-article

Design space exploration and optimization of path oblivious RAM in secure processors

Authors:

Christopher W. Fletcher,

Marten van Dijk,

Srinivas DevadasAuthors Info & Claims

ISCA '13: Proceedings of the 40th Annual International Symposium on Computer Architecture

Pages 571 - 582

https://doi.org/10.1145/2485922.2485971

Published: 23 June 2013 Publication History

Abstract

Keeping user data private is a huge problem both in cloud computing and computation outsourcing. One paradigm to achieve data privacy is to use tamper-resistant processors, inside which users' private data is decrypted and computed upon. These processors need to interact with untrusted external memory. Even if we encrypt all data that leaves the trusted processor, however, the address sequence that goes off-chip may still leak information. To prevent this address leakage, the security community has proposed ORAM (Oblivious RAM). ORAM has mainly been explored in server/file settings which assume a vastly different computation model than secure processors. Not surprisingly, naïvely applying ORAM to a secure processor setting incurs large performance overheads.

In this paper, a recent proposal called Path ORAM is studied. We demonstrate techniques to make Path ORAM practical in a secure processor setting. We introduce background eviction schemes to prevent Path ORAM failure and allow for a performance-driven design space exploration. We propose a concept called super blocks to further improve Path ORAM's performance, and also show an efficient integrity verification scheme for Path ORAM. With our optimizations, Path ORAM overhead drops by 41.8%, and SPEC benchmark execution time improves by 52.4% in relation to a baseline configuration. Our work can be used to improve the security level of previous secure processors.

References

[1]

W. Arbaugh, D. Farber, and J. Smith, "A Secure and Reliable Bootstrap Architecture," in Proceedings of the 1997 IEEE Symposium on Security and Privacy, May 1997, pp. 65--71. {Online}. Available: citeseer.nj.nec.com/arbaugh97secure.html

Digital Library

[2]

V. Costan, L. F. G. Sarmenta, M. van Dijk, and S. Devadas, "The trusted execution module: Commodity general-purpose trusted computing," in CARDIS, 2008.

Digital Library

[3]

C. Fletcher, M. van Dijk, and S. Devadas, "Secure Processor Architecture for Encrypted Computation on Untrusted Programs," in Proceedings of the 7th ACM CCS Workshop on Scalable Trusted Computing, Oct. 2012, pp. 3--8.

Digital Library

[4]

C. W. Fletcher, "Ascend: An architecture for performing secure computation on encrypted data," in MIT CSAIL CSG Technical Memo 508, April 2013. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-508/Memo-508.pdf

[5]

L. Gao, J. Yang, M. Chrobak, Y. Zhang, S. Nguyen, and H.-H. S. Lee, "A low-cost memory remapping scheme for address bus protection," in Proceedings of the 15th PACT, ser. PACT '06. ACM, 2006. {Online}. Available: http://doi.acm.org/10.1145/1152154.1152169

Digital Library

[6]

B. Gassend, G. E. Suh, D. Clarke, M. van Dijk, and S. Devadas, "Caches and Merkle Trees for Efficient Memory Integrity Verification," in Proceedings of Ninth International Symposium on High Performance Computer Architecture. New-York: IEEE, February 2003.

Digital Library

[7]

O. Goldreich, "Towards a theory of software protection and simulation on oblivious rams," in STOC, 1987.

Digital Library

[8]

O. Goldreich and R. Ostrovsky, "Software protection and simulation on oblivious rams," in J. ACM, 1996.

Digital Library

[9]

D. Grawrock, The Intel Safer Computing Initiative: Building Blocks for Trusted Computing. Intel Press, 2006.

[10]

R. Huang and G. E. Suh, "Ivec: off-chip memory integrity protection for both security and reliability," in Proceedings of the 37th annual international symposium on Computer architecture, ser. ISCA '10, 2010, pp. 395--406.

Digital Library

[11]

D. Lie, J. Mitchell, C. Thekkath, and M. Horwitz, "Specifying and verifying hardware for tamper-resistant software," in Proceedings of the IEEE Symposium on Security and Privacy, 2003.

Digital Library

[12]

D. Lie, C. Thekkath, and M. Horowitz, "Implementing an untrusted operating system on trusted hardware," in Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 178--192.

Digital Library

[13]

D. Lie, C. Thekkath, M. Mitchell, P. Lincoln, D. Boneh, J. Mitchell, and M. Horowitz, "Architectural Support for Copy and Tamper Resistant Software," in Proceedings of the 9^th Int'l Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), November 2000, pp. 168--177.

Digital Library

[14]

J. R. Lorch, J. W. Mickens, B. Parno, M. Raykova, and J. Schiffman, "Toward practical private access to data centers via parallel oram." IACR Cryptology ePrint Archive, vol. 2012, p. 133, 2012, informal publication. {Online}. Available: http://dblp.uni-trier.de/db/journals/iacr/iacr2012.html#LorchMPRS12

[15]

R. Ostrovsky, "Efficient computation on oblivious rams," in STOC, 1990.

Digital Library

[16]

J. Renau, "Sesc: Superescalar simulator," university of illinois urbana-champaign ECE department, Tech. Rep., 2002. {Online}. Available: http://sesc.sourceforge.net/index.html

[17]

P. Rosenfeld, E. Cooper-Balis, and B. Jacob, "Dramsim2: A cycle accurate memory system simulator," Computer Architecture Letters, vol. 10, no. 1, pp. 16--19, jan.-june 2011.

Digital Library

[18]

L. F. G. Sarmenta, M. van Dijk, C. W. O'Donnell, J. Rhodes, and S. Devadas, "Virtual Monotonic Counters and Count-Limited Objects using a TPM without a Trusted OS," in Proceedings of the 1st ACM CCS Workshop on Scalable Trusted Computing (STC'06), Nov. 2006.

Digital Library

[19]

E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li, "Oblivious ram with o((log n)³) worst-case cost," in Asiacrypt, 2011, pp. 197--214.

Digital Library

[20]

E. Stefanov and E. Shi, "Path O-RAM: An Extremely Simple Oblivious RAM Protocol," Cornell University Library, arXiv:1202.5150v1, 2012, arxiv.org/abs/1202.5150.

[21]

E. Stefanov, E. Shi, and D. Song, "Towards practical oblivious ram," in NDSS, 2012.

[22]

G. E. Suh, D. Clarke, B. Gassend, M. van Dijk, and S. Devadas, "Efficient Memory Integrity Verification and Encryption for Secure Processors," in Proceedings of the 36^th Int'l Symposium on Microarchitecture, Dec 2003, pp. 339--350.

Digital Library

[23]

G. E. Suh, "aegis: Architecture for Tamper-Evident and Tamper-Resistant Processing," in Proceedings of the 17^th Int'l Conference on Supercomputing (MIT-CSAIL-CSG-Memo-474 is an updated version). New-York: ACM, June 2003. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-474/Memo-474.pdf(revisedone)

Digital Library

[24]

G. E. Suh, C. W. O'Donnell, I. Sachdev, and S. Devadas, "Design and Implementation of the aegis Single-Chip Secure Processor Using Physical Random Functions," in Proceedings of the 32^nd Annual International Symposium on Computer Architecture. New-York: ACM, June 2005. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-483/Memo-483.pdf

Digital Library

[25]

Trusted Computing Group, "TCG Specification Architecture Overview Revision 1.2," http://www.trustedcomputinggroup.com/home, 2004.

[26]

C. Yan, D. Englender, M. Prvulovic, B. Rogers, and Y. Solihin, "Improving cost, performance, and security of memory encryption and authentication," in Proceedings of the 33rd annual international symposium on Computer Architecture, ser. ISCA '06, 2006, pp. 179--190.

Digital Library

[27]

J. Yang, L. Gao, Y. Zhang, M. Chrobak, and H. Lee, "A low-cost memory remapping scheme for address bus protection," Journal of Parallel and Distributed Computing, vol. 70, no. 5, pp. 443--457, 2010.

Digital Library

[28]

J. Yang, Y. Zhang, and L. Gao, "Fast secure processor for inhibiting software piracy and tampering," in Microarchitecture, 2003. MICRO-36. Proceedings. 36th Annual IEEE/ACM International Symposium on, dec. 2003, pp. 351--360.

Digital Library

[29]

X. Yu, C. Fletcher, L. Ren, M. van Dijk, and S. Devadas, "Efficient private information retrieval using secure hardware," in MIT CSAIL CSG Technical Memo 509, April 2013. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-509/Memo-509.pdf

[30]

X. Zhuang, T. Zhang, and S. Pande, "HIDE: an infrastructure for efficiently protecting information leakage on the address bus," in ASPLOS-XI: Proceedings of the 11th international conference on Architectural support for programming languages and operating systems. New York, NY, USA: ACM Press, 2004, pp. 72--84.

Digital Library

Cited By

Lim HKim JLee HLuo BLiao XXu JKirda ELie D(2024)uMMU: Securing Data Confidentiality with Unobservable Memory SubsystemProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690340(2993-3007)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690340
Lam MJohnson JXiong WMaeng KGupta ULi YLai LLeontiadis IRhu MLee HReddi VWei GBrooks DSuh ETsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)GPU-based Private Information Retrieval for On-Device Machine Learning InferenceProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624855(197-214)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624855
Rajat RWang YAnnavaram MSolihin YHeinrich M(2023)LAORAM: A Look Ahead ORAM Architecture for Training Large Embedding TablesProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589111(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589111
Show More Cited By

Design space exploration and optimization of path oblivious RAM in secure processors
1. Computer systems organization
2. Social and professional topics
  1. Computing / technology policy

Recommendations

Design space exploration and optimization of path oblivious RAM in secure processors
ICSA '13

Keeping user data private is a huge problem both in cloud computing and computation outsourcing. One paradigm to achieve data privacy is to use tamper-resistant processors, inside which users' private data is decrypted and computed upon. These ...
Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party ...
Adaptively Secure Oblivious Transfer
ASIACRYPT '98: Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology

Oblivious Transfer (OT) is a ubiquitous cryptographic tool that is of fundamental importance in secure protocol design. Despite extensive research into the design and verification of secure and efficient solutions, existing OT protocols enjoy "provable" ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISCA '13: Proceedings of the 40th Annual International Symposium on Computer Architecture

June 2013

686 pages

ISBN:9781450320795

DOI:10.1145/2485922

General Chair:
Avi Mendelson
Technion

ACM SIGARCH Computer Architecture News Volume 41, Issue 3
ICSA '13
June 2013
666 pages
ISSN:0163-5964
DOI:10.1145/2508148
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE CS

In-Cooperation

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

ISCA'13

Sponsor:

ISCA'13: The 40th Annual International Symposium on Computer Architecture

June 23 - 27, 2013

Tel-Aviv, Israel

Acceptance Rates

ISCA '13 Paper Acceptance Rate 56 of 288 submissions, 19%;

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

91
Total Citations
View Citations
858
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)3

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lim HKim JLee HLuo BLiao XXu JKirda ELie D(2024)uMMU: Securing Data Confidentiality with Unobservable Memory SubsystemProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690340(2993-3007)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690340
Lam MJohnson JXiong WMaeng KGupta ULi YLai LLeontiadis IRhu MLee HReddi VWei GBrooks DSuh ETsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)GPU-based Private Information Retrieval for On-Device Machine Learning InferenceProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624855(197-214)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624855
Rajat RWang YAnnavaram MSolihin YHeinrich M(2023)LAORAM: A Look Ahead ORAM Architecture for Training Large Embedding TablesProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589111(1-15)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589111
Li YZhou FChen JJi D(2023)Crowdsensed Data-oriented Distributed and Secure Spatial Query Scheme2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00130(912-919)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00130
Zhu JLi MZhang XBu KZhang MSong T(2023)Hitchhiker: Accelerating ORAM With Dynamic SchedulingIEEE Transactions on Computers10.1109/TC.2023.324827272:8(2321-2335)Online publication date: 1-Aug-2023
https://doi.org/10.1109/TC.2023.3248272
Raoufi MYang JTang XZhang Y(2023)AB-ORAM: Constructing Adjustable Buckets for Space Reduction in Ring ORAM2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071064(361-373)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071064
Zhou MShi EChan TMaimon S(2023)A Theory of Composition for Differential ObliviousnessAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30620-4_1(3-34)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30620-4_1
Asharov GKomargodski ILin WNayak KPeserico EShi E(2022)OptORAMa: Optimal Oblivious RAMJournal of the ACM10.1145/356604970:1(1-70)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3566049
van der Hagen MLucia BFalsafi BFerdman MLu SWenisch T(2022)Client-optimized algorithms and acceleration for encrypted compute offloadingProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507737(683-696)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3503222.3507737
Liu GLi KXiao ZWang RSalapura VZahran MChong FTang L(2022)PS-ORAMProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527425(188-203)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527425
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten