Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings

Published: 26 June 2018 Publication History

Abstract

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.

References

[1]
P. Ananth, Y.-C. Chen, K.-M. Chung, H. Lin, and W.-K. Lin, Delegating RAM computations with adaptive soundness and privacy, in Theory of Cryptography -- TCC 2016, M. Hirt and A. Smith, eds., Lecture Notes in Comput. Sci. 9986, Springer, 2016, pp. 3--30.
[2]
B. Applebaum, Y. Ishai, and E. Kushilevitz, Cryptography in NC$^0$, in 45th Annual Symposium on Foundations of Computer Science (Rome, Italy, 2004), IEEE Computer Society Press, 2004, pp. 166--175.
[3]
B. Applebaum, Y. Ishai, and E. Kushilevitz, Computationally private randomizing polynomials and their applications, Comput. Complexity, 15 (2006), pp. 115--162.
[4]
B. Applebaum, Y. Ishai, and E. Kushilevitz, From secrecy to soundness: Efficient verification via secure computation, 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.
[5]
B. Applebaum, Y. Ishai, and E. Kushilevitz, How to garble arithmetic circuits, in 52nd Annual Symposium on Foundations of Computer Science (Palm Springs, CA, 2011), R. Ostrovsky, ed., IEEE Computer Society Press, 2011, pp. 120--129.
[6]
G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, and D. Wichs, Multiparty computation with low communication, computation and interaction via threshold FHE, in Advances in Cryptology -- EUROCRYPT 2012 (Cambridge, UK, 2012), Lecture Notes in Comput. Sci. 7237, D. Pointcheval and T. Johansson, eds., Springer, 2012, pp. 483--501.
[7]
P. Ananth, A. Jain, and A. Sahai, Indistinguishability Obfuscation with Constant Size Overhead, IACR Cryptology ePrint Archive, 2015:1023, 2015.
[8]
P. Ananth, A. Jain, and A. Sahai, Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization, in Advances in Cryptology -- CRYPTO 2017, J. Katz and H. Shacham, eds., Lecture Notes in Comput. Sci. 10402, Springer, 2017, pp. 252--279.
[9]
B. Applebaum, Key-dependent message security: Generic amplification and completeness, in Advances in Cryptology -- EUROCRYPT 2011 (Tallinn, Estonia, 2011), Lecture Notes in Comput. Sci. 6632, K. G. Paterson, ed., Springer, 2011, pp. 527--546.
[10]
B. Applebaum, Randomly encoding functions: A new cryptographic paradigm (invited talk), in Proceedings of the 5th International Conference on Information Theoretic Security, ICITS 2011 (Amsterdam, The Netherlands), 2011, pp. 25--31.
[11]
B. Applebaum, Bootstrapping obfuscators via fast pseudorandom functions, in Advances in Cryptology - ASIACRYPT 2014 - Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security (Kaoshiung, Taiwan, R.O.C.), 2014, pp. 162--172.
[12]
N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, in ITCS 2012: 3rd Innovations in Theoretical Computer Science (Cambridge, MA, 2012), S. Goldwasser, ed., Association for Computing Machinery, 2012, pp. 326--349.
[13]
N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, Recursive composition and bootstrapping for SNARKS and proof-carrying data, 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.
[14]
N. Bitansky, R. Canetti, A. Chiesa, S. Goldwasser, H. Lin, A. Rubinstein, and E. Tromer, The hunting of the SNARK, J. Cryptology, 30 (2017), pp. 989--1066.
[15]
E. Boyle, K.-M. Chung, and R. Pass, On extractability obfuscation, 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.
[16]
B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang, On the (im)possibility of obfuscating programs, in Advances in Cryptology CRYPTO 2001, Springer, 2001, pp. 1--18.
[17]
E. Boyle, S. Goldwasser, and I. Ivan, Functional signatures and pseudorandom functions, in PKC, 2014, pp. 501--519.
[18]
N. Bitansky, S. Garg, H. Lin, R. Pass, and S. Telang, Succinct randomized encodings and their applications, in Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015 (Portland, OR), ACM, 2015, pp. 439--448.
[19]
B. Barak, I. Haitner, D. Hofheinz, and Y. Ishai, Bounded key-dependent message security, in Advances in Cryptology -- EUROCRYPT 2010 (French Riviera, 2010), Lecture Notes in Comput. Sci. 6110, H. Gilbert, ed., Springer, 2010, pp. 423--444.
[20]
M. Bellare, V. T. Hoang, and S. Keelveedhi, Instantiating random oracles via UCEs, 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.
[21]
M. Bellare, V. T. Hoang, and P. Rogaway, Adaptively secure garbling with applications to one-time programs and secure outsourcing, in Advances in Cryptology -- ASIACRYPT 2012 (Beijing, China, 2012), Lecture Notes in Comput. Sci. 7658, X. Wang and K. Sako, eds., Springer, 2012, pp. 134--153.
[22]
M. Bellare, V. T. Hoang, and P. Rogaway, Foundations of garbled circuits, in The ACM Conference on Computer and Communications Security, CCS'12 (Raleigh, NC), 2012, pp. 784--796.
[23]
D. Boneh, K. Lewi, H. W. Montgomery, and A. Raghunathan, Key homomorphic PRFs and their applications, in Advances in Cryptology -- CRYPTO 2013, Part I (Santa Barbara, CA, 2013), Lecture Notes in Comput. Sci. 8042, R. Canetti and J. A. Garay, eds., Springer, 2013, pp. 410--428.
[24]
D. Boneh and B. Waters, Constrained pseudorandom functions and their applications, in ASIACRYPT (2), 2013, pp. 280--300.
[25]
Y.-C. Chen, S. S. M. Chow, K.-M. Chung, R. W. F. Lai, W.-K. Lin, and H.-S. Zhou, Cryptography for Parallel RAM from Indistinguishability Obfuscation, IACR Cryptology ePrint Archive, Report 2015/406, 2015, https://eprint.iacr.org/2015/406.
[26]
R. Canetti, Y. Chen, J. Holmgren, and M. Raykova, Succinct Adaptive Garbled RAM, Cryptology ePrint Archive, Report 2015/1074, 2015, https://eprint.iacr.org/2015/1074.
[27]
R. Canetti and J. Holmgren, Fully succinct garbled RAM, in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Cambridge, MA, 2016), MIT, 2016, pp. 169--178, http://doi.acm.org/10.1145/2840728.2840765.
[28]
R. Canetti, J. Holmgren, A. Jain, and V. Vaikuntanathan, Succinct garbling and indistinguishability obfuscation for RAM programs, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC 2015 (Portland, OR), 2015, pp. 429--437.
[29]
A. De Caro, V. Iovino, A. Jain, A. O'Neill, O. Paneth, and G. Persiano, On the achievability of simulation-based security for functional encryption, in Advances in Cryptology - CRYPTO 2013, Part II (Santa Barbara, CA, 2013), Springer, 2013, pp. 519--535.
[30]
K.-M. Chung, H. Lin, and R. Pass, Constant-round concurrent zero knowledge from p-certificates, in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013 (Berkeley, CA), 2013, pp. 50--59.
[31]
R. Canetti, H. Lin, S. Tessaro, and V. Vaikuntanathan, Obfuscation of probabilistic circuits and applications, in Theory of Cryptography - 12th Theory of Cryptography Conference, Part II, TCC 2015 (Warsaw, Poland), 2015, pp. 468--497.
[32]
K.-M. Chung and R. Pass, A Simple ORAM, IACR Cryptology ePrint Archive, 2013:243, 2013.
[33]
I. Damg\aard, S. Faust, and C. Hazay, Secure two-party computation with low communication, 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.
[34]
Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs, Spooky encryption and its applications, in Advances in Cryptology - CRYPTO 2016, Part III (Santa Barbara, CA), Springer, 2016, pp. 93--122.
[35]
C. Gentry, Fully homomorphic encryption using ideal lattices, in 41st Annual ACM Symposium on Theory of Computing (Bethesda, MD, 2009), M. Mitzenmacher, ed., ACM Press, pp. 169--178.
[36]
S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits, in 54th Annual Symposium on Foundations of Computer Science (Berkeley, CA, 2013), IEEE Computer Society Press, 2013, pp. 40--49.
[37]
S. Garg, C. Gentry, S. Halevi, and M. Raykova, Two-round secure MPC from indistinguishability obfuscation, 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.
[38]
S. Garg, C. Gentry, S. Halevi, and D. Wichs, On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input, in Advances in Cryptology - CRYPTO 2014 (Santa Barbara, CA, 2014), Springer, 2014, pp. 518--535.
[39]
S. Garg, C. Gentry, S. Halevi, and M. Zhandry, Functional encryption without obfuscation, in Theory of Cryptography - 13th Theory of Cryptography Conference, Part II, Lecture Notes in Comput. Sci. 9563, Springer, 2016, pp. 480--511.
[40]
O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions, J. ACM, 33 (1986), pp. 792--807.
[41]
R. Gennaro, C. Gentry, and B. Parno, Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in Advances in Cryptology -- CRYPTO 2010 (Santa Barbara, CA, 2010), Lecture Notes in Comput. Sci. 6223, T. Rabin, ed., Springer, 2010, pp. 465--482.
[42]
C. Gentry, S. Halevi, S. Lu, R. Ostrovsky, M. Raykova, and D. Wichs, Garbled RAM revisited, in Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (Copenhagen, Denmark), 2014, pp. 405--422.
[43]
C. Gentry, S. Halevi, M. Raykova, and D. Wichs, Outsourcing private RAM computation, in 55th Annual Symposium on Foundations of Computer Science, 2014.
[44]
S. Goldwasser, Y. T. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich, Reusable garbled circuits and succinct functional encryption, 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.
[45]
S. Garg, S. Lu, R. Ostrovsky, and A. Scafuro, Garbled RAM from one-way functions, in 47th Annual ACM Symposium on Theory of Computing, ACM Press, 2015.
[46]
P. Hubácek and D. Wichs, On the communication complexity of secure function evaluation with long output, in ITCS, ACM Press, 2015, pp. 163--172.
[47]
Y. Ishai and E. Kushilevitz, Randomizing polynomials: A new representation with applications to round-efficient secure computation, in 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), IEEE Computer Society Press, 2000, pp. 294--304.
[48]
Y. Ishai and E. Kushilevitz, Perfect constant-round secure computation via perfect randomizing polynomials, in Automata, Languages and Programming, 29th International Colloquium, ICALP 2002 (Malaga, Spain), 2002, pp. 244--256.
[49]
V. Koppula, A. B. Lewko, and B. Waters, Indistinguishability obfuscation for Turing machines with unbounded memory, in 47th Annual ACM Symposium on Theory of Computing, ACM Press, 2015.
[50]
A. Kiayias, S. Papadopoulos, N. Triandopoulos, and T. Zacharias, Delegatable pseudorandom functions and applications, in CCS, 2013, pp. 669--684.
[51]
Y. T. Kalai, R. Raz, and R. D. Rothblum, How to delegate computations: The power of no-signaling proofs, in 46th Annual ACM Symposium on Theory of Computing, D. B. Shmoys, ed., ACM Press, 2014, pp. 485--494.
[52]
A. Klivans and D. van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, in 31st Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM Press, 1999, pp. 659--667.
[53]
S. Lu and R. Ostrovsky, How to garble RAM programs, in Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques (Athens, Greece), 2013, pp. 719--734.
[54]
A. López-Alt, E. Tromer, and V. Vaikuntanathan, On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, in 44th Annual ACM Symposium on Theory of Computing, H. J. Karloff and T. Pitassi, eds., ACM Press, 2012, pp. 1219--1234.
[55]
S. Micali, Computationally sound proofs, SIAM J. Comput., 30 (2000), pp. 1253--1298, https://doi.org/10.1137/S0097539795284959.
[56]
P. B. Miltersen and N. V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, in 40th Annual Symposium on Foundations of Computer Science (New York, 1999), IEEE Computer Society Press, 1999, pp. 71--80.
[57]
P. Mukherjee and D. Wichs, Two round multiparty computation via multi-key FHE, in Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Part II (Vienna, Austria), 2016, pp. 735--763.
[58]
M. Naor, On cryptographic assumptions and challenges (invited talk), in Advances in Cryptology -- CRYPTO 2003 (Santa Barbara, CA, 2003), Lecture Notes in Comput. Sci. 2729, D. Boneh, ed., Springer, 2003, pp. 96--109.
[59]
N. Pippenger and M. J. Fischer, Relations among complexity measures, J. ACM, 26 (1979), pp. 361--381.
[60]
B. Parno, M. Raykova, and V. Vaikuntanathan, How to delegate and verify in public: Verifiable computation from attribute-based encryption, 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.
[61]
P. Rogaway, The Round Complexity of Secure Protocols, Ph.D. thesis, Massachusetts Institute of Technology, 1991.
[62]
E. Shi, T.-H. H. Chan, E. Stefanov, and M. Li, Oblivious RAM with $O((\log N)^3)$ worst-case cost, in ASIACRYPT, 2011, pp. 197--214.
[63]
A. Sahai and B. Waters, How to use indistinguishability obfuscation: Deniable encryption, and more, in Proceedings of the 46th ACM Symposium on Theory of Computing, STOC 2014, D. B. Shmoys, ed., ACM Press, 2014, pp. 475--484.
[64]
B. Waters, A Punctured Programming Approach to Adaptively Secure Functional Encryption, Cryptology ePrint Archive, Report 2014/588, 2014.
[65]
A. C.-C. Yao, How to generate and exchange secrets (extended abstract), in 27th Annual Symposium on Foundations of Computer Science (Toronto, Ontario, Canada, 1986), IEEE Computer Society Press, 1986, pp. 162--167.

