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
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

Dual System Framework in Multilinear Settings and Applications to Fully Secure (Compact) ABE for Unbounded-Size Circuits

Author : Nuttapong Attrapadung

Published in: Public-Key Cryptography – PKC 2017

Publisher: Springer Berlin Heidelberg

Log in

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

search-config
loading …

Abstract

We propose a new generic framework for constructing fully secure attribute based encryption (ABE) in multilinear settings. It is applicable in a generic manner to any predicates. Previous generic frameworks of this kind are given only in bilinear group settings, where applicable predicate classes are limited. Our framework provides an abstraction of dual system paradigms over composite-order graded multilinear encoding schemes in a black-box manner.
As applications, we propose new fully secure ABE systems for general predicates, namely, ABE for circuits. We obtain two schemes for each of key-policy (KP) and ciphertext-policy (CP) variants of ABE. All of our four fully secure schemes can deal with unbounded-size circuits, while enjoy succinctness, meaning that the key and ciphertext sizes are (less than or) proportional to corresponding circuit sizes. In the CP-ABE case, no scheme ever achieves such properties, even when considering selectively secure systems. Furthermore, our second KP-ABE achieves constant-size ciphertexts, whereas our second CP-ABE achieves constant-size keys. Previous ABE systems for circuits are either selectively secure (Gorbunov et al.  STOC’13, Garg et al.  Crypto’13, and subsequent works), or semi-adaptively secure (Brakerski and Vaikuntanathan Crypto’16), or fully-secure but not succinct and restricted to bounded-size circuits (Garg et al.  ePrint 2014/622, and Garg et al.  TCC’16-A).

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
next chapter CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions
Footnotes
1
We do not elaborate the exact number as it is quite tricky to count the number of all Boolean functions that can be computed by unbounded-size bounded-depth circuits.
 
2
When we further restrict to bounded-size circuits, the loss factor is \(2^{\mathsf {poly}(g_{max})}\), where \(g_{max}\) is the maximum circuit size. This is exactly the reduction loss for all the available fully secure CP-ABE via complexity leveraging (see Table 2).
 
3
Our preliminary version [4] has been made available shortly after [26, 27].
 
4
We although still need the subgroup decision assumption required for framework.
 
5
As a caveat, some schemes are plausibly secure in the setting where encodings of zero are not given out. However, in ABE, we will need them for our security proof.
 
6
This form implies that all \(T_{j_1},\ldots ,T_{j_k}\) are pairwise disjoint.
 
7
Here, for a vector \({\varvec{x}}\), the notation ‘\(z \in {\varvec{x}}\)’ means that z is an element in \({\varvec{x}}\).
 
8
We define syntax in such a way that it does not refer to multilinear maps. We do this so that it can accommodate both perfect and computational flavor of security (the former will not refer to mult-maps while the latter will, cf. Sect. 3.2), similarly to [3, 5].
 
9
Or, \( \mathchoice{(1)_{{S_\mathsf {k}}}}{(1)_{{S_\mathsf {k}}}}{(1)_{{S_\mathsf {k}}}}{(1)_{{S_\mathsf {k}}}} \) is computable from \({\varvec{h}}_\mathsf {k}\). This is only for our purpose of dual conversion in Sect. 6.
 
10
It will be used to mask the master-key in our generic scheme in Sect. 3.3, hence the name.
 
11
More precise definitions of these games are given in the full version.
 
12
The multilinear programs \(\mathcal {P}_x\) output from EncC and \(\mathcal {P}_f\) output from EncK are straightforwardly deducible from the respective encodings.
 
13
That is, we use variable t in place of \(s_0\) of the generic construction.
 
14
We refer the definition of \(\mathcal {S}\) to the beginning of this section (Sect. 4).
 
