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