Discretisation and Product Distributions in Ring-LWE

Sean Murphy; Rachel Player

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

Note: Accepted for MathCrypt 2019

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Ring-LWE Discretisation Homomorphic Encryption.
Contact author(s): s murphy @ rhul ac uk
rachel player @ rhul ac uk
History: 2019-07-26: last of 2 revisions; 2019-06-02: received; See all versions
Short URL: https://ia.cr/2019/596
License: CC BY

BibTeX

@misc{cryptoeprint:2019/596,
      author = {Sean Murphy and Rachel Player},
      title = {Discretisation and Product Distributions in Ring-{LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/596},
      year = {2019},
      url = {https://eprint.iacr.org/2019/596}
}