Cryptology ePrint Archive: Report 2019/452

A Central Limit Framework for Ring-LWE Decryption

Sean Murphy and Rachel Player

Abstract: The purpose of this paper is to use a Central Limit approach to develop a statistical framework for analysing ciphertexts in Ring-LWE homomorphic encryption schemes. This statistical framework gives rise to Normal approximations for ciphertext random variables, and we show that this allows probabilities to be determined more accurately and hence enables better bounds for decryption failure probabilities than the widely used existing approach based on $\delta$-subgaussian random variables. To demonstrate the benefit of the Central Limit approach, we apply our framework and results to a homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version).

Category / Keywords: Ring-LWE, Central Limit Theorem, δ-subgaussian

Date: received 3 May 2019, last revised 9 May 2019

Contact author: s murphy at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190509:135827 (All versions of this report)

Short URL: ia.cr/2019/452