Communications in Cryptology IACR CiC

Lattice-based Multi-Authority/Client Attribute-based Encryption for Circuits

Authors

Valerio Cini, Russell W. F. Lai, Ivy K. Y. Woo
Valerio Cini ORCID
NTT Research, USA
cini dot valerio at gmail dot com
Russell W. F. Lai ORCID
Aalto University, Finland
russell dot lai at aalto dot fi
Ivy K. Y. Woo ORCID
Aalto University, Finland
ivy dot woo at aalto dot fi

Abstract

Multi-authority/input attribute-based encryption (MA-/MI-ABE) are multi-party extensions of ABE which enable flavours of decentralised cryptographic access control. This work aims to advance research on multi-party ABE and their lattice-based constructions in several directions:

- We introduce the notion of multi-client (MC-)ABE. This can be seen as an augmentation of MI-ABE with the addition of a ciphertext identity (CID) in the syntax, or a specialisation of multi-client functional encryption (MC-FE) to the ABE setting.

- We adapt the 2-input (2I-)ABE of Agrawal et al. (CRYPTO'22), which is heuristically secure yet without a security proof, into a 2-client (2C-)ABE, and prove it satisfies a variant of very-selective security under the learning with errors (LWE) assumption.

- We extend Wee's ciphertext-policy (CP-)ABE (EUROCRYPT'22) to the MA setting, yielding an MA-ABE. Furthermore, combining techniques in Boneh et al.'s key-policy ABE (EUROCRYPT'14) and our MA-ABE, we construct an MC-ABE. We prove that they satisfy variants of very-selective security under the evasive LWE, tensor LWE, and LWE assumptions.

All our constructions support policies expressed as arbitrary polynomial-size circuits, feature distributed key generation (for MA) and encryption (for 2C/MC), and are proven secure in the random oracle model. Although our constructions only achieve limited security against corrupt authorities/clients, the fully distributed key generation/encryption feature makes them nevertheless non-trivial and meaningful.

Prior to this work, existing MA-ABEs only support up to NC1 policies regardless of their security against corrupt authorities; existing MI-ABEs only support up to constant-many encryptors/clients and do not achieve any security against corrupt encryptors/clients; and MC-ABEs only existed in the form of MC-FEs for linear and quadratic functions.

References

