{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T18:40:23Z","timestamp":1741632023506,"version":"3.38.0"},"reference-count":53,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCS"],"published-print":{"date-parts":[[2022,1,20]]},"abstract":"<jats:p>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\u2013458) and improve it in two orthogonal aspects: match it directly with tree-based ORAMs and explore its consistency with gradual ORAM.<\/jats:p>","DOI":"10.3233\/jcs-200107","type":"journal-article","created":{"date-parts":[[2021,10,29]],"date-time":"2021-10-29T15:44:28Z","timestamp":1635522268000},"page":"197-229","source":"Crossref","is-referenced-by-count":0,"title":["Gradual GRAM and secure computation for RAM programs1"],"prefix":"10.1177","volume":"30","author":[{"given":"Carmit","family":"Hazay","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel. E-mails:\u00a0carmit.hazay@biu.ac.il,\u00a0mor.tzoomi@gmail.com"}]},{"given":"Mor","family":"Lilintal","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel. E-mails:\u00a0carmit.hazay@biu.ac.il,\u00a0mor.tzoomi@gmail.com"}]}],"member":"179","reference":[{"key":"10.3233\/JCS-200107_ref1","doi-asserted-by":"crossref","unstructured":"A. Afshar, Z. Hu, P. Mohassel and M. Rosulek, How to efficiently evaluate RAM programs with malicious security, in: EUROCRYPT, 2015, pp. 702\u2013729.","DOI":"10.1007\/978-3-662-46800-5_27"},{"key":"10.3233\/JCS-200107_ref2","doi-asserted-by":"crossref","unstructured":"D. Beaver, S. Micali and P. Rogaway, The round complexity of secure protocols (extended abstract), in: STOC, 1990, pp. 503\u2013513.","DOI":"10.1145\/100216.100287"},{"key":"10.3233\/JCS-200107_ref3","doi-asserted-by":"crossref","unstructured":"M. Bellare, V. Tung Hoang and P. Rogaway, Foundations of garbled circuits, in: CCS, 2012, pp. 784\u2013796.","DOI":"10.1145\/2382196.2382279"},{"key":"10.3233\/JCS-200107_ref4","doi-asserted-by":"crossref","unstructured":"J. Buus Nielsen, P. Sebastian Nordholt, C. Orlandi and S.S. Burra, A new approach to practical active-secure two-party computation, in: CRYPTO, 2012, pp. 681\u2013700.","DOI":"10.1007\/978-3-642-32009-5_40"},{"key":"10.3233\/JCS-200107_ref5","unstructured":"K. Chung and R. Pass, A simple ORAM, IACR Cryptology ePrint Archive 2013 (2013), 243."},{"key":"10.3233\/JCS-200107_ref6","doi-asserted-by":"crossref","unstructured":"S.A. Cook and R.A. Reckhow, Time-bounded random access machines, in: STOC, 1972, pp. 73\u201380.","DOI":"10.1145\/800152.804898"},{"key":"10.3233\/JCS-200107_ref7","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, M. Keller, E. Larraia, V. Pastro, P. Scholl and N.P. Smart, Practical covertly secure MPC for dishonest majority \u2013 or: Breaking the SPDZ limits, in: ESORICS, 2013, pp. 1\u201318.","DOI":"10.1007\/978-3-642-40203-6_1"},{"key":"10.3233\/JCS-200107_ref8","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, S. Meldgaard and J.B. Nielsen, Perfectly secure oblivious RAM without random oracles, in: TCC, 2011, pp. 144\u2013163.","DOI":"10.1007\/978-3-642-19571-6_10"},{"key":"10.3233\/JCS-200107_ref9","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, V. Pastro, N.P. Smart and S. Zakarias, Multiparty computation from somewhat homomorphic encryption, in: CRYPTO, 2012, pp. 643\u2013662.","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"10.3233\/JCS-200107_ref10","doi-asserted-by":"crossref","unstructured":"J. Doerner and A. Shelat, Scaling ORAM for secure computation, in: CCS, 2017, pp. 523\u2013535.","DOI":"10.1145\/3133956.3133967"},{"key":"10.3233\/JCS-200107_ref11","doi-asserted-by":"crossref","unstructured":"S. Garg, D. Gupta, P. Miao and O. Pandey, Secure multiparty RAM computation in constant rounds, in: TCC, 2016, pp. 491\u2013520.","DOI":"10.1007\/978-3-662-53641-4_19"},{"key":"10.3233\/JCS-200107_ref12","doi-asserted-by":"crossref","unstructured":"S. Garg, S. Lu and R. Ostrovsky, Black-box garbled RAM, in: FOCS, 2015, pp. 210\u2013229.","DOI":"10.1109\/FOCS.2015.22"},{"key":"10.3233\/JCS-200107_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746593"},{"key":"10.3233\/JCS-200107_ref14","doi-asserted-by":"crossref","unstructured":"C. Gentry, K.A. Goldman, S. Halevi, C.S. Jutla, M. Raykova and D. Wichs, Optimizing ORAM and using it efficiently for secure computation, in: PETS, 2013, pp. 1\u201318.","DOI":"10.1007\/978-3-642-39077-7_1"},{"key":"10.3233\/JCS-200107_ref15","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Halevi, S. Lu, R. Ostrovsky, M. Raykova and D. Wichs, Garbled RAM revisited, in: EUROCRYPT, 2014, pp. 405\u2013422.","DOI":"10.1007\/978-3-642-55220-5_23"},{"key":"10.3233\/JCS-200107_ref16","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Towards a theory of software protection and simulation by oblivious rams, in: STOC, 1987, pp. 182\u2013194.","DOI":"10.1145\/28395.28416"},{"issue":"3","key":"10.3233\/JCS-200107_ref17","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","article-title":"Software protection and simulation on oblivious rams","volume":"43","author":"Goldreich","year":"1996","journal-title":"J. ACM"},{"key":"10.3233\/JCS-200107_ref18","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, M. Mitzenmacher, O. Ohrimenko and R. Tamassia, Privacy-preserving group data access via stateless oblivious RAM simulation, in: SODA, 2012, pp. 157\u2013167.","DOI":"10.1137\/1.9781611973099.14"},{"key":"10.3233\/JCS-200107_ref19","doi-asserted-by":"crossref","unstructured":"S.D. Gordon, J. Katz, V. Kolesnikov, F. Krell, T. Malkin, M. Raykova and Y. Vahlis, Secure two-party computation in sublinear (amortized) time, in: CCS, 2012, pp. 513\u2013524.","DOI":"10.1145\/2382196.2382251"},{"key":"10.3233\/JCS-200107_ref20","doi-asserted-by":"crossref","unstructured":"S. Gueron, Y. Lindell, A. Nof and B. Pinkas, Fast garbling of circuits under standard assumptions, in: CCS, 2015, pp. 567\u2013578.","DOI":"10.1145\/2810103.2813619"},{"key":"10.3233\/JCS-200107_ref21","doi-asserted-by":"crossref","unstructured":"C. Hazay, Y. Ishai and M. Venkitasubramaniam, Actively secure garbled circuits with constant communication overhead in the plain model, in: TCC, 2017, pp. 3\u201339.","DOI":"10.1007\/978-3-319-70503-3_1"},{"key":"10.3233\/JCS-200107_ref22","doi-asserted-by":"crossref","unstructured":"C. Hazay and M. Lilintal, Gradual GRAM and secure computation for RAM programs, in: SCN, 2020, pp. 233\u2013252.","DOI":"10.1007\/978-3-030-57990-6_12"},{"key":"10.3233\/JCS-200107_ref23","doi-asserted-by":"crossref","unstructured":"C. Hazay, P. Scholl and E. Soria-Vazquez, Low cost constant round MPC combining BMR and oblivious transfer, in: ASIACRYPT, 2017, pp. 598\u2013628.","DOI":"10.1007\/978-3-319-70694-8_21"},{"key":"10.3233\/JCS-200107_ref24","doi-asserted-by":"crossref","unstructured":"C. Hazay and A. Yanai, Constant-round maliciously secure two-party computation in the RAM model, in: TCC, 2016, pp. 521\u2013553.","DOI":"10.1007\/978-3-662-53641-4_20"},{"key":"10.3233\/JCS-200107_ref25","doi-asserted-by":"crossref","unstructured":"Y. Huang, J. Katz, V. Kolesnikov, R. Kumaresan and A.J. Malozemoff, Amortizing garbled circuits, in: CRYPTO, 2014, pp. 458\u2013475.","DOI":"10.1007\/978-3-662-44381-1_26"},{"key":"10.3233\/JCS-200107_ref26","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, M. Prabhakaran and A. Sahai, Efficient non-interactive secure computation, in: EUROCRYPT, 2011, pp. 406\u2013425.","DOI":"10.1007\/978-3-642-20465-4_23"},{"key":"10.3233\/JCS-200107_ref27","doi-asserted-by":"crossref","unstructured":"M. Keller and P. Scholl, Efficient, oblivious data structures for MPC, in: ASIACRYPT, 2014, pp. 506\u2013525.","DOI":"10.1007\/978-3-662-45608-8_27"},{"key":"10.3233\/JCS-200107_ref28","doi-asserted-by":"crossref","unstructured":"M. Keller and A. Yanai, Efficient maliciously secure multiparty computation for RAM, in: EUROCRYPT, 2018, pp. 91\u2013124.","DOI":"10.1007\/978-3-319-78372-7_4"},{"key":"10.3233\/JCS-200107_ref29","doi-asserted-by":"crossref","unstructured":"V. Kolesnikov and T. Schneider, Improved garbled circuit: Free XOR gates and applications, in: ICALP, 2008, pp. 486\u2013498.","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"10.3233\/JCS-200107_ref30","doi-asserted-by":"crossref","unstructured":"Y. Lindell and B. Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in: EUROCRYPT, 2007, pp. 52\u201378.","DOI":"10.1007\/978-3-540-72540-4_4"},{"key":"10.3233\/JCS-200107_ref31","doi-asserted-by":"crossref","unstructured":"Y. Lindell, B. Pinkas, N.P. Smart and A. Yanai, Efficient constant round multi-party computation combining BMR and SPDZ, in: CRYPTO, 2015, pp. 319\u2013338.","DOI":"10.1007\/978-3-662-48000-7_16"},{"key":"10.3233\/JCS-200107_ref32","doi-asserted-by":"crossref","unstructured":"C. Liu, Y. Huang, E. Shi, J. Katz and M.W. Hicks, Automating efficient ram-model secure computation, in: IEEE Symposium on Security and Privacy, 2014, pp. 623\u2013638.","DOI":"10.1109\/SP.2014.46"},{"key":"10.3233\/JCS-200107_ref33","doi-asserted-by":"crossref","unstructured":"S. Lu and R. Ostrovsky, How to garble RAM programs, in: EUROCRYPT, 2013, pp. 719\u2013734.","DOI":"10.1007\/978-3-642-38348-9_42"},{"key":"10.3233\/JCS-200107_ref34","unstructured":"P. Miao, Cut-and-choose for garbled RAM, IACR Cryptology ePrint Archive 2016 (2016), 907."},{"key":"10.3233\/JCS-200107_ref35","doi-asserted-by":"crossref","unstructured":"T. Moataz, T. Mayberry, E. Blass and A. Hui Chan, Resizable tree-based oblivious RAM, in: FC, 2015, pp. 147\u2013167.","DOI":"10.1007\/978-3-662-47854-7_9"},{"key":"10.3233\/JCS-200107_ref36","doi-asserted-by":"crossref","unstructured":"P. Mohassel and M. Rosulek, Non-interactive secure 2pc in the offline\/online and batch settings, in: EUROCRYPT, 2017, pp. 425\u2013455.","DOI":"10.1007\/978-3-319-56617-7_15"},{"key":"10.3233\/JCS-200107_ref37","doi-asserted-by":"crossref","unstructured":"J.B. Nielsen and C. Orlandi, Lego for two-party secure computation, in: TCC, 2009, pp. 368\u2013386.","DOI":"10.1007\/978-3-642-00457-5_22"},{"key":"10.3233\/JCS-200107_ref38","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, Efficient computation on oblivious rams, in: STOC, 1990, pp. 514\u2013523.","DOI":"10.1145\/100216.100289"},{"issue":"2","key":"10.3233\/JCS-200107_ref39","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations among complexity measures","volume":"26","author":"Pippenger","year":"1979","journal-title":"J. ACM"},{"key":"10.3233\/JCS-200107_ref40","unstructured":"L. Ren, C.W. Fletcher, A. Kwon, E. Stefanov, E. Shi, M. van Dijk and S. Devadas, Constants count: Practical improvements to oblivious RAM, in: USENIX, 2015, pp. 415\u2013430."},{"key":"10.3233\/JCS-200107_ref41","unstructured":"P. Rindal and M. Rosulek, Faster malicious 2-party secure computation with online\/offline dual execution, in: USENIX, 2016, pp. 297\u2013314."},{"key":"10.3233\/JCS-200107_ref42","doi-asserted-by":"crossref","unstructured":"B. Schoenmakers and P. Tuyls, Practical two-party computation based on the conditional gate, in: ASIACRYPT, 2004, pp. 119\u2013136.","DOI":"10.1007\/978-3-540-30539-2_10"},{"key":"10.3233\/JCS-200107_ref43","doi-asserted-by":"crossref","unstructured":"E. Shi, T.-H. Hubert Chan, E. Stefanov and M. Li, Oblivious RAM with o((logn)3) worst-case cost, in: ASIACRYPT, 2011, pp. 197\u2013214.","DOI":"10.1007\/978-3-642-25385-0_11"},{"issue":"4","key":"10.3233\/JCS-200107_ref44","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/3177872","article-title":"Path ORAM: an extremely simple oblivious RAM protocol","volume":"65","author":"Stefanov","year":"2018","journal-title":"J. ACM"},{"key":"10.3233\/JCS-200107_ref45","doi-asserted-by":"crossref","unstructured":"X. Wang, T.-H.H. Chan and E. Shi, Circuit ORAM: on tightness of the Goldreich\u2013Ostrovsky lower bound, in: CCS, 2015, pp. 850\u2013861.","DOI":"10.1145\/2810103.2813634"},{"key":"10.3233\/JCS-200107_ref46","doi-asserted-by":"crossref","unstructured":"X. Wang, A.J. Malozemoff and J. Katz, Faster secure two-party computation in the single-execution setting, in: EUROCRYPT, 2017, pp. 399\u2013424.","DOI":"10.1007\/978-3-319-56617-7_14"},{"key":"10.3233\/JCS-200107_ref47","doi-asserted-by":"crossref","unstructured":"X. Wang, S. Ranellucci and J. Katz, Authenticated garbling and efficient maliciously secure two-party computation, in: CCS, 2017, pp. 21\u201337.","DOI":"10.1145\/3133956.3134053"},{"key":"10.3233\/JCS-200107_ref48","doi-asserted-by":"crossref","unstructured":"X. Wang, S. Ranellucci and J. Katz, Global-scale secure multiparty computation, in: CCS, 2017, pp. 39\u201356.","DOI":"10.1145\/3133956.3133979"},{"key":"10.3233\/JCS-200107_ref49","doi-asserted-by":"crossref","unstructured":"X.S. Wang, Y. Huang, T.-H. Hubert Chan, A. Shelat and E. Shi, SCORAM: oblivious RAM for secure computation, in: CCS, 2014, pp. 191\u2013202.","DOI":"10.1145\/2660267.2660365"},{"key":"10.3233\/JCS-200107_ref50","doi-asserted-by":"crossref","unstructured":"X.S. Wang, K. Nayak, C. Liu, T.-H. Hubert Chan, E. Shi, E. Stefanov and Y. Huang, Oblivious data structures, in: CCS, 2014, pp. 215\u2013226.","DOI":"10.1145\/2660267.2660314"},{"key":"10.3233\/JCS-200107_ref51","doi-asserted-by":"crossref","unstructured":"P. Williams and R. Sion, Single round access privacy on outsourced storage, in: CCS, 2012, pp. 293\u2013304.","DOI":"10.1145\/2382196.2382229"},{"key":"10.3233\/JCS-200107_ref52","doi-asserted-by":"crossref","unstructured":"A.C. Yao, How to generate and exchange secrets (extended abstract), in: FOCS, 1986, pp. 162\u2013167.","DOI":"10.1109\/SFCS.1986.25"},{"key":"10.3233\/JCS-200107_ref53","doi-asserted-by":"crossref","unstructured":"S. Zahur, M. Rosulek and D. Evans, Two halves make a whole \u2013 reducing data transfer in garbled circuits using half gates, in: EUROCRYPT, 2015, pp. 220\u2013250.","DOI":"10.1007\/978-3-662-46803-6_8"}],"container-title":["Journal of Computer Security"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JCS-200107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T17:41:55Z","timestamp":1741628515000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/JCS-200107"}},"subtitle":[],"editor":[{"given":"Clemente","family":"Galdi","sequence":"additional","affiliation":[]},{"given":"Vladimir","family":"Kolesnikov","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":53,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/jcs-200107","relation":{},"ISSN":["1875-8924","0926-227X"],"issn-type":[{"type":"electronic","value":"1875-8924"},{"type":"print","value":"0926-227X"}],"subject":[],"published":{"date-parts":[[2022,1,20]]}}}