Literature
1.
Albrecht, M.R., Farshim, P., Hofheinz, D., Larraia, E., Paterson, K.G.: Multilinear maps from obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 446–473. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49096-9_​19 CrossRef
2.
Ananth, P., Brakerski, Z., Segev, G., Vaikuntanathan, V.: From selective to adaptive security in functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 657–677. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48000-7_​32 CrossRef
3.
Attrapadung, N.: Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 557–577. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​31 CrossRef
4.
Attrapadung N.: Fully secure and succinct attribute based encryption for circuits from multi-linear maps. Cryptology ePrint Archive: report 2014/772 (2014)
5.
Attrapadung, N.: Dual system encryption framework in prime-order groups via computational pair encodings. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 591–623. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53890-6_​20 CrossRef
6.
Attrapadung, N.: Dual system framework in multilinear settings and applications to fully secure (compact) ABE for unbounded-size circuits. Cryptology ePrint Archive: report 2017/023 (2017). (The full version of this paper)
7.
Attrapadung, N., Libert, B.: Functional encryption for inner product: achieving constant-size ciphertexts with adaptive security or support for negation. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 384–402. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13013-7_​23 CrossRef
8.
Attrapadung, N., Libert, B., Panafieu, E.: Expressive key-policy attribute-based encryption with constant-size ciphertexts. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 90–108. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19379-8_​6 CrossRef
9.
Attrapadung, N., Yamada, S.: Duality in ABE: converting attribute based encryption for dual predicate and dual policy via computational encodings. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 87–105. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-16715-2_​5
10.
Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19379-8_​4 CrossRef
11.
Brakerski, Z., Vaikuntanathan, V.: Circuit-ABE from LWE: unbounded attributes and semi-adaptive security. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 363–384. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53015-3_​13 CrossRef
12.
Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24676-3_​14 CrossRef
13.
Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., Vinayagamurthy, D.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 533–556. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-55220-5_​30 CrossRef
14.
Boneh, D., Gentry, C., Waters, B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​16 CrossRef
15.
16.
Boyen, X. Fan, X., Shi, E.: Adaptively secure fully homomorphic signatures based on lattices. Cryptology ePrint Archive, report 2014/916 (2014)
17.
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). doi:10.​1007/​978-3-662-46800-5_​1
18.
Cheon, J.H., Fouque, P.-A., Lee, C., Minaud, B., Ryu, H.: Cryptanalysis of the New CLT multilinear map over the integers. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 509–536. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​20 CrossRef
19.
Chen, J., Wee, H.: Semi-adaptive Attribute-Based Encryption and Improved Delegation for Boolean Formula. In: Abdalla, M., Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 277–297. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-10879-7_​16
20.
21.
Coron, J.-S., et al.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 247–266. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-47989-6_​12 CrossRef
22.
23.
24.
Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 479–499. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​27 CrossRef
25.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. FOCS 2013, 40–49 (2013)MathSciNetMATH
26.
Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Fully secure attribute based encryption from multilinear maps. Cryptology ePrint Archive: report 2014/622 (2014)
27.
Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Functional encryption without obfuscation. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 480–511. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49099-0_​18 CrossRef
28.
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. STOC 2013, 467–476 (2013)MathSciNetMATH
29.
Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 479–499. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40084-1_​27 CrossRef
30.
Gentry, C., Lewko, A., Sahai, A., Waters, B.: Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption. In: FOCS 2015, pp. 151–170 (2015)
31.
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: STOC, pp. 545–554 (2013)
32.
Goyal, R., Koppula, V., Waters, B.: Semi-adaptive security and bundling functionalities made generic and easy. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 361–388. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53644-5_​14 CrossRef
33.
Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. ACM CCS 2006, 89–98 (2006)
34.
Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-78967-3_​9 CrossRef
35.
Lewko, A., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455–479. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-11799-2_​27 CrossRef
36.
Lewko, A., Waters, B.: New proof methods for attribute-based encryption: achieving full security through selective techniques. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 180–198. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32009-5_​12 CrossRef
37.
Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62–91. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13190-5_​4 CrossRef
38.
Lin, H.: Indistinguishability obfuscation from constant-degree graded encoding schemes. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 28–57. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​2 CrossRef
39.
40.
Okamoto, T., Takashima, K.: Fully secure functional encryption with general relations from the decisional linear assumption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14623-7_​11 CrossRef
41.
Okamoto, T., Takashima, K.: Adaptively attribute-hiding (hierarchical) inner product encryption. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 591–608. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​35 CrossRef
42.
43.
Rouselakis, Y., Waters, B.: Practical constructions and new proof methods for large universe attribute-based encryption. In: ACM CCS 2013, pp. 463–474 (2013)
44.
45.
Takashima, K.: Expressive attribute-based encryption with constant-size ciphertexts from the decisional linear assumption. In: Abdalla, M., Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 298–317. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-10879-7_​17
46.
Valiant, L.G.: Universal circuits (preliminary report). In: STOC 1976, pp. 196–203 (1976)
47.
Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-19379-8_​4 CrossRef
48.
49.
50.
51.
Metadata
Title
Dual System Framework in Multilinear Settings and Applications to Fully Secure (Compact) ABE for Unbounded-Size Circuits
Author
Nuttapong Attrapadung
Copyright Year
2017
Publisher
Springer Berlin Heidelberg
Book
Public-Key Cryptography – PKC 2017

Print ISBN: 978-3-662-54387-0

Electronic ISBN: 978-3-662-54388-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-662-54388-7_1

Premium Partner

    Image Credits