Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings
© 2018 Society for Industrial and Applied Mathematics. We show how to construct indistinguishability obfuscation (\bfi/bfO) for RAM programs with bounded space, assuming/bfi/bfO for circuits and one-way functions, both with subexponential security. That is, given a RAM program whose computation requ...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137817 |
| _version_ | 1811086291278757888 |
|---|---|
| author | Bitansky, Nir Canetti, Ran Garg, Sanjam Holmgren, Justin Jain, Abhishek Lin, Huijia Pass, Rafael Telang, Sidharth Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bitansky, Nir Canetti, Ran Garg, Sanjam Holmgren, Justin Jain, Abhishek Lin, Huijia Pass, Rafael Telang, Sidharth Vaikuntanathan, Vinod |
| author_sort | Bitansky, Nir |
| collection | MIT |
| description | © 2018 Society for Industrial and Applied Mathematics. We show how to construct indistinguishability obfuscation (\bfi/bfO) for RAM programs with bounded space, assuming/bfi/bfO 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. |
| first_indexed | 2024-09-23T13:23:51Z |
| format | Article |
| id | mit-1721.1/137817 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:23:51Z |
| publishDate | 2021 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1378172022-10-01T14:59:15Z Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings Bitansky, Nir Canetti, Ran Garg, Sanjam Holmgren, Justin Jain, Abhishek Lin, Huijia Pass, Rafael Telang, Sidharth Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2018 Society for Industrial and Applied Mathematics. We show how to construct indistinguishability obfuscation (\bfi/bfO) for RAM programs with bounded space, assuming/bfi/bfO 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. 2021-11-08T20:25:00Z 2021-11-08T20:25:00Z 2018-01 2019-07-09T16:46:24Z Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 https://hdl.handle.net/1721.1/137817 Bitansky, Nir, Canetti, Ran, Garg, Sanjam, Holmgren, Justin, Jain, Abhishek et al. 2018. "Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings." 47 (3). en 10.1137/15m1050963 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Bitansky, Nir Canetti, Ran Garg, Sanjam Holmgren, Justin Jain, Abhishek Lin, Huijia Pass, Rafael Telang, Sidharth Vaikuntanathan, Vinod Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title | Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title_full | Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title_fullStr | Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title_full_unstemmed | Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title_short | Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings |
| title_sort | indistinguishability obfuscation for ram programs and succinct randomized encodings |
| url | https://hdl.handle.net/1721.1/137817 |
| work_keys_str_mv | AT bitanskynir indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT canettiran indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT gargsanjam indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT holmgrenjustin indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT jainabhishek indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT linhuijia indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT passrafael indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT telangsidharth indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings AT vaikuntanathanvinod indistinguishabilityobfuscationforramprogramsandsuccinctrandomizedencodings |