Top

Designs, Codes and Cryptography

Published in:

03-06-2021

Tag-based ABE in prime-order groups via pair encoding

Author: Atsushi Takayasu

Published in: Designs, Codes and Cryptography | Issue 8/2021

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

search-config

AI-assisted search

Off

Abstract

Predicate/pair encodings are simple frameworks for designing attribute-based encryption (\(\textsf {ABE}\)) for complex predicates, with pair encodings being able to handle more complex predicates. Thus far, several generic constructions of prime-order \(\textsf {ABE}\) schemes have been proposed with these encodings. Chen, Gay, and Wee (\(\textsf {CGW}\)) (Eurocrypt’15) and Chen and Gong \((\textsf {CG})\) (Asiacrypt’17) proposed generic constructions with predicate encodings with a trade-off in efficiency. In particular, the former construction (\(\textsf {CGW}\) \(\textsf {ABE}\)) has the shorter secret keys, whereas the latter construction (\(\textsf {CG}\) \(\textsf {ABE}\)) has the shorter master public keys and ciphertexts. Moreover, \(\textsf {CG}\) \(\textsf {ABE}\) requires three pairing operations during decryption, while \(\textsf {CGW}\) \(\textsf {ABE}\) requires four. Agrawal and Chase (\(\textsf {AC}\)) (TCC’16) proposed a generic construction with pair encodings that is an extension of \(\textsf {CGW}\) \(\textsf {ABE}\) and can handle more complex predicates. Specifically, if pair encoding schemes satisfy perfect security (resp. relaxed perfect security), then \(\textsf {AC}\) \(\textsf {ABE}\) satisfies full security (resp. semi-adaptive security) from the standard k-linear assumption. However, there is no extension of \(\textsf {CG}\) \(\textsf {ABE}\) with pair encodings. In this paper, we construct this extension. As with the trade-off between \(\textsf {CGW}\) \(\textsf {ABE}\) and \(\textsf {CG}\) \(\textsf {ABE}\), our proposed \(\textsf {ABE}\) has shorter master public keys and ciphertexts and larger secret keys, requires less pairing operations during decryption than \(\textsf {AC}\) \(\textsf {ABE}\). Furthermore, as with \(\textsf {AC}\) \(\textsf {ABE}\), our proposed \(\textsf {ABE}\) satisfies full security (resp. semi-adaptive security) if pair encoding schemes satisfy perfect security (resp. relaxed perfect security) from the standard k-linear assumption. As an application, we propose a ciphertext-policy \(\textsf {ABE}\) scheme for non-monotone span programs with compact ciphertexts satisfying semi-adaptive security.

previous article Breaking tweakable enciphering schemes using Simon’s algorithm

next article Adaptively secure lattice-based revocable IBE in the QROM: compact parameters, tight security, and anonymity

Available only for authorised users

The definition of semi-adaptive security lies between selective security and full security but is rather close to selective security [26].

Although there are other known schemes with small universe, we only list known schemes with large universe.

In [12], Blazy and Mukherjee also studied CCA security; however, we can covert our \(\textsf {ABE}\) scheme to achieve CCA security based on [9, 14, 34‐38, 47, 48].

Agrawal S., Chase M.: A study of pair encodings: Predicate encryption in prime order groups. In: Kushilevitz E, Malkin T (eds.) Theory of Cryptography—13th International Conference, TCC 2016-A, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9563, pp. 259–288. Springer (2016).

Agrawal S., Chase M.: Simplifying design and analysis of complex predicate encryption schemes. In: Coron J., Nielsen J.B. (eds.) Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part I, Lecture Notes in Computer Science, vol. 10210, pp. 627–656 (2017).

Agrawal S., Maitra M., Yamada S.: Attribute based encryption (and more) for nondeterministic finite automata from LWE. In: Boldyreva A., Micciancio D. (eds.) Advances in Cryptology—CRYPTO 2019—39th Annual International Cryptology Conference, Proceedings, Part II, Lecture Notes in Computer Science, vol. 11693, pp. 765–797. Springer (2019).

