Efficient Maliciously Secure Multiparty Computation for RAM

被引:20
作者
Keller, Marcel [1 ]
Yanai, Avishay [2 ]
机构
[1] Univ Bristol, Bristol, Avon, England
[2] Bar Ilan Univ, Ramat Gan, Israel
来源
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2018, PT III | 2018年 / 10822卷
基金
英国工程与自然科学研究理事会; 欧洲研究理事会;
关键词
BMR;
D O I
10.1007/978-3-319-78372-7_4
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa. In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit -based actively secure RAM computation with dishonest majority. Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgard et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM's, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM's storage size. Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).
引用
收藏
页码:91 / 124
页数:34
相关论文
共 41 条
  • [1] How to Efficiently Evaluate RAM Programs with Malicious Security
    Afshar, Arash
    Hu, Zhangxiang
    Mohassel, Payman
    Rosulek, Mike
    [J]. ADVANCES IN CRYPTOLOGY - EUROCRYPT 2015, PT I, 2015, 9056 : 702 - 729
  • [2] [Anonymous], 2004, FDN CRYPTOGRAPHY BAS
  • [3] [Anonymous], 1987, P 19 ANN ACM S THEOR, DOI DOI 10.1145/28395.28420
  • [4] Ben-Efraim Aner, 2017, Advances in Cryptology - ASIACRYPT 2017. 23rd International Conference on the Theory and Applications of Cryptology and Information Security. Proceedings: LNCS 10625, P471, DOI 10.1007/978-3-319-70697-9_17
  • [5] Ben-Efraim A., 2016, OPTIMIZING SEMIHONES, P578
  • [6] Function Secret Sharing: Improvements and Extensions
    Boyle, Elette
    Gilboa, Niv
    Ishai, Yuval
    [J]. CCS'16: PROCEEDINGS OF THE 2016 ACM SIGSAC CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, 2016, : 1292 - 1303
  • [7] Function Secret Sharing
    Boyle, Elette
    Gilboa, Niv
    Ishai, Yuval
    [J]. ADVANCES IN CRYPTOLOGY - EUROCRYPT 2015, PT II, 2015, 9057 : 337 - 367
  • [8] Fully Succinct Garbled RAM
    Canetti, Ran
    Holmgren, Justin
    [J]. ITCS'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON INNOVATIONS IN THEORETICAL COMPUTER SCIENCE, 2016, : 169 - 178
  • [9] Damgård I, 2012, LECT NOTES COMPUT SC, V7417, P643
  • [10] DOERNER J., 2017, CCS