Scaling ORAM for Secure Computation
作者： Jack Doerner , Abhi Shelat
关键词: Secret sharing 、 Overhead (computing) 、 Byte 、 Hash function 、 Computer science 、 Secure multi-party computation 、 Binary search algorithm 、 Data structure 、 Theoretical computer science 、 Initialization 、 Access time 、 Permutation
摘要: We design and implement a Distributed Oblivious Random Access Memory (DORAM) data structure that is optimized for use in two-party secure computation protocols. improve upon the access time of previous constructions by factor up to ten, their memory overhead one hundred or more, initialization thousands. are able instantiate ORAMs hold 234 bytes, perform operations on them seconds, which was not previously feasible with any implemented scheme. Unlike prior ORAM based hierarchical hashing, permutation, trees, our derived from new Function Secret Sharing scheme introduced Boyle, Gilboa Ishai. This significantly reduces amount required an access, albeit at cost O(n) efficient local operations. construction find that, despite its poor asymptotic complexity, it still outperforms fastest known constructions, Circuit Square-root ORAM, datasets 32 KiB larger, work applications such as stable matching binary search factors two ten.
acm.org 
sci-hub.se 参考文章(55)
Niv Gilboa, Yuval Ishai, Distributed Point Functions and their Applications theory and application of cryptographic techniques. pp. 640- 658 ,(2014) , 10.1007/978-3-642-55220-5_35
Eyal Kushilevitz, Rafail Ostrovsky, Steve Lu, On the (in)security of hash-based oblivious RAM and a new balancing scheme symposium on discrete algorithms. pp. 143- 156 ,(2012) , 10.5555/2095116.2095129
Elette Boyle, Niv Gilboa, Yuval Ishai, Function Secret Sharing theory and application of cryptographic techniques. pp. 337- 367 ,(2015) , 10.1007/978-3-662-46803-6_12
Samee Zahur, Mike Rosulek, David Evans, Two Halves Make a Whole theory and application of cryptographic techniques. pp. 220- 250 ,(2015) , 10.1007/978-3-662-46803-6_8
Joan Boyar, René Peralta, A new combinational logic minimization technique with applications to cryptology symposium on experimental and efficient algorithms. ,vol. 6049, pp. 178- 189 ,(2010) , 10.1007/978-3-642-13193-6_16
Benny Pinkas, Thomas Schneider, Nigel P. Smart, Stephen C. Williams, Secure Two-Party Computation Is Practical international conference on the theory and application of cryptology and information security. pp. 250- 267 ,(2009) , 10.1007/978-3-642-10366-7_15
Elaine Shi, T. -H. Hubert Chan, Emil Stefanov, Mingfei Li, Oblivious RAM with o((logn) 3 ) worst-case cost international conference on the theory and application of cryptology and information security. pp. 197- 214 ,(2011) , 10.1007/978-3-642-25385-0_11
Ivan Damgård, Sigurd Meldgaard, Jesper Buus Nielsen, Perfectly secure oblivious RAM without random oracles theory of cryptography conference. ,vol. 6597, pp. 144- 163 ,(2011) , 10.1007/978-3-642-19571-6_10
Olga Ohrimenko, Roberto Tamassia, Michael Mitzenmacher, Michael T. Goodrich, Privacy-preserving group data access via stateless oblivious RAM simulation symposium on discrete algorithms. pp. 157- 167 ,(2012) , 10.5555/2095116.2095130
Joan Boyar, René Peralta, A Small Depth-16 Circuit for the AES S-Box information security conference. ,vol. 376, pp. 287- 298 ,(2012) , 10.1007/978-3-642-30436-1_24