Paper 2019/452
A Central Limit Framework for Ring-LWE Decryption
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
-
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}
}
