Enhancing Multi-Party Computation Efficiency Through ORAM Techniques

Slide Note

Explore the realm of efficient random access in multi-party computation through the reevaluation of classic schemes and the introduction of new approaches. Discover the potential of ORAM in improving performance and reducing costs in various computational tasks, such as secure multi-party computation applications, linear scans, and access pattern hiding.

jeronimo_a Follow

Uploaded on Sep 12, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Revisiting Square Root ORAM Efficient Random Access in Multi-Party Computation Samee Zahur Jack Doerner David Evans Xiao Wang Jonathan Katz Mariana Raykova Adri Gasc n oblivc.org/sqoram

Secure multi-party computation applications Set intersection [FNP04] Iris code matching [LCPLB12] Matrix factorization for recommendations [NIWJTB13] Median computation [AMP04] Linear ridge-regression [NWIJBT13]

Random Access

Hiding access pattern Linear scan Oblivious RAM Access every element Per-access cost: ? Continually shuffle elements around Per-access cost: (log? ?)

Linear scan Figure from: Wang, Chan, Shi. Circuit Circuit Oram Oram. CCS 15

(our work) 6

Approach: revisit old schemes Classic square root scheme by Goldreich and Ostrovsky (1996). Considered slow for MPC because of per-access hash evaluation. Per-access amortized cost: ?log?

Four-element ORAM Larger Sizes

4-Block ORAM Cost: 5? + ?+2?+3? = 11? every 3 accesses +

Comparison Our scheme Linear scan Cost: 4? = 12?/3 Cost: 11?/3

Four-element ORAM Larger Sizes

Position map 0 1 2 3 0 1 2 3 3 0 2 1 1 3 0 2

Creating position map

Creating position map

Inverse permutation ? ?? ? ??= ?? ? ??

Inverse permutation ?? ?? ??= ?? ? ?? Bob computes ?? 1 ?? 1 1= ? 1 ?? ?? 1 ?? = ? 1 ?? = ? 1

Rinse and repeat 1. Shuffle elements 2. Recreate position map 3. Service ? = ?log? accesses

Access time

Initialization cost

Benchmarks Circuit ORAM Square-root ORAM Task Parameters Linear scan 210 searches 215 elements 1020 s 5041 s 825 s Binary search 210 vertices 213 edges Breadth-first search 4570 s 3750 s 680 s - 189000 s 2850 s 119000 s 1920 s 29 pairs Stable matching 7 days N = 214 scrypt hashing

Conclusion We revisited a well-known scheme and used it to Lower initialization cost Improve breakeven point Shows that asymptotic costs are not the final word, concrete costs require more consideration.