Cryptology ePrint Archive: Report 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.

Category / Keywords: Ring-LWE, Central Limit Theorem, δ-subgaussian, decryption failure probability, homomorphic encryption

Date: received 3 May 2019, last revised 21 Jul 2020

Contact author: s murphy at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200721:120548 (All versions of this report)

Short URL: ia.cr/2019/452