Decentralized Multi-Client Functional Encryption with Strong Security
Authors
Ky Nguyen, David Pointcheval, Robert Schädlich
Ky Nguyen
DIENS, Ecole normale superieure, CNRS, Inria, PSL University, Paris, France
ky dot nguyen at ens dot fr
ky dot nguyen at ens dot fr
David Pointcheval
DIENS, Ecole normale superieure, CNRS, Inria, PSL University, Paris, France
david dot pointcheval at ens dot fr
david dot pointcheval at ens dot fr
Robert Schädlich
DIENS, Ecole normale superieure, CNRS, Inria, PSL University, Paris, France
robert dot schaedlich at ens dot fr
robert dot schaedlich at ens dot fr
Abstract
Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple plaintext-inputs to be given for evaluation to the function embedded in the functional decryption key, defined by multiple parameter-inputs. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys. Tags can be used in the ciphertexts and the keys to specify which inputs can be combined together. As any encryption scheme, DMCFE provides privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process.
In this paper, we provide new proof techniques to analyze a new concrete construction of function-hiding DMCFE for inner products, with strong security guarantees: the adversary can adaptively query multiple challenge ciphertexts and multiple challenge keys, with unbounded repetitions of the same tags in the ciphertext-queries and a fixed polynomially-large number of repetitions of the same tags in the key-queries. Previous constructions were proven secure in the selective setting only.
References
[ABDP15]
Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple Functional Encryption Schemes for Inner Products. In Jonathan Katz, editor, PKC 2015, volume 9020 of LNCS, pages 733–751. 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46447-2_33
[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, Heidelberg. 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, Heidelberg. DOI: 10.1007/978-3-030-17259-6_5
[ACF+18]
Michel Abdalla, Dario Catalano, Dario Fiore, Romain Gay, and Bogdan Ursu. Multi-Input Functional Encryption for Inner Products: Function-Hiding Realizations and Constructions Without Pairings. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 597–627. August 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-96884-1_20
[ACGU20]
Michel Abdalla, Dario Catalano, Romain Gay, and Bogdan Ursu. Inner-Product Functional Encryption with Fine-Grained Access Control. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 467–497. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64840-4_16
[AGT21a]
Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-input Quadratic Functional Encryption from Pairings. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 208–238, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84259-8_8
[AGT21b]
Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-Party Functional Encryption. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 224–255. November 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-90453-1_8
[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, Heidelberg. DOI: 10.1007/978-3-031-22318-1_25
[AJ15]
Prabhanjan Ananth and Abhishek Jain. Indistinguishability Obfuscation from Compact Functional Encryption. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 308–326. August 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-47989-6_15
[ALdP11]
Nuttapong Attrapadung, Benoît Libert, and Elie de Panafieu. Expressive Key-Policy Attribute-Based Encryption with Constant-Size Ciphertexts. In Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi, editors, PKC 2011, volume 6571 of LNCS, pages 90–108. March 2011. Springer, Heidelberg. DOI: 10.1007/978-3-642-19379-8_6
[ALS16]
Shweta Agrawal, Benoît Libert, and Damien Stehlé. Fully Secure Functional Encryption for Inner Products, from Standard Assumptions. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 333–362. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53015-3_12
[AS17]
Prabhanjan Ananth and Amit Sahai. Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation from Degree-5 Multilinear Maps. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, pages 152–181. 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-56620-7_6
[ATY23]
Shweta Agrawal, Junichi Tomida, and Anshu Yadav. Attribute-Based Multi-input FE (and More) for Attribute-Weighted Sums. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part IV, volume 14084 of LNCS, pages 464–497. August 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-38551-3_15
[BBL17]
Fabrice Benhamouda, Florian Bourse, and Helger Lipmaa. CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions. In Serge Fehr, editor, PKC 2017, Part II, volume 10175 of LNCS, pages 36–66. March 2017. Springer, Heidelberg. DOI: 10.1007/978-3-662-54388-7_2
[BCFG17]
Carmen Elisabetta Zaira Baltico, Dario Catalano, Dario Fiore, and Romain Gay. Practical Functional Encryption for Quadratic Functions with Applications to Predicate Encryption. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 67–98. August 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-63688-7_3
[BF01]
Dan Boneh and Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 213–229. August 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44647-8_13
[BJK15]
Allison Bishop, Abhishek Jain, and Lucas Kowalczyk. Function-Hiding Inner Product Encryption. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, pages 470–491. 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-48797-6_20
[BR06]
Mihir Bellare and Phillip Rogaway. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 409–426. 2006. Springer, Heidelberg. DOI: 10.1007/11761679_25
[BSW11]
Dan Boneh, Amit Sahai, and Brent Waters. Functional Encryption: Definitions and Challenges. In Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS, pages 253–273. March 2011. Springer, Heidelberg. DOI: 10.1007/978-3-642-19571-6_16
[BV15]
Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability Obfuscation from Functional Encryption. In Venkatesan Guruswami, editor, 56th FOCS, pages 171–190. October 2015. IEEE Computer Society Press. DOI: 10.1109/FOCS.2015.20
[CDG+18a]
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, Heidelberg. DOI: 10.1007/978-3-030-03329-3_24
[CDG+18b]
Jérémy Chotard, Edouard Dufour Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Multi-Client Functional Encryption with Repetition for Inner Product. https://eprint.iacr.org/2018/1021. Cryptology ePrint Archive, Report 2018/1021. 2018.
[CDSG+20]
Jérémy Chotard, Edouard Dufour-Sans, Romain Gay, Duong Hieu Phan, and David Pointcheval. Dynamic Decentralized Functional Encryption. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 747–775. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56784-2_25
[CLL+13]
Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, and Hoeteck Wee. Shorter IBE and Signatures via Asymmetric Pairings. In Michel Abdalla and Tanja Lange, editors, PAIRING 2012, volume 7708 of LNCS, pages 122–140. May 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-36334-4_8
[CLT18]
Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker. Practical Fully Secure Unrestricted Inner Product Functional Encryption Modulo p. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 733–764. December 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03329-3_25
[Coc01]
Clifford Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues. In Bahram Honary, editor, 8th IMA International Conference on Cryptography and Coding, volume 2260 of LNCS, pages 360–363. December 2001. Springer, Heidelberg. DOI: 10.1007/3-540-45325-3_32
[DDM16]
Pratish Datta, Ratna Dutta, and Sourav Mukhopadhyay. Functional Encryption for Inner Product with Full Function Privacy. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016, Part I, volume 9614 of LNCS, pages 164–195. March 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49384-7_7
[DOT18]
Pratish Datta, Tatsuaki Okamoto, and Junichi Tomida. Full-Hiding (Unbounded) Multi-input Inner Product Functional Encryption from the $k$-Linear Assumption. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 245–277. March 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-76581-5_9
[EHK+13]
Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, and Jorge Villar. An Algebraic Framework for Diffie-Hellman Assumptions. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 129–147. August 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-40084-1_8
[Gay20]
Romain Gay. A New Paradigm for Public-Key Functional Encryption for Degree-2 Polynomials. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part I, volume 12110 of LNCS, pages 95–120. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45374-9_4
[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, Heidelberg. DOI: 10.1007/978-3-642-55220-5_32
[GKL+13]
S. Dov Gordon, Jonathan Katz, Feng-Hao Liu, Elaine Shi, and Hong-Sheng Zhou. Multi-Input Functional Encryption. https://eprint.iacr.org/2013/774. Cryptology ePrint Archive, Report 2013/774. 2013.
[GPSW06]
Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters. Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 89–98. 2006. ACM Press. DOI: 10.1145/1180405.1180418 Available as Cryptology ePrint Archive Report 2006/309
[GVW15]
Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate Encryption for Circuits from LWE. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 503–523. August 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-48000-7_25
[JR17]
Charanjit S. Jutla and Arnab Roy. Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces. Journal of Cryptology, 30(4):1116–1156, October 2017. DOI: 10.1007/s00145-016-9243-7
[KKS19]
Sungwook Kim, Jinsu Kim, and Jae Hong Seo. A new approach to practical function-private inner product encryption. Theoretical Computer Science, 783:22–40, 2019. DOI: 10.1016/J.TCS.2019.03.016
[KLM+18]
Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J. Wu. Function-Hiding Inner Product Encryption Is Practical. In Dario Catalano and Roberto De Prisco, editors, SCN 18, volume 11035 of LNCS, pages 544–562. September 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-98113-0_29
[Lin17]
Huijia Lin. Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 599–629. August 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-63688-7_20
[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, Heidelberg. DOI: 10.1007/978-3-030-34618-8_18
[LV16]
Huijia Lin and Vinod Vaikuntanathan. Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. In Irit Dinur, editor, 57th FOCS, pages 11–20. October 2016. IEEE Computer Society Press. DOI: 10.1109/FOCS.2016.11
[LW10]
Allison B. Lewko and Brent Waters. New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 455–479. February 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-11799-2_27
[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, Heidelberg. DOI: 10.1007/978-3-031-22963-3_4
[NPP23]
Ky Nguyen, Duong Hieu Phan, and David Pointcheval. Optimal Security Notion for Decentralized Multi-Client Functional Encryption. In Mehdi Tibouchi and Xiaofeng Wang, editors, ACNS 23, Part II, volume 13906 of LNCS, pages 336–365. June 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-33491-7_13
[NPS24]
Ky Nguyen, David Pointcheval, and Robert Schädlich. Decentralized Multi-Client Functional Encryption with Strong Security. Cryptology ePrint Archive, Paper 2024/764. 2024.
[OSW07]
Rafail Ostrovsky, Amit Sahai, and Brent Waters. Attribute-based encryption with non-monotonic access structures. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 195–203. October 2007. ACM Press. DOI: 10.1145/1315245.1315270
[OT10]
Tatsuaki Okamoto and Katsuyuki Takashima. Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 191–208. August 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-14623-7_11
[OT12a]
Tatsuaki Okamoto and Katsuyuki Takashima. Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 591–608. April 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-29011-4_35
[OT12b]
Tatsuaki Okamoto and Katsuyuki Takashima. Fully Secure Unbounded Inner-Product and Attribute-Based Encryption. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS, pages 349–366. December 2012. Springer, Heidelberg. DOI: 10.1007/978-3-642-34961-4_22
[Sha84]
Adi Shamir. Identity-Based Cryptosystems and Signature Schemes. In G. R. Blakley and David Chaum, editors, CRYPTO'84, volume 196 of LNCS, pages 47–53. August 1984. Springer, Heidelberg. DOI: 10.1007/3-540-39568-7_5
[SV23]
Elaine Shi and Nikhil Vanjani. Multi-Client Inner Product Encryption: Function-Hiding Instantiations Without Random Oracles. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part I, volume 13940 of LNCS, pages 622–651. May 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-31368-4_22
[SW05]
Amit Sahai and Brent R. Waters. Fuzzy Identity-Based Encryption. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 457–473. May 2005. Springer, Heidelberg. DOI: 10.1007/11426639_27
[TAO16]
Junichi Tomida, Masayuki Abe, and Tatsuaki Okamoto. Efficient Functional Encryption for Inner-Product Values with Full-Hiding Security. In Matt Bishop and Anderson C. A. Nascimento, editors, ISC 2016, volume 9866 of LNCS, pages 408–425. September 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-45871-7_24
[Tom19]
Junichi Tomida. Tightly Secure Inner Product Functional Encryption: Multi-input and Function-Hiding Constructions. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 459–488. December 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-34618-8_16
[Tom20]
Junichi Tomida. Tightly secure inner product functional encryption: Multi-input and function-hiding constructions. Theoretical Computer Science, 833:56–86, 2020. DOI: 10.1016/J.TCS.2020.05.008
[{\"U}na20]
Akin Ünal. Impossibility Results for Lattice-Based Functional Encryption Schemes. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 169–199. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45721-1_7
[Wat09]
Brent Waters. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 619–636. August 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-03356-8_36
PDF
History
Submitted: 2024-01-08
Accepted: 2024-06-04
Published: 2024-07-08
Accepted: 2024-06-04
Published: 2024-07-08
How to cite
Ky Nguyen, David Pointcheval, and Robert Schädlich, Decentralized Multi-Client Functional Encryption with Strong Security. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/andkp2fgx.
Citations
There is at least one citation.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.