Agrawal S., Maitra M., Yamada S.: Attribute based encryption for deterministic finite automata from DLIN. IACR Cryptol. ePrint Arch. 2019, 645 (2019).MATH

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.) Advances in Cryptology—EUROCRYPT 2014—33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Lecture Notes in Computer Science, vol. 8441, pp. 557–577. Springer (2014).

Attrapadung N.: Dual system encryption framework in prime-order groups via computational pair encodings. In: Cheon J.H., Takagi T. (eds.) Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part II, Lecture Notes in Computer Science, vol. 10032, pp. 591–623 (2016).

Attrapadung N.: Unbounded dynamic predicate compositions in attribute-based encryption. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part I, Lecture Notes in Computer Science, vol. 11476, pp. 34–67. Springer (2019).

Attrapadung N., Hanaoka G., Yamada S.: Conversions among several classes of predicate encryption and applications to ABE with various compactness tradeoffs. In: Iwata T., Cheon J.H. (eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I, Lecture Notes in Computer Science, vol. 9452, pp. 575–601. Springer (2015).

Attrapadung N., Tomida J.: Unbounded dynamic predicate compositions in ABE from standard assumptions. In: Moriai S., Wang H. (eds.) Advances in Cryptology—ASIACRYPT 2020—26th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part III, Lecture Notes in Computer Science, vol. 12493, pp. 405–436. Springer (2020).

10.

Beimel A.: Secret-sharing schemes: A survey. In: Chee Y.M., Guo Z., Ling S., Shao F., Tang Y., Wang H., Xing C. (eds.) Coding and Cryptology—Third International Workshop, IWCC 2011, Proceedings, Lecture Notes in Computer Science, vol. 6639, pp. 11–46. Springer (2011).

11.

Bethencourt J., Sahai A., Waters B.: Ciphertext-policy attribute-based encryption. In: 2007 IEEE Symposium on Security and Privacy (S&P 2007), pp. 321–334. IEEE Computer Society (2007).

12.

Blazy O., Mukherjee S.: CCA-secure ABE using tag and pair encoding. In: Bhargavan K., Oswald E., Prabhakaran M. (eds.) Progress in Cryptology—INDOCRYPT 2020—21st International Conference on Cryptology in India, Proceedings, Lecture Notes in Computer Science, vol. 12578, pp. 691–714. Springer (2020).

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.) Advances in Cryptology—EUROCRYPT 2014—33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 8441, pp. 533–556. Springer (2014).

14.

Chatterjee S., Mukherjee S., Pandit T.: CCA-secure predicate encryption from pair encoding in prime order groups: generic and efficient. In: Patra A., Smart N.P. (eds.) Progress in Cryptology—INDOCRYPT 2017—18th International Conference on Cryptology in India, Proceedings, Lecture Notes in Computer Science, vol. 10698, pp. 85–106. Springer (2017).

15.

Chen J., Gay R., Wee H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 9057, pp. 595–624. Springer (2015).

16.

Chen J., Gong J.: ABE with tag made easy—concise framework and new instantiations in prime-order groups. In: Takagi T., Peyrin T. (eds.) Advances in Cryptology—ASIACRYPT 2017—23rd International Conference on the Theory and Applications of Cryptology and Information Security. Proceedings, Part II, Lecture Notes in Computer Science, vol. 10625, pp. 35–65. Springer (2017).

17.

Chen J., Gong J., Kowalczyk L., Wee H.: Unbounded ABE via bilinear entropy expansion, revisited. In: Nielsen J.B., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part I, Lecture Notes in Computer Science, vol. 10820, pp. 503–534. Springer (2018).

18.

Chen J., Wee H.: Fully, (almost) tightly secure IBE and dual system groups. In: Canetti R., Garay J.A. (eds.) Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference. Proceedings, Part II, Lecture Notes in Computer Science, vol. 8043, pp. 435–460. Springer (2013).

19.

Chen J., Wee H.: Dual system groups and its applications—compact HIBE and more. IACR Cryptol. ePrint Arch. 2014, 265 (2014).

