Top

Published in:

2016 | OriginalPaper | Chapter

Multi-input Functional Encryption with Unbounded-Message Security

Authors : Vipul Goyal, Aayush Jain, Adam O’Neill

Published in: Advances in Cryptology – ASIACRYPT 2016

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Multi-input functional encryption (MIFE) was introduced by Goldwasser et al. (EUROCRYPT 2014) as a compelling extension of functional encryption. In MIFE, a receiver is able to compute a joint function of multiple, independently encrypted plaintexts. Goldwasser et al. (EUROCRYPT 2014) show various applications of MIFE to running SQL queries over encrypted databases, computing over encrypted data streams, etc.

The previous constructions of MIFE due to Goldwasser et al. (EUROCRYPT 2014) based on indistinguishability obfuscation had a major shortcoming: it could only support encrypting an a priori bounded number of message. Once that bound is exceeded, security is no longer guaranteed to hold. In addition, it could only support selective-security, meaning that the challenge messages and the set of “corrupted” encryption keys had to be declared by the adversary up-front.

In this work, we show how to remove these restrictions by relying instead on sub-exponentially secure indistinguishability obfuscation. This is done by carefully adapting an alternative MIFE scheme of Goldwasser et al. that previously overcame these shortcomings (except for selective security wrt. the set of “corrupted” encryption keys) by relying instead on differing-inputs obfuscation, which is now seen as an implausible assumption. Our techniques are rather generic, and we hope they are useful in converting other constructions using differing-inputs obfuscation to ones using sub-exponentially secure indistinguishability obfuscation instead.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Multi-key Homomorphic Authenticators

next chapter Verifiable Functional Encryption

We note that, since we do not work in the public-key setting, there is no generic implication of single-message to multi-message security.

Corruption of encryption keys \(\mathsf {EK}_1,\ldots ,\mathsf {EK}_n\) is an aspect of MIFE security not present for single-input FE; note that in [25], some subset of these keys could not be requested adaptively by the adversary - they were to be chosen even before the setup was done.

Actually, [25] required even a stronger form of \(di\mathcal {O}\) called strong differing-inputs obfuscation or differing-inputs obfuscation secure in presence of an oracle.

Due to the number of hybrids in our proof, we will also need the punctured PRFs to be sub-exponentially secure, but this already follows from a sub-exponentially secure injective one-way function.

We however do not require that the injective one-way function can be sampled efficiently.

Due to the number of hybrids in our proof, we will also need the punctured PRFs to be sub-exponentially secure, but this already follows from sub-exponentially secure injective one-way functions.

Ananth, P., Boneh, D., Garg, S., Sahai, A., Zhandry, M.: Differing-inputs obfuscation and applications. IACR Cryptology ePrint Archive 2013, p. 689 (2013). http://eprint.iacr.org/2013/689

Ananth, P., Brakerski, Z., Segev, G., Vaikuntanathan, V.: The trojan method in functional encryption: From selective to adaptive security, generically. IACR Cryptology ePrint Archive 2014, p. 917 (2014). http://eprint.iacr.org/2014/917

Ananth, P., Jain, A., Naor, M., Sahai, A., Yogev, E.: Universal obfuscation and witness encryption: Boosting correctness and combining security. IACR Cryptology ePrint Archive 2016, p. 281 (2016). http://eprint.iacr.org/2016/281

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

Badrinarayanan, S., Gupta, D., Jain, A., Sahai, A.: Multi-input functional encryption for unbounded arity functions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 27–51. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48797-6_2 CrossRef

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). doi:10.1007/3-540-44647-8_1 CrossRef

Beimel, A., Gabizon, A., Ishai, Y., Kushilevitz, E., Meldgaard, S., Paskin-Cherniavsky, A.: Non-interactive secure multiparty computation. IACR Cryptology ePrint Archive 2014, p. 960 (2014). http://eprint.iacr.org/2014/960

Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a nash equilibrium. In: Electronic Colloquium on Computational Complexity (ECCC) vol. 22, p. 1 (2015). http://eccc.hpi-web.de/report/2015/001

