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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Functional Encryption Without Obfuscation

verfasst von : Sanjam Garg, Craig Gentry, Shai Halevi, Mark Zhandry

Erschienen in: Theory of Cryptography

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally most of these schemes are proved in the weaker selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction.
In this work, we overcome the above limitations and realize an adaptively secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on composite order multilinear maps. Though we do not currently have secure instantiations for these assumptions, we expect that multilinear maps supporting these assumptions will discovered in the future. Alternatively, follow up results may yield constructions which can be securely instantiated.
As a separate technical contribution of independent interest, we show how to add to existing graded encoding schemes a new extension function, that can be thought of as dynamically introducing new encoding levels.

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 Cutting-Edge Cryptography Through the Lens of Secret Sharing
Nächstes Kapitel On Constructing One-Way Permutations from Indistinguishability Obfuscation
Fußnoten
1
Garg et al. [GGSW13] only provide the intuition for witness encryption but it extends to \(i\mathcal {O}\).
 
2
We note that Gorbunov et al. [GVW12] show a general transformation from \(NC^1\) to poly-size circuits, but the security proof relies on the underlying FE scheme being simulation secure. Such security is impossible in the setting where the number of secret key queries in unbounded [AGVW13], which is the setting studied in this work. Subsequent to our work, Ananth et al. [ABSV14] show that FE for \(NC^1\) can be boosted to FE for all circuit.
 
3
This observation that [BLMR13] is puncturable appears in the full version of the paper: http://​theory.​stanford.​edu/​~klewi/​papers/​homprf-full.​pdf. It is also folklore that the Naor-Reingold PRF is puncturable while maintaining \(NC^1\) evaluation.
 
4
We note that the GGH encodings can also be extended to deal with this functionality as well but here we provide this only for the CLT encodings.
 
5
Not to be confused with dual-input branching programs from [BGK+14].
 
6
Using current graded encodings, it is not possible to publicly compute matrix inverses since users do not have direct access to the underlying ring. However, the setup procedure would know a trapdoor for the graded encodings that does allow computing the matrix inverse. Alternatively, we can replace \(R_i^{-1}\) with the adjugate matrix \(R_i^{adj}\), encodings of which can be computed publicly. The adjugate and matrix inverse only differ by a scalar multiple (namely, the determinant), and since we multiply everything by a random scalar anyway, the distributions of encodings obtained are identical in both approaches.
 
7
We actually cannot compute the quantities \(R_i^{-1}\) since we do not have access to the trapdoor for the encodings. Therefore, we must actually compute \(R_i^{adj}\) instead of \(R_i^{-1}\). However, since we multiply by a random scalar anyway, the distribution of encodings is exactly the same as if we had computed the matrix inverse.
 
Literatur
[ABSV14]
[AGVW13]
Agrawal, S., Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption: new perspectives and lower bounds. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 500–518. Springer, Heidelberg (2013)CrossRef
[AJ15]
[Bar86]
Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in \(nc_1\). In: STOC (1986)
[BGI14]
Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014)CrossRef
[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)CrossRef
[BLMR13]
Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 410–428. Springer, Heidelberg (2013)CrossRef
[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)CrossRef
[BS02]
[BS15]
Brakerski, Z., Segev, G.: Function-private functional encryption in the private-key setting. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 306–324. Springer, Heidelberg (2015)CrossRef
[BSW11]
Boneh, D., Sahai, A., Waters, B.: Functional encryption: definitions and challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011)CrossRef
[BV15]
[BW13]
Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 280–300. Springer, Heidelberg (2013)CrossRef
[BWZ14]
[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, Part I. LNCS, vol. 8616, pp. 480–499. Springer, Heidelberg (2014)CrossRef
[CGH+15]
Coron, J.-S., et al.: Zeroizing without low-level zeroes: New MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 247–266. Springer, Heidelberg (2015)CrossRef
[CHL+15]
Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015)
[CLT13]
Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013)CrossRef
[CLT15a]
[CLT15b]
Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Gennaro, R., Robshaw, J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 267–286. Springer, Heidelberg (2015)CrossRef
[Gen06]
Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445–464. Springer, Heidelberg (2006)CrossRef
[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)CrossRef
[GGH+13b]
Garg, S., Gentry, C., Sahai, A., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual Symposium on Foundations of Computer Science, pp. 40–49. IEEE Computer Society Press, Berkeley, CA, USA, 26–29 October 2013
[GGHZ14a]
[GGHZ14b]
[GGSW13]
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th Annual ACM Symposium on Theory of Computing, pp. 467–476. ACM Press, Palo Alto (2013)CrossRef
[GLSW14]
[GLW14]
Gentry, C., Lewko, A., Waters, B.: Witness encryption from instance independent assumptions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 426–443. Springer, Heidelberg (2014)CrossRef
[GVW12]
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Functional encryption with bounded collusions via multi-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 162–179. Springer, Heidelberg (2012)CrossRef
[IK00]
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, pp. 294–304. IEEE Computer Society Press, Redondo Beach, California, USA, 12–14 November 2000
[Kil88]
Kilian, J.: Founding cryptography on oblivious transfer. In: 20th Annual ACM Symposium on Theory of Computing, pp. 20–31. ACM Press, Chicago, Illinois, USA, 2–4 May 1988
[KPTZ13]
Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013: 20th Conference on Computer and Communications Security, pp. 669–684. ACM Press, Berlin (2013)
[O’N10]
[PST14]
Pass, R., Seth, K., Telang, S.: Indistinguishability obfuscation from semantically-secure multilinear encodings. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 500–517. Springer, Heidelberg (2014)CrossRef
[Wat05]
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)CrossRef
[Wat09]
Waters, B.: Dual system encryption: realizing fully secure ibe and hibe under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Heidelberg (2009)CrossRef
[Wat14]
[Yao82]
Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, pp. 160–164. IEEE Computer Society Press, Chicago, Illinois, 3–5 November 1982
Metadaten
Titel
Functional Encryption Without Obfuscation
verfasst von
Sanjam Garg
Craig Gentry
Shai Halevi
Mark Zhandry
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
Buch
Theory of Cryptography

Print ISBN: 978-3-662-49098-3

Electronic ISBN: 978-3-662-49099-0

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-662-49099-0_18

Premium Partner

    Bildnachweise