×

Combiners for functional encryption, unconditionally. (English) Zbl 1479.94193

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12105, 141-168 (2020).
Summary: Functional encryption (FE) combiners allow one to combine many candidates for a functional encryption scheme, possibly based on different computational assumptions, into another functional encryption candidate with the guarantee that the resulting candidate is secure as long as at least one of the original candidates is secure. The fundamental question in this area is whether FE combiners exist. There have been a series of works [P. Ananth et al., Lect. Notes Comput. Sci. 9815, 491–520 (2016; Zbl 1391.94724); P. Ananth et al., ibid. 10210, 91–121 (2017; Zbl 1410.94039); P. Ananth et al., ibid. 11891, 199–228 (2019; Zbl 1455.94108)] on constructing FE combiners from various assumptions.
We give the first unconditional construction of combiners for functional encryption, resolving this question completely. Our construction immediately implies an unconditional universal functional encryption scheme, an FE scheme that is secure if such an FE scheme exists. Previously such results either relied on algebraic assumptions or required subexponential security assumptions.
For the entire collection see [Zbl 1475.94008].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal, S.; Ishai, Y.; Rijmen, V., Indistinguishability obfuscation without multilinear maps: new methods for bootstrapping and instantiation, Advances in Cryptology - EUROCRYPT 2019, 191-225 (2019), Cham: Springer, Cham · Zbl 1470.94072 · doi:10.1007/978-3-030-17653-2_7
[2] Ananth, P.; Badrinarayanan, S.; Jain, A.; Manohar, N.; Sahai, A.; Hofheinz, D.; Rosen, A., From FE combiners to secure MPC and back, Theory of Cryptography, 199-228 (2019), Cham: Springer, Cham · Zbl 1455.94108 · doi:10.1007/978-3-030-36030-6_9
[3] Ananth, P.; Brakerski, Z.; Segev, G.; Vaikuntanathan, V.; Gennaro, R.; Robshaw, M., From selective to adaptive security in functional encryption, Advances in Cryptology - CRYPTO 2015, 657-677 (2015), Heidelberg: Springer, Heidelberg · Zbl 1351.94021 · doi:10.1007/978-3-662-48000-7_32
[4] Ananth, P.; Jain, A.; Lin, H.; Matt, C.; Sahai, A.; Boldyreva, A.; Micciancio, D., Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification, Advances in Cryptology - CRYPTO 2019, 284-332 (2019), Cham: Springer, Cham · Zbl 1436.94030 · doi:10.1007/978-3-030-26954-8_10
[5] Ananth, P.; Jain, A.; Naor, M.; Sahai, A.; Yogev, E.; Robshaw, M.; Katz, J., Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption, Advances in Cryptology - CRYPTO 2016, 491-520 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94724 · doi:10.1007/978-3-662-53008-5_17
[6] Ananth, P.; Jain, A.; Sahai, A.; Coron, J-S; Nielsen, JB, Robust transforming combiners from indistinguishability obfuscation to functional encryption, Advances in Cryptology - EUROCRYPT 2017, 91-121 (2017), Cham: Springer, Cham · Zbl 1410.94039 · doi:10.1007/978-3-319-56620-7_4
[7] Ananth, P., Jain, A., Sahai, A.: Indistinguishability obfuscation without multilinear maps: iO from LWE, bilinear maps, and weak pseudorandomness. IACR Cryptology ePrint Archive 2018, 615 (2018)
[8] Ananth, P.; Jain, A.; Gennaro, R.; Robshaw, M., Indistinguishability obfuscation from compact functional encryption, Advances in Cryptology - CRYPTO 2015, 308-326 (2015), Heidelberg: Springer, Heidelberg · Zbl 1336.94035 · doi:10.1007/978-3-662-47989-6_15
[9] Ananth, P.; Sahai, A.; Coron, J-S; Nielsen, JB, Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps, Advances in Cryptology - EUROCRYPT 2017, 152-181 (2017), Cham: Springer, Cham · Zbl 1411.94046 · doi:10.1007/978-3-319-56620-7_6
[10] Badrinarayanan, S., Goyal, V., Jain, A., Sahai, A.: A note on VRFs from verifiable functional encryption. IACR Cryptology ePrint Archive 2017, 51 (2017)
[11] Barak, B.; Brakerski, Z.; Komargodski, I.; Kothari, PK; Nielsen, JB; Rijmen, V., Limits on low-degree pseudorandom generators (or: sum-of-squares meets program obfuscation), Advances in Cryptology - EUROCRYPT 2018, 649-679 (2018), Cham: Springer, Cham · Zbl 1428.94058 · doi:10.1007/978-3-319-78375-8_21
[12] Barak, B.; Hopkins, SB; Jain, A.; Kothari, P.; Sahai, A.; Ishai, Y.; Rijmen, V., Sum-of-squares meets program obfuscation, revisited, Advances in Cryptology - EUROCRYPT 2019, 226-250 (2019), Cham: Springer, Cham · Zbl 1470.94077 · doi:10.1007/978-3-030-17653-2_8
[13] Bitansky, N.; Kalai, Y.; Reyzin, L., Verifiable random functions from non-interactive witness-indistinguishable proofs, Theory of Cryptography, 567-594 (2017), Cham: Springer, Cham · Zbl 1412.94155 · doi:10.1007/978-3-319-70503-3_19
[14] Bitansky, N.; Nishimaki, R.; Passelègue, A.; Wichs, D.; Hirt, M.; Smith, A., From cryptomania to obfustopia through secret-key functional encryption, Theory of Cryptography, 391-418 (2016), Heidelberg: Springer, Heidelberg · Zbl 1400.94122 · doi:10.1007/978-3-662-53644-5_15
[15] Bitansky, N., Vaikuntanathan, V.: Indistinguishability obfuscation from functional encryption. In: FOCS (2015) · Zbl 1407.94087
[16] Bitansky, N.; Vaikuntanathan, V.; Kushilevitz, E.; Malkin, T., Indistinguishability obfuscation: from approximate to exact, Theory of Cryptography, 67-95 (2016), Heidelberg: Springer, Heidelberg · Zbl 1388.94034 · doi:10.1007/978-3-662-49096-9_4
[17] Bitansky, N.; Vaikuntanathan, V.; Coron, J-S; Nielsen, JB, A note on perfect correctness by derandomization, Advances in Cryptology - EUROCRYPT 2017, 592-606 (2017), Cham: Springer, Cham · Zbl 1415.94411 · doi:10.1007/978-3-319-56614-6_20
[18] Boneh, D.; Shacham, H.; Boldyreva, A., Threshold cryptosystems from threshold fully homomorphic encryption, Advances in Cryptology - CRYPTO 2018, 565-596 (2018), Cham: Springer, Cham · Zbl 1444.94047 · doi:10.1007/978-3-319-96884-1_19
[19] Boneh, D.; Sahai, A.; Waters, B.; Ishai, Y., Functional encryption: definitions and challenges, Theory of Cryptography, 253-273 (2011), Heidelberg: Springer, Heidelberg · Zbl 1295.94027 · doi:10.1007/978-3-642-19571-6_16
[20] Boyle, E.; Gilboa, N.; Ishai, Y.; Oswald, E.; Fischlin, M., Function secret sharing, Advances in Cryptology - EUROCRYPT 2015, 337-367 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94664 · doi:10.1007/978-3-662-46803-6_12
[21] Boyle, E.; Gilboa, N.; Ishai, Y.; Robshaw, M.; Katz, J., Breaking the circuit size barrier for secure computation under DDH, Advances in Cryptology - CRYPTO 2016, 509-539 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94038 · doi:10.1007/978-3-662-53018-4_19
[22] Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: CCS, pp. 1292-1303 (2016)
[23] Cheon, JH; Han, K.; Lee, C.; Ryu, H.; Stehlé, D.; Oswald, E.; Fischlin, M., Cryptanalysis of the multilinear map over the integers, Advances in Cryptology - EUROCRYPT 2015, 3-12 (2015), Heidelberg: Springer, Heidelberg · Zbl 1365.94416 · doi:10.1007/978-3-662-46800-5_1
[24] Cheon, J.H., Jeong, J., Lee, C.: An algorithm for CSPR problems and cryptanalysis of the GGH multilinear map without an encoding of zero. In: ANTS (2016) · Zbl 1404.94053
[25] Coron, J-S; Gennaro, R.; Robshaw, M., Zeroizing without low-level zeroes: new MMAP attacks and their limitations, Advances in Cryptology - CRYPTO 2015, 247-266 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94114 · doi:10.1007/978-3-662-47989-6_12
[26] Coron, J-S; Lee, MS; Lepoint, T.; Tibouchi, M.; Robshaw, M.; Katz, J., Cryptanalysis of GGH15 multilinear maps, Advances in Cryptology - CRYPTO 2016, 607-628 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94739 · doi:10.1007/978-3-662-53008-5_21
[27] Fischlin, M.; Herzberg, A.; Bin-Noon, H.; Shulman, H.; Robshaw, M.; Katz, J., Obfuscation combiners, Advances in Cryptology - CRYPTO 2016, 521-550 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94749 · doi:10.1007/978-3-662-53008-5_18
[28] Fischlin, M.; Lehmann, A.; Menezes, A., Security-amplifying combiners for collision-resistant hash functions, Advances in Cryptology - CRYPTO 2007, 224-243 (2007), Heidelberg: Springer, Heidelberg · Zbl 1215.94045 · doi:10.1007/978-3-540-74143-5_13
[29] Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS (2013) · Zbl 1348.94048
[30] Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Fully secure functional encryption without obfuscation. IACR Cryptology ePrint Archive 2014, 666 (2014)
[31] Garg, S.; Ishai, Y.; Srinivasan, A.; Beimel, A.; Dziembowski, S., Two-round MPC: information-theoretic and black-box, Theory of Cryptography, 123-151 (2018), Cham: Springer, Cham · Zbl 1443.94058 · doi:10.1007/978-3-030-03807-6_5
[32] Garg, S., Ishai, Y., Srinivasan, A.: Personal communication (2019)
[33] Garg, S.; Pandey, O.; Srinivasan, A.; Robshaw, M.; Katz, J., Revisiting the cryptographic hardness of finding a nash equilibrium, Advances in Cryptology - CRYPTO 2016, 579-604 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94752 · doi:10.1007/978-3-662-53008-5_20
[34] Garg, S.; Pandey, O.; Srinivasan, A.; Zhandry, M.; Coron, J-S; Nielsen, JB, Breaking the sub-exponential barrier in obfustopia, Advances in Cryptology - EUROCRYPT 2017, 156-181 (2017), Cham: Springer, Cham · Zbl 1394.94932 · doi:10.1007/978-3-319-56617-7_6
[35] Garg, S.; Srinivasan, A.; Nielsen, JB; Rijmen, V., Two-round multiparty secure computation from minimal assumptions, Advances in Cryptology - EUROCRYPT 2018, 468-499 (2018), Cham: Springer, Cham · Zbl 1428.94072 · doi:10.1007/978-3-319-78375-8_16
[36] Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: STOC (2013) · Zbl 1293.68108
[37] Goyal, R.; Hohenberger, S.; Koppula, V.; Waters, B.; Kalai, Y.; Reyzin, L., A generic approach to constructing and proving verifiable random functions, Theory of Cryptography, 537-566 (2017), Cham: Springer, Cham · Zbl 1412.94178 · doi:10.1007/978-3-319-70503-3_18
[38] Harnik, D.; Ishai, Y.; Kushilevitz, E.; Nielsen, JB; Canetti, R., OT-combiners via secure computation, Theory of Cryptography, 393-411 (2008), Heidelberg: Springer, Heidelberg · Zbl 1162.94366 · doi:10.1007/978-3-540-78524-8_22
[39] Harnik, D.; Kilian, J.; Naor, M.; Reingold, O.; Rosen, A.; Cramer, R., On robust combiners for oblivious transfer and other primitives, Advances in Cryptology - EUROCRYPT 2005, 96-113 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94346 · doi:10.1007/11426639_6
[40] Hemenway, B.; Jafargholi, Z.; Ostrovsky, R.; Scafuro, A.; Wichs, D.; Robshaw, M.; Katz, J., Adaptively secure garbled circuits from one-way functions, Advances in Cryptology - CRYPTO 2016, 149-178 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94063 · doi:10.1007/978-3-662-53015-3_6
[41] Hu, Y.; Jia, H.; Fischlin, M.; Coron, J-S, Cryptanalysis of GGH map, Advances in Cryptology - EUROCRYPT 2016, 537-565 (2016), Heidelberg: Springer, Heidelberg · Zbl 1385.94044 · doi:10.1007/978-3-662-49890-3_21
[42] Ishai, Y.; Prabhakaran, M.; Sahai, A.; Wagner, D., Founding cryptography on oblivious transfer – efficiently, Advances in Cryptology - CRYPTO 2008, 572-591 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94037 · doi:10.1007/978-3-540-85174-5_32
[43] Kitagawa, F.; Nishimaki, R.; Tanaka, K.; Nielsen, JB; Rijmen, V., Obfustopia built on secret-key functional encryption, Advances in Cryptology - EUROCRYPT 2018, 603-648 (2018), Cham: Springer, Cham · Zbl 1428.94081 · doi:10.1007/978-3-319-78375-8_20
[44] Komargodski, I.; Segev, G.; Coron, J-S; Nielsen, JB, From minicrypt to obfustopia via private-key functional encryption, Advances in Cryptology - EUROCRYPT 2017, 122-151 (2017), Cham: Springer, Cham · Zbl 1410.94086 · doi:10.1007/978-3-319-56620-7_5
[45] Lin, H.; Fischlin, M.; Coron, J-S, Indistinguishability obfuscation from constant-degree graded encoding schemes, Advances in Cryptology - EUROCRYPT 2016, 28-57 (2016), Heidelberg: Springer, Heidelberg · Zbl 1347.94046 · doi:10.1007/978-3-662-49890-3_2
[46] Lin, H.; Katz, J.; Shacham, H., Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs, Advances in Cryptology - CRYPTO 2017, 599-629 (2017), Cham: Springer, Cham · Zbl 1407.94138 · doi:10.1007/978-3-319-63688-7_20
[47] Lin, H., Matt, C.: Pseudo flawed-smudging generators and their application to indistinguishability obfuscation. IACR Cryptology ePrint Archive 2018, 646 (2018)
[48] Lin, H.; Tessaro, S.; Katz, J.; Shacham, H., Indistinguishability obfuscation from trilinear maps and block-wise local PRGs, Advances in Cryptology - CRYPTO 2017, 630-660 (2017), Cham: Springer, Cham · Zbl 1407.94139 · doi:10.1007/978-3-319-63688-7_21
[49] Lin, H., Vaikuntanathan, V.: Indistinguishability obfuscation from DDH-like assumptions on constant-degree graded encodings. In: FOCS (2016)
[50] Mukherjee, P.; Wichs, D.; Fischlin, M.; Coron, J-S, Two round multiparty computation via multi-key FHE, Advances in Cryptology - EUROCRYPT 2016, 735-763 (2016), Heidelberg: Springer, Heidelberg · Zbl 1351.94060 · doi:10.1007/978-3-662-49896-5_26
[51] O’Neill, A.: Definitional issues in functional encryption. IACR Cryptology ePrint Archive 2010, 556 (2010)
[52] Sahai, A.; Waters, B.; Cramer, R., Fuzzy identity-based encryption, Advances in Cryptology - EUROCRYPT 2005, 457-473 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94355 · doi:10.1007/11426639_27
[53] Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162-167 (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.