Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 9/2023

27-05-2023

On the security of functional encryption in the generic group model

Authors: Hyung Tae Lee, Jae Hong Seo

Published in: Designs, Codes and Cryptography | Issue 9/2023

Login to get access

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

search-config
loading …

Abstract

In the context of functional encryption (FE), a weak security notion called selective security, which enforces the adversary to complete a challenge prior to seeing the system parameters, is used to argue in favor of the security of proposed cryptosystems. These results are often considered as an intermediate step to design adaptively secure cryptosystems. In fact, selectively secure FE schemes play a role of more than an intermediate step in many cases. If we restrict our attention to group-based constructions, it is not surprising to find several selectively secure FE schemes such that no successful adaptive adversary is found yet and/or it is also believed that no adaptive adversary will be found in practice even in the future. In this paper, we aim at clarifying these beliefs rigorously in the ideal model, called generic group model (GGM). First, we refine the definitions of the GGM and the security notions for FE scheme for clarification. Second, we formalize a group-based FE scheme with some conditions and then show that for any group-based FE scheme satisfying these conditions we can reduce from its selective security in the standard model to adaptive security in the GGM, in particular, regardless of the functionality of FE schemes. Our reduction is applicable to many existing selectively secure FE schemes with various functionalities, e.g., the FE scheme for quadratic functions of Baltico et al. (CRYPTO, 2017), the predicate encryption scheme of Katz et al. (J Cryptol in 26:191–224, 2013), and Boneh and Boyen’s identity-based encryption scheme (EUROCRYPT 2004).
previous article On the algebraic immunity—resiliency trade-off, implications for Goldreich’s pseudorandom generator
Footnotes
1
Contrary to the exponential reduction leverage [15], our reduction works in polynomial-time.
 
2
We follow Shoup’s representation of the GGM. Note that there are several papers following Maurer’s representation of the GGM and both representations are in fact equivalent [39, 46].
 
3
We can further generalize this model by hiding the order of the group, but the model in which the group order is known is sufficient for our purposes.
 
4
We assume that \({\mathcal {M}}_{\texttt {ENC}}\) is announced to the adversary at the very beginning of the interaction.
 
5
To the best of our knowledge, almost all elliptic curve based FE schemes generate public parameters with sufficient entropy for super-polynomial uncertainty.
 
6
Note that since we separate the group order from the group description, \(\mathbb {Z}_q\) is a parameter-independent message space.
 
7
Even before fixing the group description, we can predetermine the message space that will be mapped to group elements.
 
8
In contrast to usual definitions for indistinguishability, we have modified \({\mathcal {A}}\) to begin with querying \(\textsf {mpk}\), in order to make the definition fit better to our generalization of interactions in the GGM, which will be presented in Lemma 2.
 
9
\(M_0^*\) and \(M_1^*\) may be the same with respect to FE schemes. For example, \(M_0^*=M_1^*\) in the selective-id security of IBE scheme [15].
 
10
Here, all the mentioned ‘polynomial’ means a polynomial in \(\log p\), where p is the order of the base groups \(\mathbb {G}_1,\mathbb {G}_2\), and \(\mathbb {G}_T\).
 
11
A random function is an ideal object that cannot be expressed as a closed-form expression. We manage \({{\widehat{\sigma }}}_i\) like a random oracle in the sense that for each evaluation, we choose a random function value and keep it in some internal list to reuse for the same input. Note that \({{\widehat{\sigma }}}_i\) is used only by the challenger in the poly-faking lemma.
 
12
That is, the statistical distance of two distributions is negligible in \(\log p\).
 
