Designs for practical SHE schemes based on Ring-LWR

The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. In this work, we present a thorough study of Somewhat Homomorphic Encryption schemes based on Ring-LWR that are the analogue of the Ring-LWE-based BFV scheme. Our main contribution is to present two new schemes, in the LPR and Regev paradigms, and give a thorough analysis of their security (provable and concrete). The technical tools we developed in the process may be of independent interest to the community. Our schemes inherit the many benefits of being based on LWR, including avoiding the need for expensive Gaussian sampling and improved ciphertext size. Indeed, we give a detailed comparison showing that our schemes marginally outperform the BFV scheme in terms of ciphertext size. Moreover, we show that both our schemes support RNS variants. Our Regev-type scheme can be seen as an improved generalisation of the only prior work in this direction (Costache-Smart, 2017). In particular, our scheme resolves the tangled modulus issue in the Costache-Smart proposal that led to unmanageable noise growth, and achieves a factor n improvement in the size of the public key.