Paper 2017/698

Noise Distributions in Homomorphic Ring-LWE

Sean Murphy and Rachel Player

Abstract

We develop a statistical framework to analyse the Ring-LWE processes of A Toolkit for Ring-LWE Cryptography (Eurocrypt 2013) and similar processes. We consider the $\delta$-subgaussian random variables used in the Toolkit and elsewhere in the literature, and we give a simple and complete characterisation of such random variables. We then apply our results to the homomorphic cryptosystem provided as an example application in the Toolkit. We show that the $\delta$-subgaussian approach as used in the Toolkit to argue correctness of this cryptosystem is flawed, and we also rectify this analysis using our developed statistical framework.