Paper 2019/452

A Central Limit Framework for Ring-LWE Decryption

Sean Murphy
Rachel Player
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 an average-case noise analysis for the BGV scheme. Our approach builds upon the recent work of Costache et al. 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 experimentally verify its improvement over prior, worst-case, approaches. 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 have been obtained in prior work.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
Ring-LWE Central Limit Theorem δ-subgaussian decryption failure probability BGV cryptosystem homomorphic encryption
Contact author(s)
s murphy @ rhul ac uk
History
2022-11-28: last of 10 revisions
2019-05-08: received
See all versions
Short URL
https://ia.cr/2019/452
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/452,
      author = {Sean Murphy and Rachel Player},
      title = {A Central Limit Framework for Ring-LWE Decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/452},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/452}},
      url = {https://eprint.iacr.org/2019/452}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.