{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:33Z","timestamp":1787340633233,"version":"build-2736575974"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100021796","name":"Check Point Institute for Information Security","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021796","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006919","name":"Massachusetts Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006919","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100002252","name":"NEC Foundation of America","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002252","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1350619"],"award-info":[{"award-number":["CNS-1350619"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1414119"],"award-info":[{"award-number":["CNS-1414119"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218461"],"award-info":[{"award-number":["1218461"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1514526"],"award-info":[{"award-number":["CNS-1514526"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0746990"],"award-info":[{"award-number":["CCF-0746990"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1214844"],"award-info":[{"award-number":["CCF-1214844"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We show how to construct indistinguishability obfuscation (\\bf iO) for RAM programs with bounded space, assuming \\bf iO for circuits and one-way functions, both with subexponential security. That is, given a RAM program whose computation requires space $s(n)$ in the worst case for inputs of length at most $n$, we generate an obfuscated RAM program that, for inputs of size at most $n$, runs in roughly the same time as the original program, using space roughly $s(n)$. The obfuscation process is quasi-linear in the description length of the input program and $s(n)$. At the heart of our construction are succinct randomized encodings for RAM programs. We present two very different constructions of such encodings, each with its own unique properties. Beyond their use as a tool in obfuscation for RAM programs, we show that succinct randomized encodings are interesting objects in their own right. We demonstrate the power of succinct randomized encodings in applications such as publicly verifiable delegation, functional encryption for RAMs, and key-dependent security amplification.<\/jats:p>","DOI":"10.1137\/15m1050963","type":"journal-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T15:57:32Z","timestamp":1530115052000},"page":"1123-1210","source":"Crossref","is-referenced-by-count":22,"title":["Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings"],"prefix":"10.1137","volume":"47","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Canetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjam","family":"Garg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Justin","family":"Holmgren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Jain","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sidharth","family":"Telang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_1"},{"key":"atypb2","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      Cryptography in NC$^0$\n                      , in 45th Annual Symposium on Foundations of Computer Science (Rome, Italy, 2004), IEEE Computer Society Press, 2004, pp. 166-175."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0211-8"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      From secrecy to soundness: Efficient verification via secure computation\n                      , in ICALP 2010: 37th International Colloquium on Automata, Languages and Programming, Part I (Bordeaux, France, 2010), Lecture Notes in Comput. Sci. 6198, S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, eds., Springer, 2010, pp. 152-163.","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, and E. Kushilevitz,\n                      How to garble arithmetic circuits\n                      , in 52nd Annual Symposium on Foundations of Computer Science (Palm Springs, CA, 2011), R. Ostrovsky, ed., IEEE Computer Society Press, 2011, pp. 120-129.","DOI":"10.1109\/FOCS.2011.40"},{"key":"atypb6","first-page":"483","author":"Asharov G.","year":"2012","journal-title":"Springer"},{"key":"atypb7","unstructured":"P. Ananth, A. Jain, and A. Sahai,\n                      Indistinguishability Obfuscation with Constant Size Overhead\n                      , IACR Cryptology ePrint Archive, 2015:1023, 2015."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63715-0_9"},{"key":"atypb9","first-page":"527","author":"Applebaum B.","year":"2011","journal-title":"Springer"},{"key":"atypb10","first-page":"25","author":"Applebaum B.","year":"2011","journal-title":"The Netherlands)"},{"key":"atypb11","first-page":"162","author":"Applebaum B.","year":"2014","journal-title":"R.O.C.)"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer,\n                      From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again\n                      , in ITCS 2012: 3rd Innovations in Theoretical Computer Science (Cambridge, MA, 2012), S. Goldwasser, ed., Association for Computing Machinery, 2012, pp. 326-349.","DOI":"10.1145\/2090236.2090263"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer,\n                      Recursive composition and bootstrapping for SNARKS and proof-carrying data\n                      , in 45th Annual ACM Symposium on Theory of Computing (Palo Alto, CA, 2013), D. Boneh, T. Roughgarden, and J. Feigenbaum, eds., ACM Press, 2013, pp. 111-120.","DOI":"10.1145\/2488608.2488623"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-016-9241-9"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"E. Boyle, K.M. Chung, and R. Pass,\n                      On extractability obfuscation\n                      , in TCC 2014: 11th Theory of Cryptography Conference (San Diego, CA, 2014), Lecture Notes in Comput. Sci. 8349, Y. Lindell, ed., Springer, 2014, pp. 52-73.","DOI":"10.1007\/978-3-642-54242-8_3"},{"key":"atypb16","first-page":"1","volume":"2001","author":"Barak B.","year":"2001","journal-title":"Advances in Cryptology CRYPTO"},{"key":"atypb17","first-page":"501","author":"Boyle E.","year":"2014","journal-title":"PKC"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"N. Bitansky, S. Garg, H. Lin, R. Pass, and S. Telang,\n                      Succinct randomized encodings and their applications\n                      , in Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015 (Portland, OR), ACM, 2015, pp. 439-448.","DOI":"10.1145\/2746539.2746574"},{"key":"atypb19","first-page":"423","author":"Barak B.","year":"2010","journal-title":"Springer"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"M. Bellare, V. T. Hoang, and S. Keelveedhi,\n                      Instantiating random oracles via UCEs\n                      , in Advances in Cryptology - CRYPTO 2013, Part II (Santa Barbara, CA, 2013), Lecture Notes in Comput. Sci. 8043, R. Canetti and J. A. Garay, eds., Springer, pp. 398-415.","DOI":"10.1007\/978-3-642-40084-1_23"},{"key":"atypb21","first-page":"134","author":"Bellare M.","year":"2012","journal-title":"Springer"},{"key":"atypb22","first-page":"784","author":"Bellare M.","year":"2012","journal-title":"NC)"},{"key":"atypb23","first-page":"410","author":"Boneh D.","year":"2013","journal-title":"Springer"},{"key":"atypb24","first-page":"280","author":"Boneh D.","year":"2013","journal-title":"ASIACRYPT (2)"},{"key":"atypb25","unstructured":"Y.C. Chen, S. S. M. Chow, K.M. Chung, R. W. F. Lai, W.K. Lin, and H.S. Zhou,\n                      Cryptography for Parallel RAM from Indistinguishability Obfuscation\n                      , IACR Cryptology ePrint Archive, Report 2015\/406, 2015,https:\/\/eprint.iacr.org\/2015\/406."},{"key":"atypb26","unstructured":"R. Canetti, Y. Chen, J. Holmgren, and M. Raykova,\n                      Succinct Adaptive Garbled RAM\n                      , Cryptology ePrint Archive, Report 2015\/1074, 2015,https:\/\/eprint.iacr.org\/2015\/1074."},{"key":"atypb27","first-page":"169","author":"Canetti R.","year":"2016","journal-title":"MIT"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746621"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"A. De Caro, V. Iovino, A. Jain, A. O'Neill, O. Paneth, and G. Persiano,\n                      On the achievability of simulation-based security for functional encryption\n                      , in Advances in Cryptology - CRYPTO 2013, Part II (Santa Barbara, CA, 2013), Springer, 2013, pp. 519-535.","DOI":"10.1007\/978-3-642-40084-1_29"},{"key":"atypb30","first-page":"50","author":"Chung K.-M.","year":"2013","journal-title":"CA)"},{"key":"atypb31","first-page":"468","volume":"2015","author":"Canetti R.","year":"2015","journal-title":"TCC"},{"key":"atypb32","unstructured":"K.M. Chung and R. Pass,\n                      A Simple ORAM\n                      , IACR Cryptology ePrint Archive, 2013:243, 2013."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"I. Damg\\aard, S. Faust, and C. Hazay,\n                      Secure two-party computation with low communication\n                      , in TCC 2012: 9th Theory of Cryptography Conference (Sicily, Italy, 2012), Lecture Notes in Comput. Sci. 7194, R. Cramer, ed., Springer, 2012, pp. 54-74.","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"atypb34","first-page":"93","author":"Dodis Y.","year":"2016","journal-title":"Springer"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"C. Gentry,\n                      Fully homomorphic encryption using ideal lattices\n                      , in 41st Annual ACM Symposium on Theory of Computing (Bethesda, MD, 2009), M. Mitzenmacher, ed., ACM Press, pp. 169-178.","DOI":"10.1145\/1536414.1536440"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters,\n                      Candidate indistinguishability obfuscation and functional encryption for all circuits\n                      , in 54th Annual Symposium on Foundations of Computer Science (Berkeley, CA, 2013), IEEE Computer Society Press, 2013, pp. 40-49.","DOI":"10.1109\/FOCS.2013.13"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, and M. Raykova,\n                      Two-round secure MPC from indistinguishability obfuscation\n                      , in TCC 2014: 11th Theory of Cryptography Conference (San Diego, CA, 2014), Lecture Notes in Comput. Sci. 8349, Y. Lindell, ed., Springer, 2014, pp. 74-94.","DOI":"10.1007\/978-3-642-54242-8_4"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry, S. Halevi, and D. Wichs,\n                      On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input\n                      , in Advances in Cryptology - CRYPTO 2014 (Santa Barbara, CA, 2014), Springer, 2014, pp. 518-535.","DOI":"10.1007\/978-3-662-44371-2_29"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49099-0_18"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"atypb41","first-page":"465","author":"Gennaro R.","year":"2010","journal-title":"Springer"},{"key":"atypb42","first-page":"405","author":"Gentry C.","year":"2014","journal-title":"Denmark)"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Halevi, M. Raykova, and D. Wichs,\n                      Outsourcing private RAM computation\n                      , in 55th Annual Symposium on Foundations of Computer Science, 2014.","DOI":"10.1109\/FOCS.2014.50"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich,\n                      Reusable garbled circuits and succinct functional encryption\n                      , in 45th Annual ACM Symposium on Theory of Computing (Palo Alto, CA, 2013), D. Boneh, T. Roughgarden, and J. Feigenbaum, eds., ACM Press, 2013, pp. 555-564.","DOI":"10.1145\/2488608.2488678"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"S. Garg, S. Lu, R. Ostrovsky, and A. Scafuro,\n                      Garbled RAM from one-way functions\n                      , in 47th Annual ACM Symposium on Theory of Computing, ACM Press, 2015.","DOI":"10.1145\/2746539.2746593"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"P. Hub\u00e1cek and D. Wichs,\n                      On the communication complexity of secure function evaluation with long output\n                      , in ITCS, ACM Press, 2015, pp. 163-172.","DOI":"10.1145\/2688073.2688105"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"Y. Ishai and E. Kushilevitz,\n                      Randomizing polynomials: A new representation with applications to round-efficient secure computation\n                      , in 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), IEEE Computer Society Press, 2000, pp. 294-304.","DOI":"10.1109\/SFCS.2000.892118"},{"key":"atypb48","first-page":"244","author":"Ishai Y.","year":"2002","journal-title":"Spain)"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"V. Koppula, A. B. Lewko, and B. Waters,\n                      Indistinguishability obfuscation for Turing machines with unbounded memory\n                      , in 47th Annual ACM Symposium on Theory of Computing, ACM Press, 2015.","DOI":"10.1145\/2746539.2746614"},{"key":"atypb50","first-page":"669","author":"Kiayias A.","year":"2013","journal-title":"CCS"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"Y. T. Kalai, R. Raz, and R. D. Rothblum,\n                      How to delegate computations: The power of no-signaling proofs\n                      , in 46th Annual ACM Symposium on Theory of Computing, D. B. Shmoys, ed., ACM Press, 2014, pp. 485-494.","DOI":"10.1145\/2591796.2591809"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. van Melkebeek,\n                      Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses\n                      , in 31st Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM Press, 1999, pp. 659-667.","DOI":"10.1145\/301250.301428"},{"key":"atypb53","first-page":"719","author":"Lu S.","year":"2013","journal-title":"Greece)"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"A. L\u00f3pez-Alt, E. Tromer, and V. Vaikuntanathan,\n                      On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption\n                      , in 44th Annual ACM Symposium on Theory of Computing, H. J. Karloff and T. Pitassi, eds., ACM Press, 2012, pp. 1219-1234.","DOI":"10.1145\/2213977.2214086"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"P. B. Miltersen and N. V. Vinodchandran,\n                      Derandomizing Arthur-Merlin games using hitting sets\n                      , in 40th Annual Symposium on Foundations of Computer Science (New York, 1999), IEEE Computer Society Press, 1999, pp. 71-80.","DOI":"10.1109\/SFFCS.1999.814579"},{"key":"atypb57","first-page":"735","author":"Mukherjee P.","year":"2016","journal-title":"Austria)"},{"key":"atypb58","first-page":"96","author":"Naor M.","year":"2003","journal-title":"Springer"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"atypb60","doi-asserted-by":"crossref","unstructured":"B. Parno, M. Raykova, and V. Vaikuntanathan,\n                      How to delegate and verify in public: Verifiable computation from attribute-based encryption\n                      , in TCC 2012: 9th Theory of Cryptography Conference (Sicily, Italy, 2012), Lecture Notes in Comput. Sci. 7194, R. Cramer, ed., Springer, 2012, pp. 422-439.","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"atypb61","unstructured":"P. Rogaway,\n                      The Round Complexity of Secure Protocols\n                      , Ph.D. thesis, Massachusetts Institute of Technology, 1991."},{"key":"atypb62","first-page":"197","author":"Shi E.","year":"2011","journal-title":"ASIACRYPT"},{"key":"atypb63","doi-asserted-by":"crossref","unstructured":"A. Sahai and B. Waters,\n                      How to use indistinguishability obfuscation: Deniable encryption, and more\n                      , in Proceedings of the 46th ACM Symposium on Theory of Computing, STOC 2014, D. B. Shmoys, ed., ACM Press, 2014, pp. 475-484.","DOI":"10.1145\/2591796.2591825"},{"key":"atypb64","unstructured":"B. Waters,\n                      A Punctured Programming Approach to Adaptively Secure Functional Encryption\n                      , Cryptology ePrint Archive, Report 2014\/588, 2014."},{"key":"atypb65","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao,\n                      How to generate and exchange secrets (extended abstract)\n                      , in 27th Annual Symposium on Foundations of Computer Science (Toronto, Ontario, Canada, 1986), IEEE Computer Society Press, 1986, pp. 162-167.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1050963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:09Z","timestamp":1787337729000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1050963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1050963"],"URL":"https:\/\/doi.org\/10.1137\/15m1050963","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}