20.

Cheung L., Newport C.C.: Provably secure ciphertext policy ABE. In: Ning P., di Vimercati S.D.C., Syverson P.F. (eds.) Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, pp. 456–465. ACM (2007).

21.

Escala A., Herold G., Kiltz E., Ràfols C., Villar J.L.: An algebraic framework for Diffie-Hellman assumptions. J. Cryptol. 30(1), 242–288 (2017).MathSciNetCrossRef

22.

Gong J., Waters B., Wee H.: ABE for DFA from k-lin. In: Boldyreva A., Micciancio D. (eds.) Advances in Cryptology—CRYPTO 2019—39th Annual International Cryptology Conference, Proceedings, Part II, Lecture Notes in Computer Science, vol. 11693, pp. 732–764. Springer (2019).

23.

Gong J., Wee H.: Adaptively secure ABE for DFA from k-lin and more. In: Canteaut A., Ishai Y. (eds.) 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 III, Lecture Notes in Computer Science, vol. 12107, pp. 278–308. Springer (2020).

24.

Gorbunov S., Vaikuntanathan V., Wee H.: Attribute-based encryption for circuits. J. ACM 62(6), 45 (2015).MathSciNetCrossRef

25.

Gorbunov S., Vaikuntanathan V., Wee H.: Predicate encryption for circuits from LWE. In: Gennaro R., Robshaw M. (eds.) Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Lecture Notes in Computer Science, vol. 9216, pp. 503–523. Springer (2015).

26.

Goyal R., Koppula V., Waters B.: Semi-adaptive security and bundling functionalities made generic and easy. In: Hirt M., Smith A.D. (eds.) Theory of Cryptography—14th International Conference, TCC 2016-B, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9986, pp. 361–388 (2016).

27.

Goyal V., Pandey O., Sahai A., Waters B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Juels A., Wright R.N., di Vimercati S.D.C. (eds.) Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, pp. 89–98. ACM (2006).

28.

Jutla C.S., Roy A.: Shorter quasi-adaptive NIZK proofs for linear subspaces. J. Cryptol. 30(4), 1116–1156 (2017).MathSciNetCrossRef

29.

Kowalczyk L., Wee H.: Compact adaptively secure ABE for \({{\sf nc}}^1\) from k-lin. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part I, Lecture Notes in Computer Science, vol. 11476, pp. 3–33. Springer (2019).

30.

Lewko A.B., Okamoto T., Sahai A., Takashima K., Waters B.: Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In: Gilbert H. (ed.) Advances in Cryptology—EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Lecture Notes in Computer Science, vol. 6110, pp. 62–91. Springer (2010).

31.

Lewko A.B., Waters B.: Unbounded HIBE and attribute-based encryption. In: Paterson K.G. (ed.) Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Proceedings, Lecture Notes in Computer Science, vol. 6632, pp. 547–567. Springer (2011).

32.

Lewko A.B., Waters B.: New proof methods for attribute-based encryption: achieving full security through selective techniques. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology—CRYPTO 2012—32nd Annual Cryptology Conference, Proceedings, Lecture Notes in Computer Science, vol. 7417, pp. 180–198. Springer (2012).

33.

Lin H., Luo J.: Compact adaptively secure ABE from k-lin: Beyond nc\({}^{\text{1}}\) and towards NL. In: Canteaut A., Ishai Y. (eds.) 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 III, Lecture Notes in Computer Science, vol. 12107, pp. 247–277. Springer (2020).

34.

Lin H., Luo J.: Succinct and adaptively secure ABE for ABP from k-lin. In: Moriai S., Wang H. (eds.) Advances in Cryptology—ASIACRYPT 2020—26th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part III, Lecture Notes in Computer Science, vol. 12493, pp. 437–466. Springer (2020).

35.

Nandi M., Pandit T.: Generic conversions from CPA to CCA secure functional encryption. IACR Cryptol. ePrint Arch. 2015, 457 (2015).

36.

Nandi M., Pandit T.: On the power of pair encodings: frameworks for predicate cryptographic primitives. IACR Cryptol. ePrint Arch. 2015, 955 (2015).

