A Central Limit Approach for Ring-LWE Noise Analysis

Sean Murphy; Rachel Player

doi:10.62056/ay76c0kr

A Central Limit Approach for Ring-LWE Noise Analysis

Authors

Sean Murphy, Rachel Player

Sean Murphy

Royal Holloway, University of London, Egham, UK
s dot murphy at rhul dot ac dot uk

Rachel Player

Royal Holloway, University of London, Egham, UK
rachel dot player at rhul dot ac dot uk

Keywords: Ring-LWE Central Limit Theorem decryption failure probability BGV scheme homomorphic encryption

Abstract

This paper develops Central Limit arguments for analysing the noise in ciphertexts in two homomorphic encryption schemes that are based on Ring-LWE. The first main contribution of this paper is to present and evaluate an average-case noise analysis for the BGV scheme. Our approach relies on the recent work of Costache et al.(SAC 2023) that gives the approximation of a polynomial product as a multivariate Normal distribution. We show how this result can be applied in the BGV context and evaluate its efficacy. We find this average-case approach can much more closely model the noise growth in BGV implementations than prior approaches, but in some cases it can also underestimate the practical noise growth. Our second main contribution is to develop a Central Limit framework to analyse the noise growth in the homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version). Our approach is very general: apart from finite variance, no assumption on the distribution of the noise is required (in particular, the noise need not be subgaussian). We show that our approach leads to tighter bounds for the probability of decryption failure than those of prior work.

References

