Gradual GRAM and secure computation for RAM programs¹

Issue title: Selected papers from the 12th Conference on Security and Cryptography for Networks

Guest editors: Clemente Galdi and Vladimir Kolesnikov

Article type: Research Article

Authors: Hazay, Carmit^{; *} | Lilintal, Mor

Affiliations: Bar-Ilan University, Ramat-Gan, Israel. E-mails: carmit.hazay@biu.ac.il, mor.tzoomi@gmail.com

Correspondence: [*] Corresponding author. E-mail: carmit.hazay@biu.ac.il.

Note: [1] This paper is an extended and revised version of a paper presented at the 12th Conference on Security and Cryptography for Networks.

Abstract: Despite the fact that the majority of applications encountered in practice today are captured more efficiently by RAM programs, the area of secure two-party computation (2PC) has seen tremendous improvement mostly for Boolean circuits. One of the most studied objects in this domain is garbled circuits. Analogously, garbled RAM (GRAM) provide similar security guarantees for RAM programs with applications to constant round 2PC. In this work we consider the notion of gradual GRAM which requires no memory garbling algorithm. Our approach provides several qualitative advantages over prior works due to the conceptual similarity to the analogue garbling mechanism for Boolean circuits. We next revisit the GRAM construction from (In STOC (2015) 449–458) and improve it in two orthogonal aspects: match it directly with tree-based ORAMs and explore its consistency with gradual ORAM.

Keywords: Secure computation, garbled RAM, ORAM

DOI: 10.3233/JCS-200107

Journal: Journal of Computer Security, vol. 30, no. 1, pp. 197-229, 2022