Top

Designs, Codes and Cryptography

Published in:

09-09-2023

Generic constructions of master-key KDM secure attribute-based encryption

Authors: Jiaxin Pan, Chen Qian, Benedikt Wagner

Published in: Designs, Codes and Cryptography | Issue 1/2024

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

search-config

AI-assisted search

Off

Abstract

Master-key key-dependent message (mKDM) security is a strong security notion for attribute-based encryption (ABE) schemes, which has been investigated in recent years. This line of research was started with identity-based encryption (IBE; Garg, Gay, and Hajiabadi, PKC 2020) and then was extended to (more general) ABE (Feng, Gong, and Chen, PKC 2021). Both these constructions are based on dual system techniques which crucially rely on pairings. How to construct mKDM secure ABEs without pairings or even generically was an open problem. In this paper, we propose two generic constructions of mKDM secure ABE from an ABE secure against chosen-plaintext attacks in the random oracle model (ROM) and standard model. In the ROM, our construction is very efficient, and it gives rise to the first mKDM secure ABE from lattices. Our construction in the standard model requires indistinguishability obfuscation, but it shows that, even in the standard model, mKDM security can be achieved generically, and it is not limited to dual-system-based techniques.

previous article BBB security for 5-round even-Mansour-based key-alternating Feistel ciphers

next article Nonsingular hypercubes and nonintersecting hyperboloids

Here, \(\lambda \) is the security parameter.

We do not explicitly define the circuit class for which \({\textsf{iO}} \) works. It is implicitly given in the construction and proof, see circuits \(\textsf{C}_{{\textsf{mpk}},{\textsf{x}},\textsf{m}}\) in Fig. 17 and \(\textsf{C}_{{\textsf{mpk}},{\textsf{x}},{\textsf{ct}} _f,{\textsf{sk}} _{\textsf{x}} ''}\) in Fig. 18.

Attrapadung N., Hanaoka G., Yamada S.: A framework for identity-based encryption with almost tight security. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT 2015, Part I, volume 9452 of LNCS, pp. 521–549. Springer, Heidelberg (2015).

Ajtai M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99–108. ACM Press (1996).

Ajtai M.: Generating hard instances of the short basis problem. In: Wiedermann J., van Emde Boas P., Nielsen M. (eds.) ICALP 99, volume 1644 of LNCS, pp. 1–9. Springer, Heidelberg (1999).

Alperin-Sheriff J., Peikert C.: Circular and KDM security for identity-based encryption. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012, vol. 7293, pp. 334–352. LNCS. Springer, Heidelberg (2012).

Banaszczyk W.: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296(1), 625–635 (1993).MathSciNetCrossRef

Boneh D., Franklin M.K.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) CRYPTO 2001, vol. 2139, pp. 213–229. LNCS. Springer, Heidelberg (2001).CrossRef

Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S.P., Yang K.: On the (im)possibility of obfuscating programs. In: Kilian J. (ed.) CRYPTO 2001, vol. 2139, pp. 1–18. LNCS. Springer, Heidelberg (2001).CrossRef

Brakerski Z., Langlois A., Peikert C., Regev O., Stehlé D.: Classical hardness of learning with errors. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press (2013).

Black J., Rogaway P., Shrimpton T.: Encryption-scheme security in the presence of key-dependent messages. In: Nyberg K., Heys H.M. (eds.) SAC 2002, vol. 2595, pp. 62–75. LNCS. Springer, Heidelberg (2003).

10.

Bitansky N., Vaikuntanathan V.: A note on perfect correctness by derandomization. In: Coron J.-S., Nielsen J.B. (eds) EUROCRYPT 2017, Part II, volume 10211 of LNCS, pp 592–606. Springer, Heidelberg (2017).

11.

Camenisch J., Chandran N., Shoup V.: A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In: Joux A. (ed.) EUROCRYPT 2009, vol. 5479, pp. 351–368. LNCS. Springer, Heidelberg (2009).CrossRef

12.

Cash D., Hofheinz D., Kiltz E., Peikert C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert H. (ed.) EUROCRYPT 2010, volume 6110 of LNCS, pp. 523–552. Springer, Heidelberg (2010).

13.

Chen Y., Zhang J., Deng Y., Chang J.: KDM security for identity-based encryption: constructions and separations. Cryptology ePrint Archive, Report 2016/1020 (2016). https://eprint.iacr.org/2016/1020.

14.

ElGamal T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley G.R., Chaum D. (eds) CRYPTO’84, volume 196 of LNCS, pp. 10–18. Springer, Heidelberg (1984).

15.

Feng S., Gong J., Chen J.: Master-key KDM-secure ABE via predicate encoding. In: Garay J. (ed.) PKC 2021, Part I, volume 12710 of LNCS, pp. 543–572. Springer, Heidelberg (2021).

16.

Fujisaki E., Okamoto T.: How to enhance the security of public-key encryption at minimum cost. In: Imai H., Zheng Y. (eds.) PKC’99, vol. 1560, pp. 53–68. LNCS. Springer, Heidelberg (1999).

17.

Gong J., Dong X., Chen J., Cao Z.: Efficient IBE with tight reduction to standard assumption in the multi-challenge setting. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part II, volume 10032 of LNCS, pp. 624–654. Springer, Heidelberg (2016).

18.

Gentry C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press (2009).

19.

Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS, pp. 40–49. IEEE Computer Society Press (2013).

20.

