Cryptology ePrint Archive: Report 2019/596

Discretisation and Product Distributions in Ring-LWE

Sean Murphy and Rachel Player

Abstract: A statistical framework applicable to Ring-LWE was outlined by Murphy and Player (IACR eprint 2019/452). Its applicability was demonstrated with an analysis of the decryption failure probability for degree-1 and degree-2 ciphertexts in the homomorphic encryption scheme of Lyubashevsky, Peikert and Regev (IACR eprint 2013/293). In this paper, we clarify and extend results presented by Murphy and Player. Firstly, we make precise the approximation of the discretisation of a Normal random variable as a Normal random variable, as used in the encryption process of Lyubashevsky, Peikert and Regev. Secondly, we show how to extend the analysis given by Murphy and Player to degree-k ciphertexts, by precisely characterising the distribution of the noise in these ciphertexts.

Category / Keywords: Ring-LWE, Discretisation, Homomorphic Encryption.

Date: received 29 May 2019, last revised 26 Jul 2019

Contact author: s murphy at rhul ac uk,rachel player@rhul ac uk

Available format(s): PDF | BibTeX Citation

Note: Accepted for MathCrypt 2019

Version: 20190726:102810 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]