Paper 2016/805

Constant-Round Maliciously Secure Two-Party Computation in the RAM Model

Carmit Hazay and Avishay Yanai


The random-access memory (RAM) model of computation allows program constant-time memory lookup and is more applicable in practice today, covering many important algorithms. This is in contrast to the classic setting of secure 2-party computation (2PC) that mostly follows the approach for which the desired functionality must be represented as a boolean circuit. In this work we design the first constant round maliciously secure two-party protocol in the RAM model. Our starting point is the garbled RAM construction of Gentry et al. (EUROCRYPT 2014) that readily induces a constant round semi-honest two-party protocol for any RAM program assuming identity-based encryption schemes. We show how to enhance the security of their construction into the malicious setting while facing several challenges that stem due to handling the data memory. Next, we show how to apply our techniques to a more recent garbled RAM construction by Garg et al. (STOC 2015) that is based on one-way functions.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2016
Contact author(s)
ay yanay @ gmail com
2019-04-03: last of 2 revisions
2016-08-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carmit Hazay and Avishay Yanai},
      title = {Constant-Round Maliciously Secure Two-Party Computation in the RAM Model},
      howpublished = {Cryptology ePrint Archive, Paper 2016/805},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.