Garg S., Gay R., Hajiabadi M.: Master-key KDM-secure IBE from pairings. In: Kiayias A., Kohlweiss M., Wallden P., Zikas V. (eds.) PKC 2020, Part I, volume 12110 of LNCS, pp. 123–152. Springer, Heidelberg (2020).

21.

Gay R., Hofheinz D., Kohl L., Pan J.: More efficient (almost) tightly secure structure-preserving signatures. In: Nielsen J.B., Rijmen V. (eds.) EUROCRYPT 2018, Part II, volume 10821 of LNCS, pp. 230–258. Springer, Heidelberg (2018).

22.

Galindo D., Herranz J., Villar J.L.: Identity-based encryption with master key-dependent message security and leakage-resilience. In: Foresti S., Yung M., Martinelli F. (eds.) ESORICS 2012, vol. 7459, pp. 627–642. LNCS. Springer, Heidelberg (2012).

23.

Groth J., Ostrovsky R., Sahai A.: New techniques for noninteractive zero-knowledge. J. ACM (JACM) 59(3), 1–35 (2012).MathSciNetCrossRef

24.

Gay R., Pass R.: Indistinguishability obfuscation from circular security. In: Khuller S., Williams V.V. (eds.) STOC’21, pp. 736–749. ACM (2021).

25.

Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. Cryptology ePrint Archive, Report 2007/432 (2007). https://eprint.iacr.org/2007/432.

26.

Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner R.E., Dwork C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press (2008).

27.

Groth J.: Simulation-sound NIZK proofs for a practical language and constant size group signatures. In: Lai X., Chen K. (eds.) ASIACRYPT 2006, vol. 4284, pp. 444–459. LNCS. Springer, Heidelberg (2006).CrossRef

28.

Groth J., Sahai A.: Efficient non-interactive proof systems for bilinear groups. In: Smart N.P. (ed.) EUROCRYPT 2008, vol. 4965, pp. 415–432. LNCS. Springer, Heidelberg (2008).CrossRef

29.

Hofheinz D., Koch J., Striecks C.: Identity-based encryption with (almost) tight security in the multi-instance, multi-ciphertext setting. In: Katz J. (ed.) PKC 2015, volume 9020 of LNCS, pp. 799–822. Springer, Heidelberg (2015).

30.

Jain A., Lin H., Sahai A.: Indistinguishability obfuscation from well-founded assumptions. In: Khuller S., Williams V.V. (eds.) STOC’21, pp. 60–73. ACM (2021).

31.

Kitagawa F., Matsuda T., Hanaoka G., Tanaka K.: On the key dependent message security of the Fujisaki-Okamoto constructions. In: Cheng C.-M., Chung K.-M., Persiano G., Yang B.-Y. (eds.) PKC 2016, Part I, volume 9614 of LNCS, pp. 99–129. Springer, Heidelberg (2016).

32.

Kitagawa F., Tanaka K.: Key dependent message security and receiver selective opening security for identity-based encryption. In: Abdalla M., Dahab R. (eds.) PKC 2018, Part I, volume 10769 of LNCS, pp. 32–61. Springer, Heidelberg (2018).

33.

Katz J., Wang N.: Efficiency improvements for signature schemes with tight security reductions. In: Jajodia S., Atluri V., Jaeger T. (eds.) ACM CCS 2003, pp. 155–164. ACM Press (2003).

34.

Katsumata S., Yamada S., Yamakawa T.: Tighter security proofs for GPV-IBE in the quantum random oracle model. In: Peyrin T., Galbraith S. (eds.) ASIACRYPT 2018, Part II, volume 11273 of LNCS, pp. 253–282. Springer, Heidelberg (2018).

35.

Lewko A.B., Waters B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio D. (ed.) TCC 2010, vol. 5978, pp. 455–479. LNCS. Springer, Heidelberg (2010).

36.

Marcedone A., Pass R., Shelat A.: Bounded KDM security from iO and OWF. In: Zikas V., De Prisco R. (eds.) SCN 16, volume 9841 of LNCS, pp. 571–586. Springer, Heidelberg (2016).

37.

Micciancio D, Regev O: Worst-case to average-case reductions based on Gaussian measures. In: 45th FOCS, pp. 372–381. IEEE Computer Society Press (2004).

38.

Naor M., Yung M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: 22nd ACM STOC, pp. 427–437. ACM Press (1990).

39.

Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher M. (ed.) 41st ACM STOC, pp. 333–342. ACM Press (2009).

40.

Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow H.N., Fagin R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005).

41.

Tsabary R.: Fully secure attribute-based encryption for t-CNF from LWE. In: Boldyreva A., Micciancio D. (eds.) CRYPTO 2019, Part I, volume 11692 of LNCS, pp. 62–85. Springer, Heidelberg (2019).

42.

Waters B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi S. (ed.) CRYPTO 2009, vol. 5677, pp. 619–636. LNCS. Springer, Heidelberg (2009).CrossRef

Title: Generic constructions of master-key KDM secure attribute-based encryption
Authors: Jiaxin Pan
Chen Qian
Benedikt Wagner
Publication date: 09-09-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 1/2024
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01296-4

Springer Professional

Generic constructions of master-key KDM secure attribute-based encryption

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 1/2024

Towards a Gröbner-free approach to coding

BBB security for 5-round even-Mansour-based key-alternating Feistel ciphers

Minimal and optimal binary codes obtained using -construction over the non-unital ring I

Nonsingular hypercubes and nonintersecting hyperboloids

The properties and the error-correcting pair for lengthened GRS codes

Uniqueness of an association scheme related to the Witt design on 11 points

Premium Partner