Bitansky, N., Vaikunthanathan, V.: Indistinguishability obfuscation from functional encryption. IACR Cryptology ePrint Archive 2013 (2015). http://eprint.iacr.org/2015/163

10.

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). doi:10.1007/978-3-642-19571-6_16 CrossRef

11.

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. IACR Cryptology ePrint Archive 2013, p. 352 (2013). http://eprint.iacr.org/2013/352

12.

Boyle, E., Chung, K.-M., Pass, R.: On extractability obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 52–73. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54242-8_3 CrossRef

13.

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. IACR Cryptology ePrint Archive 2013, p. 401 (2013). http://eprint.iacr.org/2013/401

14.

Brakerski, Z., Komargodski, I., Segev, G.: From single-input to multi-input functional encryption in the private-key setting. IACR Cryptology ePrint Archive 2015, p. 158 (2015). http://eprint.iacr.org/2015/158

15.

Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 468–497. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46497-7_19 CrossRef

16.

Caro, A., Iovino, V., Jain, A., O’Neill, A., Paneth, O., Persiano, G.: On the achievability of simulation-based security for functional encryption. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 519–535. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_29 CrossRef

17.

Chandran, N., Goyal, V., Jain, A., Sahai, A.: Functional encryption: decentralised and delegatable. IACR Cryptology ePrint Archive (2015)

18.

Dodis, Y., Nielsen, J.B. (eds.): TCC 2015. LNCS, vol. 9015. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46497-7 MATH

19.

Fischlin, M., Herzberg, A., Noon, H.B., Shulman, H.: Obfuscation combiners. IACR Cryptology ePrint Archive 2016, p. 289 (2016). http://eprint.iacr.org/2016/289

20.

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

21.

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 26–29 , Berkeley, CA, USA. pp. 40–49. IEEE Computer Society (2013). http://dx.doi.org/10.1109/FOCS.2013.13

22.

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

23.

Garg, S., Mukherjee, P., Srinivasan, A.: Obfuscation without the vulnerabilities of multilinear maps. IACR Cryptology ePrint Archive 2016, p. 390 (2016). http://eprint.iacr.org/2016/390

24.

Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005). http://dx.doi.org/10.1137/S0097539704443276 MathSciNetCrossRefMATH

25.

Goldwasser, S., et al.: Multi-input functional encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 578–602. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_32 CrossRef

26.

Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) Symposium on Theory of Computing Conference (STOC 2013), Palo Alto, CA, USA, June 1–4, pp. 555–564. ACM (2013). http://doi.acm.org/10.1145/2488608.2488678

27.

Holenstein, T.: Pseudorandom generators from one-way functions: a simple construction for any hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443–461. Springer, Heidelberg (2006). doi:10.1007/11681878_23 CrossRef

28.

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

29.

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS 2013), Berlin, Germany, November 4–8, pp. 669–684. ACM (2013). http://doi.acm.org/10.1145/2508859.2516668

30.

Koppula, V., Lewko, A.B., Waters, B.: Indistinguishability obfuscation for turing machines with unbounded memory. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC 2015), Portland, OR, USA, June 14–17, pp. 419–428 (2015). http://doi.acm.org/10.1145/2746539.2746614

31.

Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over GGH13. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 629–658. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53008-5_22 CrossRef

32.

Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). doi:10.1007/11426639_27 CrossRef

33.

Waters, B.: A punctured programming approach to adaptively secure functional encryption. IACR Cryptology ePrint Archive 2014, p. 588 (2014). http://eprint.iacr.org/2014/588

34.

Wee, H.: On obfuscating point functions. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, pp. 523–532. ACM (2005). http://doi.acm.org/10.1145/1060590.1060669

35.

Wee, H.: One-way permutations, interactive hashing and statistically hiding commitments. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 419–433. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70936-7_23 CrossRef

Title: Multi-input Functional Encryption with Unbounded-Message Security
Authors: Vipul Goyal
Aayush Jain
Adam O’Neill
Publisher: Springer Berlin Heidelberg
Book: Advances in Cryptology – ASIACRYPT 2016
Print ISBN: 978-3-662-53889-0

Electronic ISBN: 978-3-662-53890-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53890-6_18

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner