Paper 2019/452

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)
PDF
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
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.