Fully Collusion Resistant Traceable Identity-Based Inner Product Functional Encryption
Authors
Subhranil Dutta, Tapas Pal, Amit Kumar Singh, Sourav Mukhopadhyay
Subhranil Dutta
University of St. Gallen, Switzerland
subhranil dot dutta at unisg dot ch
subhranil dot dutta at unisg dot ch
Tapas Pal
Karlsruhe Institute of Technology, KASTEL SRL, Germany
tapas dot pal at kit dot edu
tapas dot pal at kit dot edu
Amit Kumar Singh
Siksha `O' Anusandhan (Deemed to be) University, India
amitmintu01991 at gmail dot com
amitmintu01991 at gmail dot com
Sourav Mukhopadhyay
Indian Institute of Technology Kharagpur, India
sourav at maths dot iitkgp dot ac dot in
sourav at maths dot iitkgp dot ac dot in
Keywords:
embedded identity
traitor tracing
inner product functional encryption
identity-based inner product functional encryption
Abstract
We present the first fully collusion resistant traceable functional encryption (TFE) scheme for identity-based inner product FE (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity TIBIPFE (EI-TIBIPFE) where secret keys and ciphertexts are computed for vectors, and decryption recovers the inner product between the vectors given the key and ciphertext are associated with the same group identity. Additionally, a secret key corresponds to a user identity for the purpose of tracing. Suppose some of the users linked to a particular group team up and create a pirate decoder that is capable of decrypting the content of the group, then the tracing algorithm extracts the identities of the dishonest users' given black-box access to the decoder. Previously, such schemes were designed for usual public key encryptions. In this work, we construct a fully collusion resistant EI-TIBIPFE scheme from pairings in the standard model. The ciphertext size of our scheme grows sub-linearly with the number of users in the system. We achieve many-target security of tracing, namely the adversary is allowed to ask for multiple secret keys corresponding to many functions, which notably solves an open problem raised by Do, Phan, and Pointcheval [CT-RSA'2020].
References
[ABCP15]
Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. Simple Functional Encryption Schemes for Inner Products. In Jonathan Katz, editor, Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings, volume 9020 of LNCS, pages 733–751. 2015. Springer.
[ABP+17]
Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehlé, and Shota Yamada. Efficient Public Trace and Revoke from Standard Assumptions: Extended Abstract. In Bhavani Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 2277–2293. 2017. ACM.
[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, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III, volume 12493 of LNCS, pages 467–497. 2020. Springer.
[ADM+07]
Michel Abdalla, Alexander W. Dent, John Malone-Lee, Gregory Neven, Duong Hieu Phan, and Nigel P. Smart. Identity-Based Traitor Tracing. In Tatsuaki Okamoto and Xiaoyun Wang, editors, Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, April 16-20, 2007, Proceedings, volume 4450 of LNCS, pages 361–376. 2007. Springer.
[AGT21]
Shweta Agrawal, Rishab Goyal, and Junichi Tomida. Multi-Party Functional Encryption. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II, volume 13043 of LNCS, pages 224–255. 2021. Springer.
[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, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, volume 9816 of LNCS, pages 333–362. 2016. Springer.
[BB04]
Dan Boneh and Xavier Boyen. Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, volume 3027 of LNCS, pages 223–238. 2004. Springer.
[BBG05]
Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of LNCS, pages 440–456. 2005. Springer.
[BF99]
Dan Boneh and Matthew K. Franklin. An Efficient Public Key Traitor Tracing Scheme. In Michael J. Wiener, editor, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of LNCS, pages 338–353. 1999. Springer.
[BR09]
Mihir Bellare and Thomas Ristenpart. Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings, volume 5479 of LNCS, pages 407–424. 2009. Springer.
[BSW06]
Dan Boneh, Amit Sahai, and Brent Waters. Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of LNCS, pages 573–592. 2006. Springer.
[BSW11]
Dan Boneh, Amit Sahai, and Brent Waters. Functional Encryption: Definitions and Challenges. In Yuval Ishai, editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings, volume 6597 of LNCS, pages 253–273. 2011. Springer.
[BW06]
Dan Boneh and Brent Waters. A fully collusion resistant broadcast, trace, and revoke system. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006, pages 211–220. 2006. ACM.
[BZ14]
Dan Boneh and Mark Zhandry. Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of LNCS, pages 480–499. 2014. Springer.
[CFN94]
Benny Chor, Amos Fiat, and Moni Naor. Tracing Traitors. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of LNCS, pages 257–270. 1994. Springer.
[CPP05]
Hervé Chabanne, Duong Hieu Phan, and David Pointcheval. Public Traceability in Traitor Tracing Schemes. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of LNCS, pages 542–558. 2005. Springer.
[CVW+18]
Yilei Chen, Vinod Vaikuntanathan, Brent Waters, Hoeteck Wee, and Daniel Wichs. Traitor-Tracing from LWE Made Simple and Attribute-Based. In Amos Beimel and Stefan Dziembowski, editors, Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, volume 11240 of LNCS, pages 341–369. 2018. Springer.
[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, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of LNCS, pages 177–209. 2021. Springer.
[DPP20]
Xuan Thanh Do, Duong Hieu Phan, and David Pointcheval. Traceable Inner Product Functional Encryption. In Stanislaw Jarecki, editor, Topics in Cryptology - CT-RSA 2020 - The Cryptographers' Track at the RSA Conference 2020, San Francisco, CA, USA, February 24-28, 2020, Proceedings, volume 12006 of LNCS, pages 564–585. 2020. Springer.
[Fre10]
David Mandell Freeman. Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of LNCS, pages 44–61. 2010. Springer.
[FT01]
Amos Fiat and Tamir Tassa. Dynamic Traitor Tracing. J. Cryptol., 14(3):211–223, 2001.
[GKRW18]
Rishab Goyal, Venkata Koppula, Andrew Russell, and Brent Waters. Risky Traitor Tracing and New Differential Privacy Negative Results. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, volume 10991 of LNCS, pages 467–497. 2018. Springer.
[GKW18]
Rishab Goyal, Venkata Koppula, and Brent Waters. Collusion resistant traitor tracing from learning with errors. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 660–670. 2018. ACM.
[GKW19]
Rishab Goyal, Venkata Koppula, and Brent Waters. New Approaches to Traitor Tracing with Embedded Identities. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II, volume 11892 of LNCS, pages 149–179. 2019. Springer.
[GMS12]
Fuchun Guo, Yi Mu, and Willy Susilo. Identity-Based Traitor Tracing with Short Private Key and Short Ciphertext. In Sara Foresti, Moti Yung, and Fabio Martinelli, editors, Computer Security - ESORICS 2012 - 17th European Symposium on Research in Computer Security, Pisa, Italy, September 10-12, 2012. Proceedings, volume 7459 of LNCS, pages 609–626. 2012. Springer.
[KD98]
Kaoru Kurosawa and Yvo Desmedt. Optimum Traitor Tracing and Asymmetric Schemes. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of LNCS, pages 145–157. 1998. Springer.
[KY02a]
Aggelos Kiayias and Moti Yung. Traitor Tracing with Constant Transmission Rate. In Lars R. Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of LNCS, pages 450–465. 2002. Springer.
[KY02b]
Aggelos Kiayias and Moti Yung. Traitor Tracing with Constant Transmission Rate. In Lars R. Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of LNCS, pages 450–465. 2002. Springer.
[KY02c]
Kaoru Kurosawa and Takuya Yoshida. Linear Code Implies Public-Key Traitor Tracing. In David Naccache and Pascal Paillier, editors, Public Key Cryptography, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France, February 12-14, 2002, Proceedings, volume 2274 of LNCS, pages 172–187. 2002. Springer.
[LAWH22]
Fucai Luo, Saif M. Al-Kuwari, Haiyan Wang, and Weihong Han. Generic Construction of Trace-and-Revoke Inner Product Functional Encryption. In Vijayalakshmi Atluri, Roberto Di Pietro, Christian Damsgaard Jensen, and Weizhi Meng, editors, Computer Security - ESORICS 2022 - 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26-30, 2022, Proceedings, Part I, volume 13554 of LNCS, pages 259–282. 2022. Springer.
[LPSS14]
San Ling, Duong Hieu Phan, Damien Stehlé, and Ron Steinfeld. Hardness of k-LWE and Applications in Traitor Tracing. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of LNCS, pages 315–334. 2014. Springer.
[NWZ16]
Ryo Nishimaki, Daniel Wichs, and Mark Zhandry. Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, volume 9666 of LNCS, pages 388–419. 2016. Springer.
[PT11]
Duong Hieu Phan and Viet Cuong Trinh. Identity-Based Trace and Revoke Schemes. In Xavier Boyen and Xiaofeng Chen, editors, Provable Security - 5th International Conference, ProvSec 2011, Xi'an, China, October 16-18, 2011. Proceedings, volume 6980 of LNCS, pages 204–221. 2011. Springer.
[SP19]
Edouard Dufour Sans and David Pointcheval. Unbounded Inner-Product Functional Encryption with Succinct Keys. In Robert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, and Moti Yung, editors, Applied Cryptography and Network Security - 17th International Conference, ACNS 2019, Bogota, Colombia, June 5-7, 2019, Proceedings, volume 11464 of LNCS, pages 426–441. 2019. Springer.
[SSW01]
Jessica Staddon, Douglas R. Stinson, and Ruizhong Wei. Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory, 47(3):1042–1049, 2001.
[SW98]
Douglas R. Stinson and Ruizhong Wei. Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes. SIAM J. Discret. Math., 11(1):41–53, 1998.
[TT01]
Wen-Guey Tzeng and Zhi-Jia Tzeng. A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares. In Kwangjo Kim, editor, Public Key Cryptography, 4th International Workshop on Practice and Theory in Public Key Cryptography, PKC 2001, Cheju Island, Korea, February 13-15, 2001, Proceedings, volume 1992 of LNCS, pages 207–224. 2001. Springer.
[Wat05]
Brent Waters. Efficient Identity-Based Encryption Without Random Oracles. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of LNCS, pages 114–127. 2005. Springer.
[Zha21]
Mark Zhandry. White Box Traitor Tracing. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part IV, volume 12828 of LNCS, pages 303–333. 2021. Springer.
PDF
History
Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Subhranil Dutta, Tapas Pal, Amit Kumar Singh, and Sourav Mukhopadhyay, Fully Collusion Resistant Traceable Identity-Based Inner Product Functional Encryption. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/av4fe0zn4.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.