University:
Boston University
Course:
CAS CS 501 | Computer Science Practicum
Academic year:

2024
Views:

215

Pages:

19
Author:

Raiden Hutchinson

Outline • Introduction to tree-based ORAMs • Optimizing recursive ORAM • Ring ORAM • Hardware ORAM 20 Improve Eviction Quality • Path ORAM: 8log𝑁 evict to the [random] path being read • Load balance between paths • Allow less frequent evictions (1 per A accesses) – Z=4, A=3 Reverse lexicographic order – Z=5, A=5 – Z=7, A=8 1 0 𝑍=4 00 10 01 11 Craig Gentry, Kenny Goldman, Shai Halevi, Charanjit Julta, Mariana Raykova and Daniel Wichs. Optimizing ORAM and Using it Efficiently for Secure Computation 21 Permuted buckets • Goal: read only 1 block per bucket – Add Y reserved dummy slots, and permute buckets – Block of interest or a fresh dummy – Re-permute if out of fresh dummies 𝑍=4 𝑌>𝐴 22 Ring ORAM Performance • Eviction overhead (Z + Z + Y) / A per bucket Scheme and Parameters Read Eviction Total Path ORAM 𝑍 = 4 4𝐿 4𝐿 8𝐿 Ring ORAM 𝑍=16,𝐴=22,𝑌=28 𝑳 𝟐.𝟖𝑳 𝟑.𝟖𝑳 Ring ORAM 𝑍=5, 𝐴=5,𝑌=7 𝑳 𝟑.𝟖𝑳 𝟒.𝟖𝑳 3.8x ! 1.8x 23 Outline • Introduction to tree-based ORAMs • Optimizing recursive ORAM • Ring ORAM • Hardware ORAM 24 Hardware ORAM • Things we take for granted in ORAM algorithms – Computation is cheap (e.g. ORAM eviction, hashing) – RAM has uniform latency 25 Stash Management • Computation is cheap? 26 ORAM Authenticity • Just use hash tree? – A serialization problem. Hashing becomes the bottleneck Hash 0 Hash 1 Hash Tree Hash 3 Hash 2 Hash 4 Hash 5 Hash 6 Bucket 0 ORAM Tree Bucket 1 Bucket 3 Bucket 4 Bucket 2 Bucket 5 Bucket 6 27 PMMAC for Authenticity • Construction – Block à monotonic counter – MAC(Block address || counter || block data) • Problem: privacy under malicious server – Is it fixable? Bounding the leakage? 28 DRAM Timing • An access to a new row is slow • Very bad for trees • Solution: subtree layout GIF from http://www.pcmag.com/article2/0,2817,1153175,00.asp 29 Our Hardware ORAM • Techniques we have implemented – PLB + Unified ORAM tree – Load balance eviction order (1/A eviction frequency) – Efficient stash management – PMMAC – Subtree layout • Techniques we have not implemented – Compressed counter, permuted buckets 30 FPGA Die Photo • Area: 6% logic, 14% memory of a mid-range FPGA • Performance: 250 cycles (200 MHz clock) = 1.25 us 31 Take-aways • Recursion accounts for about 50% overhead; PLB (+ Compression) makes it almost free • Ring ORAM achieves another 2x improvement • Design challenges in hardware ORAM: computation, hashing, DRAM locality 32 Backup What block size? • Data block size 𝐵↓𝑑 𝛽=loglog𝑁, 𝑘=log𝑁/loglog𝑁 , 𝛼=𝛳(log𝑁) • PosMap block size 𝐵↓𝑝 =𝛼+𝑘𝛽=𝛳(log𝑁) • Will use 𝐵↓𝑝 (using 𝐵↓𝑑 is suboptimal) – Break a data block into ⌈𝐵↓𝑑 /𝐵↓𝑝 ⌉ sub-blocks of size 𝐵↓𝑝 – Treat them as separate blocks in backend, with position being – 𝑃𝑅𝐹↓𝐾 (𝐺𝐶 | 𝐼𝐶↓𝑗 | 𝑗 | 𝑡) where 𝑡 is sub-block index • (⌈𝐵↓𝑑 /𝐵↓𝑝 ⌉+log𝑁/log𝑘 )𝑂(log↑2 𝑁)1/𝐵↓𝑑 =𝑂(log𝑁+ log↑𝟑 𝑁/𝐵↓𝑑 loglog𝑁 ) – 𝑁 à 𝑁⌈𝐵↓𝑑 /𝐵↓𝑝 ⌉ 34 Theoretical Construction 𝐺𝐶, 𝐼𝐶↓0 ,𝐼𝐶↓1 ,⋯, 𝐼𝐶↓𝑘−1 • 𝛽=loglog𝑁, 𝑘=log𝑁/loglog𝑁 , 𝛼=𝛳(log𝑁)𝛼 bits 𝛽 bits • 𝑘/2↑𝛽 =𝑜(1), 𝛼/𝑘 +𝛽=loglog𝑁