Literature
1.
Abdalla M., Bourse F., De Caro A.: Simple functional encryption schemes for inner products. In: PKC 2015. LNCS vol. 9020, 733–751 (2015).
2.
Abdolmaleki B., Baghery K., Lipmaa H., Zajac M.: A subversion-resistant SNARK. In: ASIACRYPT 2017 Part III. LNCS vol. 10626, 3–33 (2017).
3.
Abe M., Fuchsbauer G., Groth J., Haralambiev K., Ohkubo M.: Structure-preserving signatures and commitments to group elements. In: CRYPTO 2010. LNCS vol. 6223, 209–236 (2010).
4.
Agrawal S., Libert B., Stehlé D.: Fully secure functional encryption for inner products, from standard assumptions. In: CRYPTO (3) 2016. LNCS vol. 9816, 333–362 (2016).
5.
Albrecht M..R., Bai S., Ducas L.: A subfield lattice attack on overstretched NTRU assumptions-cryptanalysis of some FHE and graded encoding schemes. In: CRYPTO (1) 2016 vol. 9814, 153–178 (2016).
6.
Ambrona M., Barthe G., Schmidt B.: Automated unbounded analysis of cryptographic constructions in the generic group model. In: EUROCRYPT (2) 2016. LNCS vol. 9666, 822–851 (2016).
7.
Ambrona M., Barthe G., Gay R., Wee H.: Attribute-based encryption in the generic group model: automated proofs and new constructions. In: ACM CCS 2017, LNCS, pp. 647–664. Springer (2017)
8.
Ananth P., Brakerski Z., Segev G., Vaikuntanathan V.: From selective to adaptive security in functional encryption. In: CRYPTO (2) 2015. LNCS vol. 9216, 657–677 (2015).
9.
Ananth, P., Jain, A., Sahai, A.: Robust transforming combiners from indistinguishability obfuscation to functional encryption. In: EUROCRYPT (1) 2017, LNCS, vol. 10210, pp. 91–121. Springer (2017)
10.
Babai L., Szemeredi E.: On the complexity of matrix group problems. In: FOCS 1984, pp. 229–240 (1984)
11.
Baltico C.E.Z., Catalano D., Fiore D., Gay R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: CRYPTO(1) 2017. LNCS vol. 10401, pp. 67–98 (2017).
12.
Barthe G., Fagerholm E., Fiore D., Mitchell J..C., Scedrov A., Schmidt B.: Automated analysis of cryptographic assumptions in generic group models. In: CRYPTO (1) 2014. LNCS vol. 8616, 95–112 (2014).
13.
Bellare M., Fuchsbauer G., Scafuro A.: NIZKs with an untrusted CRS: security in the face of parameter subversion. In: ASIACRYPT 2016 Part II, LNCS, vol. 10032, pp. 777–804. Springer (2016)
14.
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM CCS 1993, pp. 62–73 (1993)
15.
Boneh D., Boyen X.: Efficient selective-id identity based encryption without random oracles. In: EUROCRYPT 2004. LNCS vol. 3027, 223–238 (2004).
16.
17.
Boneh D., Lipton R.J.: Algorithms for black-box fields and their application to cryptography. In: CRYPTO 1996. LNCS vol. 1109, 283–297 (1996).
18.
Boneh D., Boyen X., Goh E.: Hierarchical identity based encryption with constant size ciphertexts. In: EUROCRYPT 2005. LNCS vol. 3494, 440–456 (2005).
19.
Boneh D., Goh E., Nissim K.: Evaluating 2-DNF formulas on ciphertexts. In: TCC 2005, LNCS, vol. 3378. Springer (2005).
20.
Boneh D., Sahai A., Waters B.: Functional encryption: a new vision for public-key cryptography. Commun. ACM 55(11), 56–64 (2012).CrossRef
21.
Boyen X.: The uber-assumption family (invited talk). In: Pairing 2008, LNCS, vol. 5209, 39–56 (2008).
22.
Boyen X., Waters B.: Anonymous hierarchical identity-based encryption (without random oracles). In: CRYPTO 2006. LNCS vol. 4117, 290–307 (2006).
23.
Boyle E., Chung K.M., Pass R.: On extractability obfuscation. In: TCC 2014. LNCS vol. 8349, 52–73 (2014).
24.
Canetti R., Halevi S., Katz J.: Chosen-ciphertext security from identity-based encryption. In: EUROCRYPT 2004. LNCS vol. 3027, 207–222 (2004).
25.
26.
Cheon J.H., Han K., Lee C., Ryu H., Stehlé D.: Cryptanalysis of the multilinear map over the integers. In: EUROCRYPT (1) 2015. LNCS vol. 9056, 3–12 (2015).
27.
Cheon J.H., Fouque P..A., Lee C., Minaud B., Ryu H.: Cryptanalysis of the new CLT multilinear map over the integers. In: EUROCRYPT (1) 2016. LNCS vol. 9665, 509–536 (2016).
28.
Cheon J.H., Hhan M., Kim J., Lee C.: Cryptanalyses of branching program obfuscations over GGH13 multilinear map from the NTRU problem. In: CRYPTO (3) 2018. LNCS vol. 10993, 184–210 (2018).
29.
Coron J.S., Lee M.S., Lepoint T., Tibouchi M.: Cryptanalysis of GGH15 multilinear maps. In: CRYPTO (2) 2016. LNCS vol. 9815, 607–628 (2016).
30.
ElGamal T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: G.R. Blakely, D. Chaum (eds.) CRYPTO 1984. LNCS vol. 196, 10–18 (1984).
31.
Escala A., Herold G., Kiltz E., Ràfols C., Villar J.: An algebraic framework for Diffie–Hellman assumptions. J. Cryptol. 30, 242–288 (2017) Springer.MathSciNetCrossRefMATH
32.
Fernando R., Rasmussen P.M.R., Sahai A.: Preventing CLT attacks on obfuscation with linear overhead. In: ASIACRYPT (3) 2017. LNCS vol. 10626, 242–271 (2017).
33.
Fouque P.A., Joux A., Tibouchi M.: Injective encodings to elliptic curves. In: ACISP 2013. LNCS vol. 7959, 203–218 (2013).
34.
Freeman D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: EUROCRYPT 2010. LNCS vol. 6110, 44–61 (2010).
35.
Garg, S., Gentry C., Halevi S.: Candidate multilinear maps from ideal lattices. In: EUROCRYPT 2013. LNCS vol. 7881, pp. 1–17 (2013).
36.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013, pp. 40–49. IEEE Computer Society (2013)
37.
38.
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM CCS 2006, pp. 89–98
39.
Jager T., Schwenk J.: On the equivalence of generic group models. In: ProvSec 2008. LNCS vol. 5324, 200–209 (2008).
40.
Katz J., Sahai A., Waters B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. J. Cryptol. 26, 191–224 (2013).MathSciNetCrossRefMATH
41.
Kim S., Lewi K., Mandal A., Montgomery H.W., Roy A., Wu D.J.: Function-hiding inner product encryption is practical. In: SCN 2018. LNCS vol. 11035, 544–562 (2018).
42.
Lewko A.B., Waters B.: Unbounded HIBE and attribute-based encryption. In: EUROCRYPT 2011. LNCS vol. 6632, 547–567 (2011).
43.
Lindell Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: EUROCRYPT 2011. LNCS vol. 6632, 446–466 (2011).
44.
Maurer U.M.: Abstract models of computation in cryptography. In: IMA Int. Conf. LNCS vol. 3796, 1–12 (2005).
45.
Maurer U.M., Wolf S.: Diffie–Hellman oracles. In: CRYPTO 1996. LNCS vol. 1109, 268–282 (1996).
46.
47.
48.
Nechaev V.I.: Complexity of a determinate algorithm for the discrete logarithm. In: Mathematical Notes, 1994, vol. 55, pp. 165–172. Translated from Maternaticheskie Zametki, 55(2):91–101, 1994 (1994)
49.
Ostrovsky R., Sahai A., Waters B.: Attribute-based encryption with non-monotonic access structures. In: ACM CCS 2007, pp. 195–203. ACM (2007)
50.
Rouselakis Y., Waters B.: Practical constructions and new proof methods for large universe attribute-based encryption. In: ACM CCS 2013, pp. 463–474
51.
Sahai A., Ananth P.: Projective arithmetic functional encryption and indistinguishability obfuscation from degree-5 multilinear maps. In: EUROCRYPT (1) 2017. LNCS vol. 10210, 152–181 (2017).
52.
Sahai A., Waters B.: Fuzzy identity-based encryption. In: EUROCRYPT 2005. LNCS vol. 3494, 457–473 (2005).
53.
Sans, E.D., Gay, R., Pointcheval, D.: Reading in the dark: classifying encrypted digits with functional encryption. In: ePrint Archive: Report 2018/206 (2018)
54.
55.
Seo J.H., Kobayashi T., Ohkubo M., Suzuki K.: Anonymous hierarchical identity-based encryption with constant size ciphertexts. In: G. Tsudik, S. Jarecki (eds.) PKC 2009. LNCS vol. 5443, pp. 215–234 (2009).
56.
Shoup V.: Lower bounds for discrete logarithms and related problems. In: EUROCRYPT 1997, LNCS vol. 1233, 256–266 (1997).
57.
Waters B.: Efficient identity-based encryption without random oracles. In: EUROCRYPT 2005. LNCS vol. 3494, pp. 114–127 (2005).
58.
Waters B.: A punctured programming approach to adaptively secure functional encryption. In: CRYPTO 2015. LNCS vol. 9216, pp. 678–697 (2015).
Metadata
Title
On the security of functional encryption in the generic group model
Authors
Hyung Tae Lee
Jae Hong Seo
Publication date
27-05-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 9/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01237-1

Other articles of this Issue 9/2023

Designs, Codes and Cryptography 9/2023 Go to the issue

EditorialNotes

Obituary of Professor Zhexian Wan

OriginalPaper

(Compact) Adaptively secure FE for attribute-weighted sums from k-Lin

OriginalPaper

Hiding the input-size in multi-party private set intersection

OriginalPaper

The proportion of non-degenerate complementary subspaces in classical spaces

OriginalPaper

Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework

OriginalPaper

Several families of irreducible constacyclic and cyclic codes

Premium Partner

    Image Credits