Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM
Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. Recently, ORAM has been architected into secure processors. A big challenge for hardware ORAM schemes is how to efficiently manage the Position Map (PosMap), a central component in moder...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121405 |
| _version_ | 1811081854086807552 |
|---|---|
| author | Fletcher, Christopher Wardlaw Ren, Ling Kwon, Albert van Dijk, Marten Devadas, Srinivas |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Fletcher, Christopher Wardlaw Ren, Ling Kwon, Albert van Dijk, Marten Devadas, Srinivas |
| author_sort | Fletcher, Christopher Wardlaw |
| collection | MIT |
| description | Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. Recently, ORAM has been architected into secure processors. A big challenge for hardware ORAM schemes is how to efficiently manage the Position Map (PosMap), a central component in modern ORAM algorithms. Implemented naively, the PosMap causes ORAM to be fundamentally unscalable in terms of on-chip area. On the other hand, a technique called Recursive ORAM fixes the area problem yet significantly increases ORAM's performance overhead.
To address this challenge, we propose three new mechanisms. We propose a new ORAM structure called the PosMap Lookaside Buffer (PLB) and PosMap compression techniques to reduce the performance overhead from Recursive ORAM empirically (the latter also improves the construction asymptotically). Through simulation, we show that these techniques reduce the memory bandwidth overhead needed to support recursion by 95%, reduce overall ORAM bandwidth by 37% and improve overall SPEC benchmark performance by 1.27x. We then show how our PosMap compression techniques further facilitate an extremely efficient integrity verification scheme for ORAM which we call PosMap MAC (PMMAC). For a practical parameterization, PMMAC reduces the amount of hashing needed for integrity checking by >= 68x relative to prior schemes and introduces only 7% performance overhead.
We prototype our mechanisms in hardware and report area and clock frequency for a complete ORAM design post-synthesis and post-layout using an ASIC flow in a 32~nm commercial process. With 2 DRAM channels, the design post-layout runs at 1~GHz and has a total area of .47~mm2. Depending on PLB-specific parameters, the PLB accounts for 10% to 26% area. PMMAC costs 12% of total design area. Our work is the first to prototype Recursive ORAM or ORAM with any integrity scheme in hardware. |
| first_indexed | 2024-09-23T11:53:31Z |
| format | Article |
| id | mit-1721.1/121405 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:53:31Z |
| publishDate | 2019 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1214052022-10-01T06:45:42Z Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM Fletcher, Christopher Wardlaw Ren, Ling Kwon, Albert van Dijk, Marten Devadas, Srinivas Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. Recently, ORAM has been architected into secure processors. A big challenge for hardware ORAM schemes is how to efficiently manage the Position Map (PosMap), a central component in modern ORAM algorithms. Implemented naively, the PosMap causes ORAM to be fundamentally unscalable in terms of on-chip area. On the other hand, a technique called Recursive ORAM fixes the area problem yet significantly increases ORAM's performance overhead. To address this challenge, we propose three new mechanisms. We propose a new ORAM structure called the PosMap Lookaside Buffer (PLB) and PosMap compression techniques to reduce the performance overhead from Recursive ORAM empirically (the latter also improves the construction asymptotically). Through simulation, we show that these techniques reduce the memory bandwidth overhead needed to support recursion by 95%, reduce overall ORAM bandwidth by 37% and improve overall SPEC benchmark performance by 1.27x. We then show how our PosMap compression techniques further facilitate an extremely efficient integrity verification scheme for ORAM which we call PosMap MAC (PMMAC). For a practical parameterization, PMMAC reduces the amount of hashing needed for integrity checking by >= 68x relative to prior schemes and introduces only 7% performance overhead. We prototype our mechanisms in hardware and report area and clock frequency for a complete ORAM design post-synthesis and post-layout using an ASIC flow in a 32~nm commercial process. With 2 DRAM channels, the design post-layout runs at 1~GHz and has a total area of .47~mm2. Depending on PLB-specific parameters, the PLB accounts for 10% to 26% area. PMMAC costs 12% of total design area. Our work is the first to prototype Recursive ORAM or ORAM with any integrity scheme in hardware. National Science Foundation (U.S.) American Society for Engineering Education. National Defense Science and Engineering Graduate Fellowship 2019-06-25T16:56:38Z 2019-06-25T16:56:38Z 2015-03 2019-05-28T16:04:47Z Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-2835-7 https://hdl.handle.net/1721.1/121405 Fletcher, Christopher W. "Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM." Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, 14-18 March, 2015, Istanbul, Turkey, ACM, 2015. en http://dx.doi.org/10.1145/2775054.2694353 Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Fletcher, Christopher Wardlaw Ren, Ling Kwon, Albert van Dijk, Marten Devadas, Srinivas Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title | Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title_full | Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title_fullStr | Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title_full_unstemmed | Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title_short | Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM |
| title_sort | freecursive oram nearly free recursion and integrity verification for position based oblivious ram |
| url | https://hdl.handle.net/1721.1/121405 |
| work_keys_str_mv | AT fletcherchristopherwardlaw freecursiveoramnearlyfreerecursionandintegrityverificationforpositionbasedobliviousram AT renling freecursiveoramnearlyfreerecursionandintegrityverificationforpositionbasedobliviousram AT kwonalbert freecursiveoramnearlyfreerecursionandintegrityverificationforpositionbasedobliviousram AT vandijkmarten freecursiveoramnearlyfreerecursionandintegrityverificationforpositionbasedobliviousram AT devadassrinivas freecursiveoramnearlyfreerecursionandintegrityverificationforpositionbasedobliviousram |