Designs for practical SHE schemes based on Ring-LWR
Authors
Madalina Bolboceanu, Anamaria Costache, Erin Hales, Rachel Player, Miruna Rosca, Radu Titiu
Rachel Player
Royal Holloway, University of London, UK
rachel dot player at rhul dot ac dot uk
rachel dot player at rhul dot ac dot uk
Abstract
The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key.
References
[ACC+18]
M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, and V. Vaikuntanathan. Homomorphic Encryption Security Standard. Technical report, HomomorphicEncryption.org. 2018.
[ACD+18]
Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. Estimate All the {LWE, NTRU} Schemes!. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks - 11th International Conference, SCN 2018, Amalfi, Italy, September 5-7, 2018, Proceedings, volume 11035 of Lecture Notes in Computer Science, pages 351–367. 2018. Springer. DOI: 10.1007/978-3-319-98113-0_19
[APS15]
M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of Learning with Errors. J. Mathematical Cryptology, 9(3):169–203, 2015.
[BBC+20]
Hayo Baan, Sauvik Bhattacharya, Jung Hee Cheon, Scott Fluhrer, Oscar Garcia-Morchon, Paul Gorissen, Thijs Laarhoven, Rachel Player, Ronald Rietman, Markku-Juhani O. Saarinen, Yongha Son, Ludo Tolhuizen, José Luis Torre-Arce, and Zhenfei Zhang. Round5: KEM and PKE based on (Ring) Learning with Rounding. round5.org. 2020.
[BBSS20]
Xavier Bonnetain, Rémi Bricout, André Schrottenloher, and Yixin Shen. Improved Classical and Quantum Algorithms for Subset-Sum. 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 II, volume 12492 of Lecture Notes in Computer Science, pages 633–666. 2020. Springer. DOI: 10.1007/978-3-030-64834-3_22
[BBTV23]
Jonas Bertels, Michiel Van Beirendonck, Furkan Turan, and Ingrid Verbauwhede. Hardware Acceleration of FHEW. In Maksim Jenihhin, Hana Kubátová, Nele Metens, Jaan Raik, Foisal Ahmed, and Jan Belohoubek, editors, 26th International Symposium on Design and Diagnostics of Electronic Circuits and Systems, DDECS 2023, Tallinn, Estonia, May 3-5, 2023, pages 57–60. 2023. IEEE. DOI: 10.1109/DDECS57882.2023.10139347
[BCC+24]
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 Commun. Cryptol., 1(4):26, 2024. DOI: 10.62056/ANXRA69P1
[BCH+24]
Madalina Bolboceanu, Anamaria Costache, Erin Hales, Rachel Player, Miruna Rosca, and Radu Titiu. Designs for practical SHE schemes based on Ring-LWR. IACR Cryptol. ePrint Arch., 2024.
[BDK+18]
Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018, London, United Kingdom, April 24-26, 2018, pages 353–367. 2018. IEEE. DOI: 10.1109/EUROSP.2018.00032
[BDL+18]
Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner, and Chris Peikert. More Efficient Commitments from Structured Lattice Assumptions. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks - 11th International Conference, SCN 2018, Amalfi, Italy, September 5-7, 2018, Proceedings, volume 11035 of Lecture Notes in Computer Science, pages 368–385. 2018. Springer. DOI: 10.1007/978-3-319-98113-0_20
[BEHZ16]
Jean-Claude Bajard, Julien Eynard, M. Anwar Hasan, and Vincent Zucca. A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes. In Roberto Avanzi and Howard M. Heys, editors, Selected Areas in Cryptography - SAC 2016 - 23rd International Conference, St. John's, NL, Canada, August 10-12, 2016, Revised Selected Papers, volume 10532 of Lecture Notes in Computer Science, pages 423–442. 2016. Springer. DOI: 10.1007/978-3-319-69453-5_23
[BGLS19]
Shi Bai, Steven D. Galbraith, Liangze Li, and Daniel Sheffield. Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem. J. Cryptol., 32(1):35–83, 2019. DOI: 10.1007/s00145-018-9304-1
[BGRT17]
Sauvik Bhattacharya, Óscar García-Morchón, Ronald Rietman, and Ludo Tolhuizen. spKEX: An optimized lattice-based key exchange. IACR Cryptol. ePrint Arch., 2017.
[BGV12]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 309–325. 2012. ACM. DOI: 10.1145/2090236.2090262
[BHLY16]
Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. Flush, Gauss, and Reload - A Cache Attack on the BLISS Lattice-Based Signature Scheme. In Benedikt Gierlichs and Axel Y. Poschmann, editors, Cryptographic Hardware and Embedded Systems - CHES 2016 - 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, volume 9813 of Lecture Notes in Computer Science, pages 323–345. 2016. Springer. DOI: 10.1007/978-3-662-53140-2_16
[BPR12]
Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom Functions and Lattices. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 719–737. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_42
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In R. Safavi-Naini and R. Canetti, editors, Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 868–886. 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-32009-5_50
[BSS22]
Katharina Boudgoust, Amin Sakzad, and Ron Steinfeld. Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems. Des. Codes Cryptogr., 90(8):1899–1936, 2022. DOI: 10.1007/s10623-022-01083-7
[BV11a]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, 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, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 505–524. 2011. Springer. 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
[CH18]
Hao Chen and Kyoohyung Han. Homomorphic Lower Digits Removal and Improved FHE Bootstrapping. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pages 315–337. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_12
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I, volume 10624 of Lecture Notes in Computer Science, pages 409–437. 2017. Springer. DOI: 10.1007/978-3-319-70694-8_15
[CKLS18]
Jung Hee Cheon, Duhyeong Kim, Joohee Lee, and Yongsoo Song. Lizard: Cut Off the Tail! A Practical Post-quantum Public-Key Encryption from LWE and LWR. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks - 11th International Conference, SCN 2018, Amalfi, Italy, September 5-7, 2018, Proceedings, volume 11035 of Lecture Notes in Computer Science, pages 160–177. 2018. Springer. DOI: 10.1007/978-3-319-98113-0_9
[CLP20]
Anamaria Costache, Kim Laine, and Rachel Player. Evaluating the Effectiveness of Heuristic Worst-Case Noise Analysis in FHE. In Liqun Chen, Ninghui Li, Kaitai Liang, and Steve A. Schneider, editors, Computer Security - ESORICS 2020 - 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14-18, 2020, Proceedings, Part II, volume 12309 of Lecture Notes in Computer Science, pages 546–565. 2020. Springer. DOI: 10.1007/978-3-030-59013-0_27
[CLR17]
Hao Chen, Kim Laine, and Peter Rindal. Fast Private Set Intersection from Homomorphic Encryption. 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 1243–1255. 2017. ACM. DOI: 10.1145/3133956.3134061
[CP19]
Benjamin R. Curtis and Rachel Player. On the Feasibility and Impact of Standardising Sparse-secret LWE Parameter Sets for Homomorphic Encryption. In Michael Brenner, Tancrède Lepoint, and Kurt Rohloff, editors, Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2019, London, UK, November 11-15, 2019, pages 1–10. 2019. ACM. DOI: 10.1145/3338469.3358940
[CS16]
Ana Costache and Nigel P. Smart. Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?. In Kazue Sako, editor, Topics in Cryptology - CT-RSA 2016 - The Cryptographers' Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 - March 4, 2016, Proceedings, volume 9610 of Lecture Notes in Computer Science, pages 325–340. 2016. Springer. DOI: 10.1007/978-3-319-29485-8_19
[CS17]
Anamaria Costache and Nigel P. Smart. Homomorphic Encryption without Gaussian Noise. IACR Cryptol. ePrint Arch., 2017.
[DKL+18]
Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(1):238–268, 2018. DOI: 10.13154/TCHES.V2018.I1.238-268
[DKRV18]
Jan-Pieter D'Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. In Antoine Joux, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors, Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7-9, 2018, Proceedings, volume 10831 of Lecture Notes in Computer Science, pages 282–305. 2018. Springer. DOI: 10.1007/978-3-319-89339-6_16
[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
[DPSZ12]
Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 643–662. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_38
[DRS04]
Yevgeniy Dodis, Leonid Reyzin, and Adam D. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. 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 Lecture Notes in Computer Science, pages 523–540. 2004. Springer. DOI: 10.1007/978-3-540-24676-3_31
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptol. ePrint Arch., 2012.
[GBP+23]
Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios D. Dimou, Ingrid Verbauwhede, Frederik Vercauteren, and David W. Archer. BASALISC: Programmable Hardware Accelerator for BGV Fully Homomorphic Encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(4):32–57, 2023. DOI: 10.46586/TCHES.V2023.I4.32-57
[Gen09]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169–178. 2009. ACM. DOI: 10.1145/1536414.1536440
[GH19]
Craig Gentry and Shai Halevi. Compressible FHE with Applications to PIR. 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 Lecture Notes in Computer Science, pages 438–464. 2019. Springer. DOI: 10.1007/978-3-030-36033-7_17
[GHS12a]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Better Bootstrapping in Fully Homomorphic Encryption. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings, volume 7293 of Lecture Notes in Computer Science, pages 1–16. 2012. Springer. DOI: 10.1007/978-3-642-30057-8_1
[GHS12b]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 465–482. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_28
[GHS12c]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic Evaluation of the AES Circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 850–867. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_49
[GIKV23]
Robin Geelen, Ilia Iliashenko, Jiayi Kang, and Frederik Vercauteren. On Polynomial Functions Modulo p\({}^{\mbox{e}}\) and Faster Bootstrapping for Homomorphic Encryption. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part III, volume 14006 of Lecture Notes in Computer Science, pages 257–286. 2023. Springer. DOI: 10.1007/978-3-031-30620-4_9
[GM23]
Timo Glaser and Alexander May. How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium. In Jing Deng, Vladimir Kolesnikov, and Alexander A. Schwarzmann, editors, Cryptology and Network Security - 22nd International Conference, CANS 2023, Augusta, GA, USA, October 31 - November 2, 2023, Proceedings, volume 14342 of Lecture Notes in Computer Science, pages 75–100. 2023. Springer. DOI: 10.1007/978-981-99-7563-1_4
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 197–206. 2008. ACM. 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, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75–92. 2013. Springer. DOI: 10.1007/978-3-642-40041-4_5
[GV23]
Robin Geelen and Frederik Vercauteren. Bootstrapping for BGV and BFV Revisited. J. Cryptol., 36(2):12, 2023. DOI: 10.1007/s00145-023-09454-6
[HEl19]
HElib. https://github.com/shaih/HElib. January 2019.
[HPS19]
Shai Halevi, Yuriy Polyakov, and Victor Shoup. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Mitsuru Matsui, editor, Topics in Cryptology - CT-RSA 2019 - The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, March 4-8, 2019, Proceedings, volume 11405 of Lecture Notes in Computer Science, pages 83–105. 2019. Springer. DOI: 10.1007/978-3-030-12612-4_5
[HS21]
Shai Halevi and Victor Shoup. Bootstrapping for HElib. J. Cryptol., 34(1):7, 2021. DOI: 10.1007/s00145-020-09368-7
[Ili19]
I. Iliashenko. Optimisations of fully homomorphic encryption. PhD thesis, KU Leuven, 2019.
[KH18]
Suhri Kim and Seokhie Hong. Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure. Appl. Sci., 1809, 2018.
[KKK+22]
Sangpyo Kim, Jongmin Kim, Michael Jaemin Kim, Wonkyung Jung, John Kim, Minsoo Rhu, and Jung Ho Ahn. BTS: an accelerator for bootstrappable fully homomorphic encryption. In Valentina Salapura, Mohamed Zahran, Fred Chong, and Lingjia Tang, editors, ISCA '22: The 49th Annual International Symposium on Computer Architecture, New York, New York, USA, June 18 - 22, 2022, pages 711–725. 2022. ACM. DOI: 10.1145/3470496.3527415
[KNK+25]
Suparna Kundu, Quinten Norga, Angshuman Karmakar, Shreya Gangopadhyay, Jose Maria Bermudo Mera, and Ingrid Verbauwhede. Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation Mechanisms. ACM Trans. Embed. Comput. Syst., 24(1):10:1–10:40, 2025. DOI: 10.1145/3696208
[KPZ21]
Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting Homomorphic Encryption Schemes for Finite Fields. In Mehdi Tibouchi and Huaxiong Wang, editors, 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, volume 13092 of Lecture Notes in Computer Science, pages 608–639. 2021. Springer. DOI: 10.1007/978-3-030-92078-4_21
[LPR10]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. 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 Lecture Notes in Computer Science, pages 1–23. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_1
[LPR13]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A Toolkit for Ring-LWE Cryptography. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 35–54. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_3
[LS18]
Vadim Lyubashevsky and Gregor Seiler. Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, pages 204–224. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_8
[LWW+18]
Fucai Luo, Fuqun Wang, Kunpeng Wang, Jie Li, and Kefei Chen. LWR-Based Fully Homomorphic Encryption, Revisited. Secur. Commun. Networks, 2018:5967635:1–5967635:12, 2018. DOI: 10.1155/2018/5967635
[LWWC19]
Fucai Luo, Fuqun Wang, Kunpeng Wang, and Kefei Chen. Fully homomorphic encryption based on the ring learning with rounding problem. IET Inf. Secur., 13(6):639–648, 2019. DOI: 10.1049/IET-IFS.2018.5427
[Lyu16]
Vadim Lyubashevsky. Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings. 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 II, volume 10032 of Lecture Notes in Computer Science, pages 196–214. 2016. DOI: 10.1007/978-3-662-53890-6_7
[MAK+23]
Ahmet Can Mert, Aikata, Sunmin Kwon, Youngsam Shin, Donghoon Yoo, Yongwoo Lee, and Sujoy Sinha Roy. Medha: Microcoded Hardware Accelerator for computing on Encrypted Data. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(1):463–500, 2023. DOI: 10.46586/tches.v2023.i1.463-500
[May21]
Alexander May. How to Meet Ternary LWE Keys. 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 II, volume 12826 of Lecture Notes in Computer Science, pages 701–731. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_24
[Mic02]
Daniele Micciancio. Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 356–365. 2002. IEEE Computer Society. DOI: 10.1109/SFCS.2002.1181960
[MKKV21]
Jose Maria Bermudo Mera, Angshuman Karmakar, Suparna Kundu, and Ingrid Verbauwhede. Scabbard: a suite of efficient learning with rounding key-encapsulation mechanisms. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(4):474–509, 2021. DOI: 10.46586/tches.v2021.i4.474-509
[MM11]
Daniele Micciancio and Petros Mol. Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 465–484. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_26
[OPP23]
Hiroki Okada, Rachel Player, and Simon Pohmann. Homomorphic Polynomial Evaluation Using Galois Structure and Applications to BFV Bootstrapping. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part VI, volume 14443 of Lecture Notes in Computer Science, pages 69–100. 2023. Springer. DOI: 10.1007/978-981-99-8736-8_3
[PAL17]
PALISADE v1.0. New Jersey Institute of Technology (NJIT). https://git.njit.edu/palisade/PALISADE. 2017.
[PBT+24]
David Du Pont, Jonas Bertels, Furkan Turan, Michiel Van Beirendonck, and Ingrid Verbauwhede. Hardware Acceleration of the Prime-Factor and Rader NTT for BGV Fully Homomorphic Encryption. 2024.
[Pla18]
R. Player. Parameter selection in lattice-based cryptography. PhD thesis, Royal Holloway, University of London, 2018.
[Reg05]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84–93. 2005. ACM. DOI: 10.1145/1060590.1060603
[Reg10]
Oded Regev. The Learning with Errors Problem (Invited Survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 191–204. 2010. IEEE Computer Society. DOI: 10.1109/CCC.2010.26
[RVV13]
Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. High Precision Discrete Gaussian Sampling on FPGAs. In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, pages 383–401. 2013. Springer. DOI: 10.1007/978-3-662-43414-7_19
[SEA23]
Microsoft SEAL (release 4.1). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. January 2023.
[SFK+21]
Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald G. Dreslinski, Christopher Peikert, and Daniel Sánchez. F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption. In MICRO '21: 54th Annual IEEE/ACM International Symposium on Microarchitecture, Virtual Event, Greece, October 18-22, 2021, pages 238–252. 2021. ACM. DOI: 10.1145/3466752.3480070
[She23]
Yixin Shen. Personal communication. 2023.
[SSTX09]
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, volume 5912 of Lecture Notes in Computer Science, pages 617–635. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_36
[ZLYW23]
Shiduo Zhang, Xiuhan Lin, Yang Yu, and Weijia Wang. Improved Power Analysis Attacks on Falcon. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part IV, volume 14007 of Lecture Notes in Computer Science, pages 565–595. 2023. Springer. DOI: 10.1007/978-3-031-30634-1_19
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
Madalina Bolboceanu, Anamaria Costache, Erin Hales, Rachel Player, Miruna Rosca, and Radu Titiu, Designs for practical SHE schemes based on Ring-LWR. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/av7tudy6b.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.