[ABB10]
Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient Lattice (H)IBE in the Standard Model. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 553–572. 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-13190-5_28
[ABG19]
Michel Abdalla, Fabrice Benhamouda, and Romain Gay. From Single-Input to Multi-client Inner-Product Functional Encryption. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 552–582. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34618-8_19
[ABKW19]
Michel Abdalla, Fabrice Benhamouda, Markulf Kohlweiss, and Hendrik Waldner. Decentralizing Inner-Product Functional Encryption. In Dongdai Lin and Kazue Sako, editors, PKC 2019, Part II, volume 11443 of LNCS, pages 128–157. April 2019. Springer, Cham. DOI: 10.1007/978-3-030-17259-6_5
[AG23]
Miguel Ambrona and Romain Gay. Multi-authority ABE for Non-monotonic Access Structures. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part II, volume 13941 of LNCS, pages 306–335. May 2023. Springer, Cham. DOI: 10.1007/978-3-031-31371-4_11
[AGT22]
Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-Input Quadratic Functional Encryption: Stronger Security, Broader Functionality. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 711–740. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22318-1_25
[ARYY23]
Shweta Agrawal, Mélissa Rossi, Anshu Yadav, and Shota Yamada. Constant Input Attribute Based (and Predicate) Encryption from Evasive and Tensor LWE. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part IV, volume 14084 of LNCS, pages 532–564. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38551-3_17
[AYY22]
Shweta Agrawal, Anshu Yadav, and Shota Yamada. Multi-input Attribute Based Encryption and Predicate Encryption. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 590–621. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15802-5_21
[BGG+14]
Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 533–556. May 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-55220-5_30
[BJK+18]
Zvika Brakerski, Aayush Jain, Ilan Komargodski, Alain Passelègue, and Daniel Wichs. Non-trivial Witness Encryption and Null-iO from Standard Assumptions. In Dario Catalano and Roberto De Prisco, editors, SCN 18, volume 11035 of LNCS, pages 425–441. September 2018. Springer, Cham. DOI: 10.1007/978-3-319-98113-0_23
[BLMR13]
Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. Key Homomorphic PRFs and Their Applications. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 410–428. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_23
[BUW24]
Chris Brzuska, Akin Ünal, and Ivy K. Y. Woo. Evasive LWE Assumptions: Definitions, Classes, and Counterexamples. In To appear in ASIACRYPT 2024. 2024. Springer.
[BV22]
Zvika Brakerski and Vinod Vaikuntanathan. Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 28:1–28:20. 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ITCS.2022.28
[CDG+18]
Jérémy Chotard, Edouard Dufour Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Decentralized Multi-Client Functional Encryption for Inner Product. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 703–732. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03329-3_24
[Cha07]
Melissa Chase. Multi-authority Attribute Based Encryption. In Salil P. Vadhan, editor, TCC 2007, volume 4392 of LNCS, pages 515–534. February 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-70936-7_28
[DKW21]
Pratish Datta, Ilan Komargodski, and Brent Waters. Decentralized Multi-authority ABE for DNFs from LWE. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 177–209. October 2021. Springer, Cham. DOI: 10.1007/978-3-030-77870-5_7
[DKW23a]
Pratish Datta, Ilan Komargodski, and Brent Waters. Decentralized Multi-authority ABE for NC${}^1$ from BDH. Journal of Cryptology, 36(2):6, April 2023. DOI: 10.1007/s00145-023-09445-7
[DKW23b]
Pratish Datta, Ilan Komargodski, and Brent Waters. Fully Adaptive Decentralized Multi-Authority ABE. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part III, volume 14006 of LNCS, pages 447–478. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30620-4_15
[DRS04]
Yevgeniy Dodis, Leonid Reyzin, and Adam Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 523–540. May 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24676-3_31
[FFMV23]
Danilo Francati, Daniele Friolo, Giulio Malavolta, and Daniele Venturi. Multi-key and Multi-input Predicate Encryption from Learning with Errors. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part III, volume 14006 of LNCS, pages 573–604. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30620-4_19
[FWW23]
Cody Freitag, Brent Waters, and David J. Wu. How to Use (Plain) Witness Encryption: Registered ABE, Flexible Broadcast, and More. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part IV, volume 14084 of LNCS, pages 498–531. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38551-3_16
[GGG+14]
Shafi Goldwasser, S. Dov Gordon, Vipul Goyal, Abhishek Jain, Jonathan Katz, Feng-Hao Liu, Amit Sahai, Elaine Shi, and Hong-Sheng Zhou. Multi-input Functional Encryption. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 578–602. May 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-55220-5_32
[GM18]
Nicholas Genise and Daniele Micciancio. Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 174–203. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78381-9_7
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 197–206. May 2008. ACM Press. DOI: 10.1145/1374376.1374407
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 75–92. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_5
[Kim19]
Sam Kim. Multi-Authority Attribute-Based Encryption from LWE in the OT Model. Cryptology ePrint Archive, Report 2019/280. 2019.
[LT19]
Benoît Libert and Radu Titiu. Multi-Client Functional Encryption for Linear Functions in the Standard Model from LWE. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 520–551. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34618-8_18
[LW11]
Allison B. Lewko and Brent Waters. Decentralizing Attribute-Based Encryption. In Kenneth G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS, pages 568–588. May 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-20465-4_31
[MP12]
Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 700–718. April 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-29011-4_41
[NPP22]
Ky Nguyen, Duong Hieu Phan, and David Pointcheval. Multi-Client Functional Encryption with Fine-Grained Access Control. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part I, volume 13791 of LNCS, pages 95–125. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22963-3_4
[Tsa22]
Rotem Tsabary. Candidate Witness Encryption from Lattice Techniques. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 535–559. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15802-5_19
[VWW22]
Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. Witness Encryption and Null-IO from Evasive LWE. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part I, volume 13791 of LNCS, pages 195–221. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22963-3_7
[Wee22]
Hoeteck Wee. Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part II, volume 13276 of LNCS, pages 217–241. 2022. Springer, Cham. DOI: 10.1007/978-3-031-07085-3_8
[Wee23]
Hoeteck Wee. Optimal Broadcast Encryption and CP-ABE from Evasive Lattice Assumptions. Cryptology ePrint Archive, Report 2023/906. 2023.
[WFL19]
Zhedong Wang, Xiong Fan, and Feng-Hao Liu. FE for Inner Products and Its Application to Decentralized ABE. In Dongdai Lin and Kazue Sako, editors, PKC 2019, Part II, volume 11443 of LNCS, pages 97–127. April 2019. Springer, Cham. DOI: 10.1007/978-3-030-17259-6_4
[WWW22]
Brent Waters, Hoeteck Wee, and David J. Wu. Multi-authority ABE from Lattices Without Random Oracles. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 651–679. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22318-1_23

PDFPDF Open access

History
Submitted: 2024-04-09
Accepted: 2024-09-02
Published: 2025-01-13
How to cite

Valerio Cini, Russell W. F. Lai, and Ivy K. Y. Woo, Lattice-based Multi-Authority/Client Attribute-based Encryption for Circuits. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ahmpgy4e-.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.