HRA-Secure Homomorphic Lattice-Based Proxy Re-Encryption with Tight Security
Authors
Aloni Cohen, David Bruce Cousins, Nicholas Genise, Erik Kline, Yuriy Polyakov, Saraswathy RV
Aloni Cohen
University of Chicago, USA
aloni at uchicago dot edu
aloni at uchicago dot edu
David Bruce Cousins
Duality Technologies Inc., USA
Nicholas Genise
Apple, USA
Erik Kline
University of Southern California/Information Sciences Institute, USA
Yuriy Polyakov
Duality Technologies Inc., USA
ypolyakov at dualitytech dot com
ypolyakov at dualitytech dot com
Saraswathy RV
Abstract
We construct an efficient proxy re-encryption (PRE) scheme secure against honest re-encryption attacks (HRA-secure) with precise concrete security estimates. To get these precise concrete security estimates, we introduce the tight, fine-grained noise-flooding techniques of Li et al. (CRYPTO'22) to RLWE-based (homomorphic) PRE schemes, as well as a mixed statistical-computational security definition to HRA security analysis. Our solution also supports homomorphic operations on the ciphertexts. Such homomorphism allows for advanced applications, e.g., encrypted computation of network statistics across networks, and unlimited hops in the case of full homomorphism, i.e., when bootstrapping is available.
We implement our PRE scheme in the OpenFHE software library and apply it to a problem of secure multi-hop data distribution in the context of 5G virtual network slices. We also experimentally evaluate the performance of our scheme, demonstrating that the implementation is practical.
Moreover, we compare our PRE method with other lattice-based PRE schemes and approaches targeting HRA security. These achieve HRA security, but not in a tight, practical scheme such as our work. Further, we present an attack on the PRE scheme proposed in Davidson et al.'s (ACISP'19), which was claimed to achieve HRA security without noise flooding, i.e., without adding large noise.
References
[ABB+22]
Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 53–63, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3560827.3563379
[ACC+21]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic Encryption Standard. In Kristin Lauter, Wei Dai, and Kim Laine, editors, Protecting Privacy through Homomorphic Encryption, pages 31–62, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-77287-1_2
[AFGH06]
Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan Hohenberger. Improved proxy re-encryption schemes with applications to secure distributed storage. ACM Trans. Inf. Syst. Secur., 9(1):1–30, 2006. DOI: 10.1145/1127345.1127346
[AJL+12]
Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 483–501. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_29
[BBS98]
Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible Protocols and Atomic Proxy Cryptography. In EUROCRYPT, volume 1403 of Lecture Notes in Computer Science, pages 127–144. 1998. Springer. DOI: 10.1007/BFb0054122
[BCC+25]
Jean-Philippe Bossuat, Rosario Cammarota, Ilaria Chillotti, Benjamin R. Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, Changmin Lee, Xianhui Lu, Carsten Maple, Alberto Pedrouzo-Ulloa, Rachel Player, Yuriy Polyakov, Luis Antonio Ruiz Lopez, Yongsoo Song, and Donggeon Yhee. Security Guidelines for Implementing Homomorphic Encryption. IACR Communications in Cryptology, 1(4), 2025. DOI: 10.62056/anxra69p1
[BGG+18]
Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold Cryptosystems from Threshold Fully Homomorphic Encryption. 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 Lecture Notes in Computer Science, pages 565–596. 2018. Springer. DOI: 10.1007/978-3-319-96884-1_19
[BGP+17]
Cristian Borcea, Arnab Deb Gupta, Yuriy Polyakov, Kurt Rohloff, and Gerard W. Ryan. PICADOR: End-to-end encrypted Publish-Subscribe information distribution with proxy re-encryption. Future Gener. Comput. Syst., 71:177–191, 2017. DOI: 10.1016/j.future.2016.10.013
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. DOI: 10.1145/2633600
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 868–886. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_50
[BV11a]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS, pages 97–106. 2011. IEEE Computer Society. DOI: 10.1109/FOCS.2011.12
[BV11b]
Zvika Brakerski and Vinod Vaikuntanathan. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. In Phillip Rogaway, editor, CRYPTO 2011, pages 505–524, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-22792-9_29
[CGGI16]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 3–33. 2016. DOI: 10.1007/978-3-662-53887-6_1
[CH07]
Ran Canetti and Susan Hohenberger. Chosen-ciphertext secure proxy re-encryption. In CCS, pages 185–194. 2007. ACM. DOI: 10.1145/1315245.13152
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In ASIACRYPT (1), volume 10624 of Lecture Notes in Computer Science, pages 409–437. 2017. Springer. DOI: 10.1007/978-3-319-70694-8_15
[Coh19]
Aloni Cohen. What About Bob? The Inadequacy of CPA Security for Proxy Reencryption. In Public Key Cryptography (2), volume 11443 of Lecture Notes in Computer Science, pages 287–316. 2019. Springer. DOI: 10.1007/978-3-030-17259-6_10
[CSS+22]
Siddhartha Chowdhury, Sayani Sinha, Animesh Singh, Shubham Mishra, Chandan Chaudhary, Sikhar Patranabis, Pratyay Mukherjee, Ayantika Chatterjee, and Debdeep Mukhopadhyay. Efficient Threshold FHE for Privacy-Preserving Applications. Cryptology ePrint Archive, Paper 2022/1625. 2022.
[dCJV21]
Leo de Castro, Chiraag Juvekar, and Vinod Vaikuntanathan. Fast Vector Oblivious Linear Evaluation from Ring Learning with Errors. In WAHC@CCS, pages 29–41. 2021. WAHC@ACM. DOI: 10.1145/3474366.3486928
[DCN18]
Abebe Abeshu Diro, Naveen K. Chilamkurti, and Yunyoung Nam. Analysis of Lightweight Encryption Scheme for Fog-to-Things Communication. IEEE Access, 6:26820–26830, 2018. DOI: 10.1109/ACCESS.2018.2822822
[DDLM19]
Alex Davidson, Amit Deo, Ela Lee, and Keith Martin. Strong Post-Compromise Secure Proxy Re-Encryption. In ACISP, volume 11547 of Lecture Notes in Computer Science, pages 58–77. 2019. Springer. DOI: 10.1007/978-3-030-21548-4_4
[DDP+18]
Wei Dai, Yarkin Doröz, Yuriy Polyakov, Kurt Rohloff, Hadi Sajjadpour, Erkay Savas, and Berk Sunar. Implementation and Evaluation of a Lattice-Based Key-Policy ABE Scheme. IEEE Trans. Inf. Forensics Secur., 13(5):1169–1184, 2018. DOI: 10.1109/TIFS.2017.2779427
[DEF+19]
Ivan Damgård, Daniel Escudero, Tore Kasper Frederiksen, Marcel Keller, Peter Scholl, and Nikolaj Volgushev. New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning. In IEEE Symposium on Security and Privacy, pages 1102–1120. 2019. IEEE. DOI: 10.1109/SP.2019.00078
[dlPVA22]
Antonio de la Piedra, Marloes Venema, and Greg Alpár. ABE Squared: Accurately Benchmarking Efficiency of Attribute-Based Encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(2):192–239, 2022. DOI: 10.46586/tches.v2022.i2.192-239
[DM15]
Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 617–640. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_24
[DN21]
Nico Döttling and Ryo Nishimaki. Universal Proxy Re-Encryption. In Public Key Cryptography (1), volume 12710 of Lecture Notes in Computer Science, pages 512–542. 2021. Springer. DOI: 10.1007/978-3-030-75245-3_19
[DS16]
Léo Ducas and Damien Stehlé. Sanitization of FHE Ciphertexts. In EUROCRYPT (1), volume 9665 of Lecture Notes in Computer Science, pages 294–310. 2016. Springer. DOI: 10.1007/978-3-662-49890-3_12
[Dua]
[FKKP19]
Georg Fuchsbauer, Chethan Kamath, Karen Klein, and Krzysztof Pietrzak. Adaptively Secure Proxy Re-encryption. In Public Key Cryptography (2), volume 11443 of Lecture Notes in Computer Science, pages 317–346. 2019. Springer. DOI: 10.1007/978-3-030-17259-6_11
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptol. ePrint Arch., 2012.
[Gen09]
Craig Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, USA, 2009.
[GHS12a]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 465–482. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_28
[GHS12b]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic Evaluation of the AES Circuit. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 850–867. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_49
[GKS24]
Kamil Doruk Gür, Jonathan Katz, and Tjerand Silde. Two-Round Threshold Lattice-Based Signatures from Threshold Homomorphic Encryption. In Markku-Juhani O. Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Oxford, UK, June 12-14, 2024, Proceedings, Part II, volume 14772 of Lecture Notes in Computer Science, pages 266–300. 2024. Springer. DOI: 10.1007/978-3-031-62746-0_12
[GLSW21]
Sivanarayana Gaddam, Atul Luykx, Rohit Sinha, and Gaven J. Watson. Reducing HSM Reliance in Payments through Proxy Re-Encryption. In USENIX Security Symposium, pages 4061–4078. 2021. USENIX Association.
[GMP19]
Nicholas Genise, Daniele Micciancio, and Yuriy Polyakov. Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More. In EUROCRYPT (2), volume 11477 of Lecture Notes in Computer Science, pages 655–684. 2019. Springer. DOI: 10.1007/978-3-030-17656-3_23
[Goo]
Google.com. gRPC: Google Remote Procedure Call framework.
[GPR+19]
Kamil Doruk Gür, Yuriy Polyakov, Kurt Rohloff, Gerard W. Ryan, Hadi Sajjadpour, and Erkay Savas. Practical Applications of Improved Gaussian Sampling for Trapdoor Lattices. IEEE Trans. Computers, 68(4):570–584, 2019. DOI: 10.1109/TC.2018.2874479
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197–206. 2008. ACM. DOI: 10.1145/1374376.1374407
[HM17]
Gottfried Herold and Alexander May. LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith's Binary Matrix LWE. In Public Key Cryptography (1), volume 10174 of Lecture Notes in Computer Science, pages 3–15. 2017. Springer. DOI: 10.1007/978-3-662-54365-8_1
[HO17]
James Howe and Máire O'Neill. GLITCH: A Discrete Gaussian Testing Suite for Lattice-based Cryptography. In Pierangela Samarati, Mohammad S. Obaidat, and Enrique Cabello, editors, Proceedings of the 14th International Joint Conference on e-Business and Telecommunications (ICETE 2017) - Volume 4: SECRYPT, Madrid, Spain, July 24-26, 2017, pages 413–419. 2017. SciTePress. DOI: 10.5220/0006412604130419
[HPS19]
Shai Halevi, Yuriy Polyakov, and Victor Shoup. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Mitsuru Matsui, editor, CT-RSA 2019, pages 83–105, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-12612-4_5
[ID03]
Anca-Andreea Ivan and Yevgeniy Dodis. Proxy Cryptography Revisited. In NDSS. 2003. The Internet Society.
[Ins]
USC Information Sciences Institute. RAVEN: Ry's Apparatus for Virtual Encodable Networks.
[KPZ21]
Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting Homomorphic Encryption Schemes for Finite Fields. In Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part III, pages 608–639, Berlin, Heidelberg. 2021. Springer-Verlag. DOI: 10.1007/978-3-030-92078-4_21
[KS23]
Kamil Kluczniak and Giacomo Santato. On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption. IACR Cryptol. ePrint Arch., 2023.
[Lee20]
Jasper Lee. Lecture notes in Sublinear Algorithms for Big Data. 2020.
[LM21]
Baiyu Li and Daniele Micciancio. On the Security of Homomorphic Encryption on Approximate Numbers. In EUROCRYPT (1), volume 12696 of Lecture Notes in Computer Science, pages 648–677. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_23
[LMSS22]
Baiyu Li, Daniele Micciancio, Mark Schultz, and Jessica Sorrell. Securing Approximate Homomorphic Encryption Using Differential Privacy. In CRYPTO (1), volume 13507 of Lecture Notes in Computer Science, pages 560–589. 2022. Springer. DOI: 10.1007/978-3-031-15802-5_20
[LPR10]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 1–23. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_1
[MBH23]
Christian Mouchet, Elliott Bertrand, and Jean-Pierre Hubaux. An Efficient Threshold Access-Structure for RLWE-Based Multiparty Homomorphic Encryption. J. Cryptol., 36(2):10, 2023. DOI: 10.1007/S00145-023-09452-8
[MP12]
Daniele Micciancio and Chris Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 700–718. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_41
[MW17]
Daniele Micciancio and Michael Walter. Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time. In CRYPTO (2), volume 10402 of Lecture Notes in Computer Science, pages 455–485. 2017. Springer. DOI: 10.1007/978-3-319-63715-0_16
[MW18]
Daniele Micciancio and Michael Walter. On the Bit Security of Cryptographic Primitives. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer Science, pages 3–28. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_1
[ON20]
Ruxandra F. Olimid and Gianfranco Nencioni. 5G Network Slicing: A Security Overview. IEEE Access, 8:99999–100009, 2020. DOI: 10.1109/ACCESS.2020.2997702
[PRSV17]
Yuriy Polyakov, Kurt Rohloff, Gyana Sahu, and Vinod Vaikuntanathan. Fast Proxy Re-Encryption for Publish/Subscribe Systems. ACM Trans. Priv. Secur., 20(4):14:1–14:31, 2017. DOI: 10.1145/3128607
[PS25]
Alain Passelègue and Damien Stehlé. Low Communication Threshold Fully Homomorphic Encryption. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology – ASIACRYPT 2024, pages 297–329, Singapore. 2025. Springer Nature Singapore. DOI: 10.1007/978-981-96-0875-1_10
[Reg05]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84–93. 2005. ACM. DOI: 10.1145/1060590.1060603
[SDDR21]
Willy Susilo, Priyanka Dutta, Dung Hoang Duong, and Partha Sarathi Roy. Lattice-Based HRA-secure Attribute-Based Proxy Re-Encryption in Standard Model. In ESORICS (2), volume 12973 of Lecture Notes in Computer Science, pages 169–191. 2021. Springer. DOI: 10.1007/978-3-030-88428-4_9
[ZLH24]
Yunxiao Zhou, Shengli Liu, and Shuai Han. Multi-hop Fine-Grained Proxy Re-encryption. In Qiang Tang and Vanessa Teague, editors, Public-Key Cryptography – PKC 2024, pages 161–192, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-57728-4_6
[ZLHZ23]
Yunxiao Zhou, Shengli Liu, Shuai Han, and Haibin Zhang. Fine-Grained Proxy Re-encryption: Definitions and Constructions from LWE. In ASIACRYPT (6), volume 14443 of Lecture Notes in Computer Science, pages 199–231. 2023. Springer. DOI: 10.1007/978-981-99-8736-8_7
[ZPW+15]
Hannes Zach, Philip Peinsold, Johannes Winter, Peter Danner, and Jakob Hatzl. Using proxy re-encryption for secure data management in an ambient assisted living application. In Detlef Hühnlein, Heiko Roßnagel, Raik Kuhlisch, and Jan Ziesing, editors, Open Identity Summit 2015. 2015. GI.
PDF
History
Submitted: 2025-01-10
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Aloni Cohen, David Bruce Cousins, Nicholas Genise, Erik Kline, Yuriy Polyakov, and Saraswathy RV, HRA-Secure Homomorphic Lattice-Based Proxy Re-Encryption with Tight Security. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ab0l5wol7.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.