[ABBB⁺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

Google Scholar ePrint

[ABMP24]

Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, and Yuriy Polyakov. Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use. https://eprint.iacr.org/2024/203. Cryptology ePrint Archive, Paper 2024/203. 2024.

Google Scholar ePrint

[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.

Google Scholar ePrint

[BGV12]

Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Innovations in Theoretical Computer Science 2012, pages 309–325. 2012. ACM. DOI: https://doi.org/10.1145/2090236.2090262

Google Scholar ePrint

[Bil95]

P. Billingsley. Probability and Measure. Wiley, Third edition. 1995.

Google Scholar ePrint

[BM23]

Beatrice Biasioli and Chiara Marcolla. Personal communication.. 2023.

Google Scholar ePrint

[BMCM23]

Beatrice Biasioli, Chiara Marcolla, Marco Calderini, and Johannes Mono. Improving and Automating BFV Parameters Selection: An Average-Case Approach. IACR Cryptol. ePrint Arch., 2023.

Google Scholar ePrint

[CCH⁺23]

Anamaria Costache, Benjamin R. Curtis, Erin Hales, Sean Murphy, Tabitha Ogilvie, and Rachel Player. On the Precision Loss in Approximate Homomorphic Encryption. In Claude Carlet, Kalikinkar Mandal, and Vincent Rijmen, editors, Selected Areas in Cryptography - SAC 2023 - 30th International Conference, Fredericton, Canada, August 14-18, 2023, Revised Selected Papers, volume 14201 of Lecture Notes in Computer Science, pages 325–345. 2023. Springer. DOI: 10.1007/978-3-031-53368-6_16

Google Scholar ePrint

[CCP⁺24]

Jung Hee Cheon, Hyeongmin Choe, Alain Passelègue, Damien Stehlé, and Elias Suvanto. Attacks Against the INDCPA-D Security of Exact FHE Schemes. https://eprint.iacr.org/2024/127. Cryptology ePrint Archive, Paper 2024/127. 2024.

Google Scholar ePrint

[CGGI16]

I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In J. H. Cheon and T. Takagi, editors, Advances in Cryptology - ASIACRYPT 2016, volume 10031 of LNCS, pages 3–33. 2016. Springer. DOI: https://doi.org/10.1007/978-3-662-53887-6_1

Google Scholar ePrint

[CGGI20]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast Fully Homomorphic Encryption Over the Torus. J. Cryptology, 33(1):34–91, 2020. DOI: https://doi.org/10.1007/s00145-019-09319-x

Google Scholar ePrint

[CKKS17]

J. H. Cheon, A. Kim, M. Kim, and Y. S. Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In T. Takagi and T. Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017, volume 10624 of LNCS, pages 409–437. 2017. Springer. DOI: https://doi.org/10.1007/978-3-319-70694-8_15

Google Scholar ePrint

[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

Google Scholar ePrint

[CNP23]

Anamaria Costache, Lea Nürnberger, and Rachel Player. Optimisations and Tradeoffs for HElib. In Mike Rosulek, editor, Topics in Cryptology - CT-RSA 2023 - Cryptographers' Track at the RSA Conference 2023, San Francisco, CA, USA, April 24-27, 2023, Proceedings, volume 13871 of Lecture Notes in Computer Science, pages 29–53. 2023. Springer. DOI: https://doi.org/10.1007/978-3-031-30872-7_2

Google Scholar ePrint

[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

Google Scholar ePrint

[CSBB24]

Marina Checri, Renaud Sirdey, Aymen Boudguiga, and Jean-Paul Bultel. On the practical CPAD security of “exact” and threshold FHE schemes and libraries. https://eprint.iacr.org/2024/116. Cryptology ePrint Archive, Paper 2024/116. 2024.

Google Scholar ePrint

[FV12]

J. Fan and F. Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, 2012:144, 2012.

Google Scholar ePrint

[Gen09]

C. Gentry. Fully Homomorphic Encryption using Ideal Lattices. In M. Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 169–178. 2009. DOI: https://doi.org/10.1145/1536414.1536440

Google Scholar ePrint

[GHS12a]

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

Google Scholar ePrint

[GHS12b]

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

Google Scholar ePrint

[GNSJ24]

Qian Guo, Denis Nabokov, Elias Suvanto, and Thomas Johansson. Key Recovery Attacks on Approximate Homomorphic Encryption with Non-Worst-Case Noise Flooding Countermeasures. In 33rd USENIX Security Symposium (USENIX Security 24). Philadelphia, PA: USENIX Association. 2024. Pre-proceedings version available at https://www.usenix.org/system/files/sec24summer-prepub-822-guo.pdf

Google Scholar ePrint

[GS01]

G. Grimmett and D. Stirzaker. Probability And Random Processes. Oxford University Press, 3rd edition. 2001.

Google Scholar ePrint

[GSW13]

C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In R. Canetti and J.A. Garay, editors, Advances in Cryptology - CRYPTO 2013, volume 8042 of LNCS, pages 75–92. 2013. Springer. DOI: https://doi.org/10.1007/978-3-642-40041-4_5

Google Scholar ePrint

[{HEl}19]

HElib. https://github.com/homenc/HElib. January 2019.

Google Scholar ePrint

[HS20]

Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. https://eprint.iacr.org/2020/1481. Cryptology ePrint Archive, Paper 2020/1481. 2020.

Google Scholar ePrint

[Ili19]

I. Iliashenko. Optimisations of fully homomorphic encryption. PhD thesis, KU Leuven, 2019.

Google Scholar ePrint

[KPP22]

Andrey Kim, Antonis Papadimitriou, and Yuriy Polyakov. Approximate Homomorphic Encryption with Reduced Approximation Error. In Steven D. Galbraith, editor, Topics in Cryptology - CT-RSA 2022 - Cryptographers' Track at the RSA Conference 2022, Virtual Event, March 1-2, 2022, Proceedings, volume 13161 of Lecture Notes in Computer Science, pages 120–144. 2022. Springer. DOI: 10.1007/978-3-030-95312-6_6

Google Scholar ePrint

[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

Google Scholar ePrint

[LMSS22]

B. Li, D. Micciancio, M. Schutz, and J. Sorrel. Securing Approximate Homomorphic Encryption using Differential Privacy. In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022, volume LNCS 13507, pages 560-589. 2022. DOI: https://doi.org/10.1007/978-3-031-15802-5_20

Google Scholar ePrint

[LPR12]

V. Lyubashevsky, C. Peikert, and O. Regev. On Ideal Lattices and Learning with Errors Over Rings. IACR Cryptology ePrint Archive, 2012:230, 2012.

Google Scholar ePrint

[LPR13a]

V. Lyubashevsky, C. Peikert, and O. Regev. A Toolkit for Ring-LWE Cryptography. IACR Cryptology ePrint Archive, 2013:293, 2013.

Google Scholar ePrint

[LPR13b]

V. Lyubashevsky, C. Peikert, and O. Regev. A Toolkit for Ring-LWE Cryptography. In T. Johansson and P. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, volume 7881 of LNCS, pages 35–54. 2013. Springer.

Google Scholar ePrint

[MP12]

D. Micciancio and C. Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In D. Pointcheval and T. Johansson, editors, Eurocrypt 2012, volume 7237 of LNCS, pages 700-718. 2012. Springer. DOI: https://doi.org/10.1007/978-3-642-29011-4_41

Google Scholar ePrint

[MP19]

S. Murphy and R. Player. $\delta$-subgaussian Random Variables in Cryptography. In J. Jang-Jaccard and F. Guo, editors, ACISP 2019: The 24th Australasian Conference on Information Security and Privacy, volume 11547 of LNCS, pages 251-268. 2019. Springer. DOI: https://doi.org/10.1007/978-3-030-21548-4_14

Google Scholar ePrint

[MP20]

Sean Murphy and Rachel Player. Discretisation and Product Distributions in Ring-LWE. Journal of Mathematical Cryptology, 15:45–59, 2020. DOI: https://doi.org/10.1515/jmc-2020-0073

Google Scholar ePrint

[MR09]

D. Micciancio and O. Regev. Lattice-based Cryptography. In D.J. Bernstein, J. Buchmann, and E. Dahmen, editors, Post-Quantum Cryptography, pages 147-191. 2009. Springer. DOI: 10.1007/978-3-540-88702-7_5

Google Scholar ePrint

[Pei16]

Chris Peikert. A Decade of Lattice Cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283–424, 2016. DOI: https://doi.org/10.1561/0400000074

Google Scholar ePrint

[Pla18]

Rachel Player. Parameter selection in lattice-based cryptography. PhD thesis, Royal Holloway, University of London, 2018.

Google Scholar ePrint

[Reg05]

O. Regev. On Lattices, Learning with Errors, Random Linear Codes and Cryptography. In H. Gabow and R. Fagin, editors, 37th Annual ACM Symposium of Theory of Computing. 2005. DOI: https://doi.org/10.1145/1568318.1568324

Google Scholar ePrint

[Reg10]

O. Regev. The Learning with Errors Problem (Invited Survey). In IEEE Conference on Computational Complexity, pages 191-204. 2010. DOI: https://doi.org/10.1109/CCC.2010.26

Google Scholar ePrint

[SEA22]

Microsoft SEAL (release 4.0). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. March 2022.

Google Scholar ePrint

[SSTX09]

D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In M. Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of LNCS, pages 617–635. 2009. DOI: https://doi.org/10.1007/978-3-642-10366-7_36

Google Scholar ePrint

[Str11]

D. Stroock. Probability Theory: An Analytic View. Cambridge University Press 2011.

Google Scholar ePrint

[TV11]

T. Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics. Acta Mathematica, 206:127-204, 2011. DOI: https://doi.org/10.1007/s11511-011-0061-3

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ay76c0kr

History

Submitted: 2024-03-20
Accepted: 2024-06-03
Published: 2024-07-08

How to cite

Sean Murphy and Rachel Player, A Central Limit Approach for Ring-LWE Noise Analysis. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ay76c0kr.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-2-7,
    author = "Murphy, Sean and Player, Rachel",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "A Central Limit Approach for Ring-{LWE} Noise Analysis",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ay76c0kr"
}

TY - JOUR
AU - Murphy, Sean
AU - Player, Rachel
PY  - 2024
TI  - A Central Limit Approach for Ring-LWE Noise Analysis
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/ay76c0kr
UR  - https://doi.org/10.62056/ay76c0kr
AB  - <p>This paper develops Central Limit arguments for analysing the noise in ciphertexts in two homomorphic encryption schemes that are based on Ring-LWE. The first main contribution of this paper is to present and evaluate an average-case noise analysis for the BGV scheme. Our approach relies on the recent work of Costache et al.(SAC 2023) that gives the approximation of a polynomial product as a multivariate Normal distribution. We show how this result can be applied in the BGV context and evaluate its efficacy. We find this average-case approach can much more closely model the noise growth in BGV implementations than prior approaches, but in some cases it can also underestimate the practical noise growth. Our second main contribution is to develop a Central Limit framework to analyse the noise growth in the homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version). Our approach is very general: apart from finite variance, no assumption on the distribution of the noise is required (in particular, the noise need not be subgaussian). We show that our approach leads to tighter bounds for the probability of decryption failure than those of prior work. </p>
ER  -

Sean Murphy and Rachel Player, A Central Limit Approach for Ring-LWE Noise Analysis. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ay76c0kr.