Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Secure Computation Based on Leaky Correlations: High Resilience Setting Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Incremental Program Obfuscation

verfasst von : Sanjam Garg, Omkant Pandey

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Recent advances in program obfuscation suggest that it is possible to create software that can provably safeguard secret information. However, software systems usually contain large executable code that is updated multiple times and sometimes very frequently. Freshly obfuscating the program for every small update will lead to a considerable efficiency loss. Thus, an extremely desirable property for obfuscation algorithms is incrementality: small changes to the underlying program translate into small changes to the corresponding obfuscated program.
We initiate a thorough investigation of incremental program obfuscation. We show that the strong simulation-based notions of program obfuscation, such as “virtual black-box” and “virtual grey-box” obfuscation, cannot be incremental (according to our efficiency requirements) even for very simple functions such as point functions. We then turn to the indistinguishability-based notions, and present two security definitions of varying strength — namely, a weak one and a strong one. To understand the overall strength of our definitions, we formulate the notion of incremental best-possible obfuscation and show that it is equivalent to our strong indistinguishability-based notion.
Finally, we present constructions for incremental program obfuscation satisfying both our security notions. We first give a construction achieving the weaker security notion based on the existence of general purpose indistinguishability obfuscation. Next, we present a generic transformation using oblivious RAM to amplify security from weaker to stronger, while maintaining the incrementality property.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Distinguisher-Dependent Simulation in Two Rounds and its Applications
Nächstes Kapitel From Obfuscation to the Security of Fiat-Shamir for Proofs
Fußnoten
1
Another natural way to define incrementality is the running time of \(\mathsf {Update}\) for S, divided by |S| in the worst case, taken over all \((S,F_S)\). For our constructions, the single bit measure obtains the same parameters for this alternative definition. Because for larger sets S, one can simply apply \(\mathsf {Update}\) one by one for each index in S, and still achieve same incrementality. Therefore, for simplicity, we use the simpler single bit measure. We note that for correctness and security the intermediate one bit changes may not make sense and this definitional notion is just to simplify how we measure efficiency.
 
2
See step 7, Fig. 1. Note that this obfuscation is generated only once and never changes during the updates.
 
3
Note that the only difference between these two circuits are values j and \(j-1\), and this obfuscation is performed only once throughout the whole sequence.
 
4
We emphasize that even though our scheme uses ORAM, program \(P_{C^*_1,C^*_2,s,b}\) in Fig. 5 is still only a circuit and not a “RAM” program.
 