Cited By

View all
  • (2024)Laconic Function Evaluation and ABE for RAMs from (Ring-)LWEAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_4(107-142)Online publication date: 18-Aug-2024
  • (2024)Laconic Function Evaluation, Functional Encryption and Obfuscation for RAMs with Sublinear ComputationAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58723-8_7(190-218)Online publication date: 26-May-2024
  • (2023)Succinct Computational Secret SharingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585127(1553-1566)Online publication date: 2-Jun-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing
SIAM Journal on Computing  Volume 47, Issue 3
DOI:10.1137/smjcat.47.3
Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 26 June 2018

Author Tags

  1. cryptography
  2. randomized encodings
  3. obfuscation
  4. bootstrapping

Author Tags

  1. 68P25
  2. 68Q99

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Laconic Function Evaluation and ABE for RAMs from (Ring-)LWEAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_4(107-142)Online publication date: 18-Aug-2024
  • (2024)Laconic Function Evaluation, Functional Encryption and Obfuscation for RAMs with Sublinear ComputationAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58723-8_7(190-218)Online publication date: 26-May-2024
  • (2023)Succinct Computational Secret SharingProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585127(1553-1566)Online publication date: 2-Jun-2023
  • (2023)Adaptively Secure MPC with Sublinear Communication ComplexityJournal of Cryptology10.1007/s00145-023-09446-636:2Online publication date: 22-Mar-2023
  • (2023)Non-interactive Universal ArgumentsAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_5(132-158)Online publication date: 20-Aug-2023
  • (2022)Quantum garbled circuitsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520073(804-817)Online publication date: 9-Jun-2022
  • (2022)Obfustopia Built on Secret-Key Functional EncryptionJournal of Cryptology10.1007/s00145-022-09429-z35:3Online publication date: 3-Jun-2022
  • (2021)Bounded Collusion ABE for TMs from IBEAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92068-5_13(371-402)Online publication date: 6-Dec-2021
  • (2020)Characterizing Deterministic-Prover Zero KnowledgeTheory of Cryptography10.1007/978-3-030-64375-1_19(535-566)Online publication date: 16-Nov-2020
  • (2019)Adaptively Secure and Succinct Functional Encryption: Improving Security and Efficiency, SimultaneouslyAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26954-8_17(521-551)Online publication date: 18-Aug-2019
  • Show More Cited By

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media