Threshold full-grained proxy re-encryption for all circuits of polynomial sizes

Abstract

In this paper, we introduce a new primitive called (t,N)-Threshold Full-Grained Proxy Re-Encryption (ThFPRE). With a (t,N)-ThFPRE scheme, t honest proxies can collaboratively transform an encryption of m intended for delegator A into another ciphertext encrypting a function value of m intended for delegatee B. In this way, delegator A has flexible control over the information shared with B. We define the \mathsf{H}\mathsf{R}\mathsf{A} security for (t,N)-ThFPRE, which guarantees the security of delegator’s challenge ciphertext in face of collusion between t-1 malicious proxies and the delegatee. The \mathsf{H}\mathsf{R}\mathsf{A} security is stronger than the \mathsf{C}\mathsf{P}\mathsf{A} security since it even allows the adversary to obtain full-grained re-encryptions of the challenge ciphertext to corrupted users (under some constraint to avoid trivial attacks). We propose a generic construction of \mathsf{H}\mathsf{R}\mathsf{A}-secure ThFPRE from Threshold Fully Homomorpic Encryption (ThFHE) and a PRF function. We also instantiate the generic construction of \mathsf{T}\mathsf{h}\mathsf{F}\mathsf{P}\mathsf{R}\mathsf{E} to obtain a specific (t,N)-ThFPRE scheme from lattices for all circuits of polynomial sizes. Our (t,N)-ThFPRE scheme can support arbitrary circuits of polynomial sizes, i.e., they enable transformation from a ciphertext encrypting m for delegator A into a delegatee B’s ciphertext encrypting C(m) for any polynomial-sized circuit C. Our (t,N)-ThFPRE scheme has \mathsf{H}\mathsf{R}\mathsf{A} security based on the LWE assumption in the standard model and hence enjoys post-quantum security. The threshold technique decentralizes the re-encryption power to N proxies, and it makes our (t,N)-ThFPRE schemes resilient to N-t proxy failures. And the \mathsf{H}\mathsf{R}\mathsf{A} security makes our (t,N)-ThFPRE schemes resilient to collusion of t-1 malicious proxies and the delegatee.

Graphical abstract

Keywords

proxy re-encryption / threshold cryptography / HRA security / Fully Homomorphic Encryption

References

[1] Chen H, Kim M, Razenshteyn I P, Rotaru D, Song Y, Wagh S. Maliciously secure matrix multiplication with applications to private deep learning. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security on Advances in Cryptology – ASIACRYPT 2020. 2020, 31–59

[2] Keller M, Pastro V, Rotaru D. Overdrive: making SPDZ great again. In: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology – EUROCRYPT 2018. 2018, 158–189

[3] Lindell Y, Smart N P, Soria-Vazquez E. More efficient constant-round multi-party computation from BMR and SHE. In: Proceedings of the 14th International Conference on Theory of Cryptography. 2016, 554–581

[4] Ateniese G, Fu K, Green M, Hohenberger S. Improved proxy re-encryption schemes with applications to secure distributed storage. In: Proceedings of the Network and Distributed System Security Symposium. 2005

[5] Sharma S, Swarnakar A, Babu C J, Padmavathy R, Kumar R. An authenticated keyword searchable conditional proxy re-encryption scheme in cloud services. In: Proceedings of the 5th International Conference on Computing, Communication and Security (ICCCS). 2020, 1–8

[6] Wang L, Hayashi T, Kanamori S, Waseda A, Nojima R, Moriai S. POSTER: PRINCESS: a secure cloud file storage system for managing data with hierarchical levels of sensitivity. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 2015, 1684–1686

[7] Wu X, Xu L, Zhang X. Poster: a certificateless proxy re-encryption scheme for cloud-based data sharing. In: Proceedings of the 18th ACM Conference on Computer and Communications Security. 2011, 869–872

[8] Gong M, Zhang Y, Gao Y, Qin A K, Wu Y, Wang S, Zhang Y . A multi-modal vertical federated learning framework based on homomorphic encryption. IEEE Transactions on Information Forensics and Security, 2024, 19: 1826–1839

[9] Zhou Y, Zheng P, Cao X, Huang J. Two-tier data packing in RLWE-based homomorphic encryption for secure federated learning. In: Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024, 2844–2858

[10] Blaze M, Bleumer G, Strauss M. Divertible protocols and atomic proxy cryptography. In: Proceedings of EUROCRYPT. 1998, 127–144

[11] Zhou Y, Liu S, Han S. Multi-hop fine-grained proxy re-encryption. In: Proceedings of the 27th IACR International Conference on Practice and Theory of Public-Key Cryptography on Public-Key Cryptography – PKC 2024. 2024, 161–192

[12] Zhou Y, Liu S, Han S, Zhang H. Fine-grained proxy re-encryption: definitions and constructions from LWE. In: Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security on Advances in Cryptology – ASIACRYPT 2023. 2023, 199–231

[13] Zhang Y, Liu S, Zhou Y, Zhang H . Full-grained proxy re-encryption for all circuits. Theoretical Computer Science, 2025, 1056: 115507