37.

Nandi M., Pandit T.: Verifiability-based conversion from CPA to CCA-secure predicate encryption. Appl. Algebra Eng. Commun. Comput. 29(1), 77–102 (2018).MathSciNetCrossRef

38.

Nandi M., Pandit T.: Delegation-based conversion from CPA to CCA-secure predicate encryption. Int. J. Appl. Cryptogr. 4(1), 16–35 (2020).MathSciNetCrossRef

39.

Okamoto T., Takashima K.: Fully secure unbounded inner-product and attribute-based encryption. In: Wang X., Sako K. (eds.) Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science, vol. 7658, pp. 349–366. Springer (2012).

40.

Okamoto T., Takashima K.: Fully secure functional encryption with a large class of relations from the decisional linear assumption. J. Cryptol. 32(4), 1491–1573 (2019).MathSciNetCrossRef

41.

Ostrovsky R., Sahai A., Waters B.: Attribute-based encryption with non-monotonic access structures. In: Ning P., di Vimercati S.D.C., Syverson P.F. (eds.) Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, pp. 195–203. ACM (2007).

42.

Rouselakis Y., Waters B.: Practical constructions and new proof methods for large universe attribute-based encryption. In: Sadeghi A., Gligor V.D., Yung M. (eds.) 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, 2013, pp. 463–474. ACM (2013).

43.

Sahai A., Waters B.: Fuzzy identity-based encryption. In: Cramer R. (ed.) Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 3494, pp. 457–473. Springer (2005).

44.

Waters B.: Dual system encryption: Realizing fully secure IBE and HIBE under simple assumptions. In: Halevi S. (ed.) Advances in Cryptology—CRYPTO 2009, 29th Annual International Cryptology Conference. Proceedings, Lecture Notes in Computer Science, vol. 5677, pp. 619–636. Springer (2009).

45.

Waters B.: Functional encryption for regular languages. In: Safavi-Naini R., Canetti R. (eds.) Advances in Cryptology—CRYPTO 2012—32nd Annual Cryptology Conference, Proceedings, Lecture Notes in Computer Science, vol. 7417, pp. 218–235. Springer (2012).

46.

Wee H.: Dual system encryption via predicate encodings. In: Lindell Y. (ed.) Theory of Cryptography—11th Theory of Cryptography Conference, TCC 2014, Lecture Notes in Computer Science, vol. 8349, pp. 616–637. Springer (2014).

47.

Yamada S., Attrapadung N., Hanaoka G., Kunihiro N.: Generic constructions for chosen-ciphertext secure attribute based encryption. In: Catalano D., Fazio N., Gennaro R., Nicolosi A. (eds.) Public Key Cryptography—PKC 2011 - 14th International Conference on Practice and Theory in Public Key Cryptography, Proceedings, Lecture Notes in Computer Science, vol. 6571, pp. 71–89. Springer (2011).

48.

Yamada S., Attrapadung N., Santoso B., Schuldt J.C.N., Hanaoka G., Kunihiro N.: Verifiable predicate encryption and applications to CCA security and anonymous predicate authentication. In: Fischlin M., Buchmann J., Manulis M. (eds.) Public Key Cryptography—PKC 2012—15th International Conference on Practice and Theory in Public Key Cryptography, Proceedings, Lecture Notes in Computer Science, vol. 7293, pp. 243–261. Springer (2012).

Title: Tag-based ABE in prime-order groups via pair encoding
Author: Atsushi Takayasu
Publication date: 03-06-2021
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 8/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00894-4

Springer Professional

Tag-based ABE in prime-order groups via pair encoding

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 8/2021

Adaptively secure lattice-based revocable IBE in the QROM: compact parameters, tight security, and anonymity

Hamming weight distributions of multi-twisted codes over finite fields

Correction to: Good polynomials for optimal LRC of low locality

A construction for circulant type dropout designs

Breaking tweakable enciphering schemes using Simon’s algorithm

Scattered subspaces and related codes

Premium Partner