### A Central Limit Framework for Ring-LWE Decryption

Sean Murphy and Rachel Player

##### Abstract

The main contribution of this paper is to develop a statistical framework, based on a Central Limit argument, for analysing the noise in ciphertexts in homomorphic encryption schemes that are based on Ring-LWE. Such an 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 demonstrate that such a Central Limit approach can be used to obtain a high-quality approximation of the distribution of the noise in an appropriate decoding basis, even in dimension as small as n = 100. We apply our framework and results to a homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version) in order to illustrate the benefit of this approach. We show that a Central Limit approach leads to tighter bounds for the probability of decryption failure than have been obtained in prior work.

##### Metadata
Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
Ring-LWECentral Limit Theorem&#948-subgaussiandecryption failure probabilityhomomorphic encryption
Contact author(s)
s murphy @ rhul ac uk
History
2020-07-21: last of 4 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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.