[14] Chen X, Liu Y, Li Y, Lin C. Threshold proxy re-encryption and its application in blockchain. In: Proceedings of the 4th International Conference on Cloud Computing and Security. 2018, 16–25

[15] Wu L, Han Y, Yang X, Zhang M . Identity-based threshold proxy re-encryption scheme from lattices and its applications. Frontiers of Information Technology & Electronic Engineering, 2022, 23( 2): 258–277

[16] Zhao F, Weng J, Xie W, Li M, Weng J . Hra-secure attribute-based threshold proxy re-encryption from lattices. Information Sciences, 2024, 655: 119900

[17] Li Z, Ma C, Wang D . Towards multi-hop homomorphic identity-based proxy re-encryption via branching program. IEEE Access, 2017, 5: 16214–16228

[18] Ma C, Li J, Ouyang W. A homomorphic proxy re-encryption from lattices. In: Proceedings of the 10th International Conference on Provable Security. 2016, 353–372

[19] Zhao F, Wang H, Weng J. Constant-size unbounded multi-hop fully homomorphic proxy re-encryption from lattices. In: Proceedings of the 29th European Symposium on Research in Computer Security on Computer Security – ESORICS 2024. 2024, 238–258

[20] Green M, Ateniese G. Identity-based proxy re-encryption. In: Proceedings of the 5th International Conference on Applied Cryptography and Network Security. 2007, 288–306

[21] Shao J. Anonymous ID-based proxy re-encryption. In: Proceedings of the 17th Australasian Conference on Information Security and Privacy. 2012, 364–375

[22] Ateniese G, Benson K, Hohenberger S. Key-private proxy re-encryption. In: Proceedings of the Cryptographers’ Track at the RSA Conference 2009. 2009, 279–294

[23] Chandran N, Chase M, Liu F H, Nishimaki R, Xagawa K. Re-encryption, functional re-encryption, and multi-hop re-encryption: a framework for achieving obfuscation-based security and instantiations from lattices. In: Proceedings of the 17th International Conference on Practice and Theory in Public-Key Cryptography on Public-Key Cryptography -- PKC 2014. 2014, 95–112

[24] Chandran N, Chase M, Vaikuntanathan V. Functional re-encryption and collusion-resistant obfuscation. In: Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography. 2012, 404–421

[25] Liang X, Weng J, Yang A, Yao L, Jiang Z, Wu Z. Attribute-based conditional proxy re-encryption in the standard model under LWE. In: Proceedings of the 26th European Symposium on Research in Computer Security on Computer Security – ESORICS 2021. 2021, 147–168

[26] Susilo W, Dutta P, Duong D H, Roy P S. Lattice-based HRA-secure attribute-based proxy re-encryption in standard model. In: Proceedings of the 26th European Symposium on Research in Computer Security. 2021, 169–191

[27] Miao P, Patranabis S, Watson G J. Unidirectional updatable encryption and proxy re-encryption from DDH. In: Proceedings of the 26th IACR International Conference on Practice and Theory of Public-Key Cryptography on Public-Key Cryptography – PKC 2023. 2023, 368–398

[28] Boneh D, Gennaro R, Goldfeder S, Jain A, Kim S, Rasmussen P M R, Sahai A. Threshold cryptosystems from threshold fully homomorphic encryption. In: Proceedings of the 38th Annual International Cryptology Conference on Advances in Cryptology – CRYPTO 2018. 2018, 565–596

[29] Gentry C. A fully homomorphic encryption scheme. Stanford University, Dissertation, 2009

[30] Cohen A. What about bob? The inadequacy of CPA security for proxy reencryption. In: Proceedings of the 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography on Public-Key Cryptography – PKC 2019. 2019, 287–316

[31] Banerjee A, Peikert C. New and improved key-homomorphic pseudorandom functions. In: Proceedings of the 34th Annual Cryptology Conference on Advances in Cryptology -- CRYPTO 2014. 2014, 353–370

[32] Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology – EUROCRYPT 2012. 2012, 719–737

[33] Boneh D, Lewi K, Montgomery H, Raghunathan A. Key homomorphic PRFs and their applications. In: Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology – CRYPTO 2013. 2013, 410–428

[34] Kim S. Key-homomorphic pseudorandom functions from LWE with small modulus. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology – EUROCRYPT 2020. 2020, 576–607

[35] Lai Q, Liu F H, Wang Z. Almost tight security in lattices with polynomial moduli – PRF, IBE, all-but-many LTF, and more. In: Proceedings of the 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography on Public-Key Cryptography – PKC 2020. 2020, 652–681

[36] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, 309–325

[37] Brakerski Z, Vaikuntanathan V . Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on Computing, 2014, 43( 2): 831–871

[38] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology – CRYPTO 2013. 2013, 75–92

[39] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 2005, 84–93

[40] Ducas L, Micciancio D. FHEW: bootstrapping homomorphic encryption in less than a second. In: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology – EUROCRYPT 2015. 2015, 617–640

[41] Brakerski Z, Gentry C, Vaikuntanathan V . (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory, 2014, 6( 3): 13

RIGHTS & PERMISSIONS

Higher Education Press