Abstract
This paper presents the first generic black-box construction of registered attribute-based encryption (Reg-ABE) via predicate encoding [TCC’14]. The generic scheme is based on k-Lin assumption in the prime-order bilinear group and implies the following concrete schemes that improve existing results:
-
the first Reg-ABE scheme for span program in the prime-order group; prior work uses composite-order group;
-
the first Reg-ABE scheme for zero inner-product predicate from k-Lin assumption; prior work relies on generic group model (GGM);
-
the first Reg-ABE scheme for arithmetic branching program (ABP) which has not been achieved previously.
Technically, we follow the blueprint of Hohenberger et al. [EUROCRYPT’23] but start from the prime-order dual-system ABE by Chen et al. [EUROCRYPT’15], which transforms a predicate encoding into an ABE. The proof follows the dual-system method in the context of Reg-ABE: we conceptually consider helper keys as secret keys; furthermore, malicious public keys are handled via pairing-based quasi-adaptive non-interactive zero-knowledge argument by Kiltz and Wee [EUROCRYPT’15].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Let \(\textbf{w}=(w_1,\ldots ,w_n)\). With the same substitution \(w_i\in \mathbb {Z}_N\mapsto \textbf{W}_i\in \mathbb {Z}_p^{(k+1)\times (k+1)}\) and
$$ [sw_i]_1 \mapsto [\textbf{s}\textbf{A}\textbf{W}_i]_1,\quad [rw_i]_2 \mapsto [\textbf{W}_i\textbf{B}\textbf{r}^\top ]_2, $$we have
$$\begin{aligned} {} & {} {[s\textbf{w}]_1} = [sw_1\Vert \ldots \Vert sw_n]_1 = [\textbf{s}\textbf{A}\textbf{W}_1\Vert \cdots \Vert \textbf{s}\textbf{A}\textbf{W}_n]_1 = [\textbf{s}\textbf{A}(\textbf{W}_1\Vert \cdots \Vert \textbf{W}_n)]_1 \\ {} & {} {[r\textbf{w}]_2} = [rw_1\Vert \ldots \Vert rw_n]_2 = [\textbf{W}_1\textbf{B}\textbf{r}^\top \Vert \cdots \Vert \textbf{W}_n\textbf{B}\textbf{r}^\top ]_2 = [(\textbf{W}_1\Vert \cdots \Vert \textbf{W}_n)(\textbf{I}_n\otimes \textbf{B}\textbf{r}^\top )]_2 \end{aligned}$$where we obtain \(\textbf{W}=(\textbf{W}_1\Vert \cdots \Vert \textbf{W}_n)\in \mathbb {Z}_p^{(k+1)\times (k+1)n}\).
References
Abdalla, M., Catalano, D., Gay, R., Ursu, B.: Inner-product functional encryption with fine-grained access control. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12493, pp. 467–497. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_16
Ambrona, M., Barthe, G., Schmidt, B.: Generic transformations of predicate encodings: constructions and applications. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 36–66. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_2
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). https://doi.org/10.1007/978-3-642-55220-5_31
Bellare, M., Hoang, V.T., Rogaway, P.: Foundations of garbled circuits. In: Yu, T., Danezis, G., Gligor, V.D. (eds.) ACM CCS 2012, pp. 784–796. ACM Press (2012)
Chen, J., Gay, R., Wee, H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 595–624. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_20
Cong, K., Eldefrawy, K., Smart, N.P.: Optimizing registration based encryption. IACR Cryptol. ePrint Arch., p. 499 (2021)
Döttling, N., Kolonelos, D., Lai, R.W.F., Lin, C., Malavolta, G., Rahimi, A.: Efficient laconic cryptography from learning with errors. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. Part III, vol. 14006 of LNCS, pp. 417–446. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_14
Escala, A., Herold, G., Kiltz, E., Ràfols, C., Villar, J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 129–147. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_8
Francati, D., Friolo, D., Maitra, M., Malavolta, G., Rahimi, A., Venturi, D.: Registered (inner-product) functional encryption. Cryptology ePrint Archive, Paper 2023/395 (2023). https://eprint.iacr.org/2023/395
Freitag, C., Waters, B., Wu, D.J.: How to use (plain) witness encryption: registered ABE, flexible broadcast, and more. Cryptology ePrint Archive, Paper 2023/812 (2023). https://eprint.iacr.org/2023/812
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)
Garg, S., Gentry, G., Sahai, A., Waters, B.: Witness encryption and its applications. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 467–476. ACM Press (2013)
Garg, S., Hajiabadi, M., Mahmoody, M., Rahimi, A.: Registration-based encryption: removing private-key generator from IBE. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11239, pp. 689–718. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03807-6_25
Garg, S., Hajiabadi, M., Mahmoody, M., Rahimi, A., Sekar, S.: Registration-based encryption from standard assumptions. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 63–93. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_3
Gentry, C., Waters, B.: Adaptive security in broadcast encryption systems (with short ciphertexts). In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 171–188. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_10
Glaeser, N., Kolonelos, D., Malavolta, G., Rahimi, A.: Efficient registration-based encryption. Cryptology ePrint Archive, Report 2022/1505 (2022).https://eprint.iacr.org/2022/1505
Gong, J., Waters, B., Wee, H.: ABE for DFA from \(k\)-Lin. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 732–764. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_25
Gong, J., Wee, H.: Adaptively secure ABE for DFA from \(k\)-Lin and more. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 278–308. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_10
González, A., Hevia, A., Ràfols, C.: QA-NIZK arguments in asymmetric groups: new tools and new constructions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 605–629. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_25
Goyal, R., Vusirikala, S.: Verifiable registration-based encryption. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12170, pp. 621–651. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_21
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., De Capitani di Vimercati, S. (eds.) ACM CCS 2006, pp. 89–98. ACM Press (2006). Available as Cryptology ePrint Archive Report 2006/309
Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_24
Hohenberger, S., George, L., Waters, B., David, J.W.: Registered attribute-based encryption. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14006, pp. 511–542. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_17
Ishai, Y., Wee, H.: Partial garbling schemes and their applications. Cryptology ePrint Archive, Paper 2014/995 (2014). https://eprint.iacr.org/2014/995
Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from LPN over \(\mathbb{F} _p\), DLIN, and PRGs in \({NC}^0\). In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part I, vol. 13275, pp. 670–699. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-06944-4_23
Jutla, C.S., Roy, A.: Shorter quasi-adaptive NIZK proofs for linear subspaces. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 1–20. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_1
Kiltz, E., Wee, H.: Quasi-adaptive NIZK for linear subspaces revisited. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 101–128. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_4
Kolonelos, D., Malavolta, G., Wee, H.: Distributed broadcast encryption from bilinear groups. Cryptology ePrint Archive, Paper 2023/874 (2023).https://eprint.iacr.org/2023/874
Kowalczyk, L., Wee, H.: Compact adaptively secure ABE for \(\sf NC^1\) from \(k\)-Lin. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 3–33. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_1
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). https://doi.org/10.1007/978-3-642-13190-5_4
Libert, B., Peters, T., Joye, M., Yung, M.: Compactly hiding linear spans - tightly secure constant-size simulation-sound QA-NIZK proofs and applications. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 681–707. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_28
Lin, H., Luo, J.: Compact adaptively secure ABE from \(k\)-Lin: beyond \(\sf NC^1\) and towards \(\sf NL\). In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 247–277. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_9
Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27
Vaikuntanathan, V., Wee, H., Wichs, D.: Witness encryption and null-IO from evasive LWE. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13791, pp. 195–221. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22963-3_7
Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_36
Wee, H.: Dual system encryption via predicate encodings. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 616–637. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_26
Yao, A.C.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November 1982, pp. 80–91. IEEE Computer Society (1982)
Acknowledgement
We want to thank anonymous reviewers from Asiacrypt 2023 for their insightful comments and Hoeteck Wee for his encouragement! This work is partially supported by National Natural Science Foundation of China (62002120), Shanghai Rising-Star Program (22QA1403800), Innovation Program of Shanghai Municipal Education Commission (2021-01-07-00-08-E00101) and the “Digital Silk Road” Shanghai International Joint Lab of Trustworthy Intelligent Software (22510750100).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Zhu, Z., Zhang, K., Gong, J., Qian, H. (2023). Registered ABE via Predicate Encodings. In: Guo, J., Steinfeld, R. (eds) Advances in Cryptology – ASIACRYPT 2023. ASIACRYPT 2023. Lecture Notes in Computer Science, vol 14442. Springer, Singapore. https://doi.org/10.1007/978-981-99-8733-7_3
Download citation
DOI: https://doi.org/10.1007/978-981-99-8733-7_3
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-99-8732-0
Online ISBN: 978-981-99-8733-7
eBook Packages: Computer ScienceComputer Science (R0)