5
Note that the size of S is polynomial in \(|S'|, \lambda , \log m \).
 
Literatur
[AB15]
Applebaum, B., Brakerski, Z.: Obfuscating circuits via composite-order graded encoding. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 528–556. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​21 CrossRef
[ABG+13]
[AIK06]
[AJ15]
Ananth, P., Jain, A.: Indistinguishability obfuscation from compact functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 308–326. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​15 CrossRef
[AJS17]
[App14]
Applebaum, B.: Bootstrapping obfuscators via fast pseudorandom functions. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 162–172. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45608-8_​9
[AS16]
[BBC+14]
Barak, B., Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O., Sahai, A.: Obfuscation for evasive functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 26–51. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​2 CrossRef
[BC10]
[BCC+14]
Bitansky, N., Canetti, R., Cohn, H., Goldwasser, S., Kalai, Y.T., Paneth, O., Rosen, A.: The impossibility of obfuscation with auxiliary input or a universal simulator. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 71–89. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44381-1_​5 CrossRef
[BCG+11]
Bitansky, N., Canetti, R., Goldwasser, S., Halevi, S., Kalai, Y.T., Rothblum, G.N.: Program obfuscation with leaky hardware. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 722–739. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25385-0_​39 CrossRef
[BCKP14]
Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O.: On virtual grey box obfuscation for general circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 108–125. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44381-1_​7 CrossRef
[BCP14]
[BCP16]
Boyle, E., Chung, K.-M., Pass, R.: Oblivious parallel RAM. In: TCC (2016)
[BFM88]
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (Extended Abstract). In: STOC, pp. 103–112 (1988)
[BGG94]
Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography: the case of hashing and signing. In: CRYPTO, pp. 216–233 (1994)
[BGG95]
Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography and application to virus protection. In STOC, pp. 45–56 (1995)
[BGI+12]
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012)MathSciNetCrossRefMATH
[BGK+14]
Barak, B., Garg, S., Kalai, Y.T., Paneth, O., Sahai, A.: Protecting obfuscation against algebraic attacks. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 221–238. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​13 CrossRef
[BGL+15]
Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: STOC, pp. 439–448 (2015)
[BKY01]
[BM97]
Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: incrementality at reduced cost. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 163–192. Springer, Heidelberg (1997). doi:10.​1007/​3-540-69053-0_​13
[BP15a]
Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 401–427. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​16 CrossRef
[BP15b]
[BPW16]
[BR13]
[BR14]
Brakerski, Z., Rothblum, G.N.: Virtual black-box obfuscation for all circuits via generic graded encoding. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 1–25. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54242-8_​1 CrossRef
[BS16]
[BSW11]
[BV15]
Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: FOCS (2015)
[BZ14]
Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 480–499. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44371-2_​27 CrossRef
[Can97]
Canetti, R.: Oracles, towards realizing random: hash functions that hide all partial information. In: CRYPTO, pp. 455–469 (1997)
[CHJV15]
Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Indistinguishability obfuscation of iterated circuits and RAM programs. In: STOC (2015)
[CLP14]
Chung, K.-M., Liu, Z., Pass, R.: Statistically-secure ORAM with õ(\({\rm log}^{\rm 2}\) n) overhead. In: ASIACRYPT, pp. 62–81 (2014)
[CLP15]
Chung, K.-M., Lin, H., Pass, R.: Constant-round concurrent zero-knowledge from indistinguishability obfuscation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 287–307. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​14 CrossRef
[CRV10]
[CV13]
Canetti, R., Vaikuntanathan, V.: Obfuscating branching programs using black-box pseudo-free groups. IACR Cryptology ePrint Archive 2013:500 (2013)
[Fis97a]
Fischlin, M.: Incremental cryptography and memory checkers. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 393–408. Springer, Heidelberg (1997). doi:10.​1007/​3-540-69053-0_​27
[Fis97b]
Fischlin, M.: Lower bounds for the signature size of incremental schemes. In: FOCS, pp. 438–447(1997)
[FLS99]
Feige, L., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29, 1–28 (1999)MathSciNetCrossRefMATH
[GGH13a]
Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38348-9_​1 CrossRef
[GGH+13b]
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013)
[GGHW14]
Garg, S., Gentry, C., Halevi, S., Wichs, D.: On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 518–535. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44371-2_​29 CrossRef
[GIS+10]
Goyal, V., Ishai, Y., Sahai, A., Venkatesan, R., Wadia, A.: Founding cryptography on tamper-proof hardware tokens. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 308–326. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-11799-2_​19 CrossRef
[GK05]
Goldwasser, S., Kalai, Y.T.: On the impossibility of obfuscation with auxiliary input. In: FOCS, pp. 553–562 (2005)
[GO96]
[Gol87]
Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC, pp. 182–194 (1987)
[GOS06]
Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006). doi:10.​1007/​11761679_​21 CrossRef
[GR07]
[Had00]
[Had10]
[HRSV07]
Hohenberger, S., Rothblum, G.N., Shelat, A., Vaikuntanathan, V.: Securely obfuscating re-encryption. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 233–252. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-70936-7_​13 CrossRef
[HSW14]
Hohenberger, S., Sahai, A., Waters, B.: Replacing a random oracle: full domain hash from indistinguishability obfuscation. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 201–220. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​12 CrossRef
[HW15]
Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS, pp. 163–172 (2015)
[IB]
[IPS15]
Ishai, Y., Pandey, O., Sahai, A.: Public-coin differing-inputs obfuscation and its applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 668–697. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​26 CrossRef
[KLW15]
Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: STOC (2015)
[KMN+14]
Komargodski, I., Moran, T., Naor, M., Pass, R., Rosen, A., Yogev, E.: One-way functions and (im)perfect obfuscation. In: FOCS, pp. 374–383 (2014)
[LO13]
[LPS04]
Lynn, B., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24676-3_​2 CrossRef
[Mic97]
Micciancio, D., Structures, O.D.: Applications to cryptography. In: STOC, pp. 456–464 (1997)
[MO14]
Marcedone, A., Orlandi, C.: Obfuscation \(\Rightarrow \) (IND-CPA security !\(\Rightarrow \) circular security). In: Proceedings of the 9th International Conference on Security and Cryptography for Networks, SCN 2014, Amalfi, Italy, 3–5 September 2014, pp. 77–90 (2014)
[MPRS12]
Mironov, I., Pandey, O., Reingold, O., Segev, G.: Incremental deterministic public-key encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 628–644. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​37 CrossRef
[NY90]
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427–437 (1990)
[O’N10]
O’Neill, A.: Definitional issues in functional encryption. Cryptology ePrint Archive, Report 2010/556 (2010)
[OPWW15]
Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 121–145. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48797-6_​6 CrossRef
[Ost90]
Ostrovsky, R.: Efficient computation on oblivious RAMs. In: STOC, pp. 514–523 (1990)
[PPS15]
Pandey, O., Prabhakaran, M., Sahai, A.: Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 638–667. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46497-7_​25 CrossRef
[SCSL11]
Shi, E., Chan, T.-H.H., Stefanov, E., Li, M.: Oblivious RAM with O((logN)3) worst-case cost. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 197–214. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25385-0_​11 CrossRef
[SvDS+13]
Stefanov, E., van Dijk, M., Shi, E., Fletcher, C.W., Ren, L., Xiangyao, Y., Devadas, S.: Path ORAM: an extremely simple oblivious RAM protocol. In: ACM CCS, pp. 299–310 (2013)
[SW14]
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC, pp. 475–484 (2014)
[Wee05]
Wee, H.: On obfuscating point functions. In: STOC, pp. 523–532 (2005)
Metadaten
Titel
Incremental Program Obfuscation
verfasst von
Sanjam Garg
Omkant Pandey
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63714-3

Electronic ISBN: 978-3-319-63715-0

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63715-0_7