Space-efficient variants of cryptosystems based on learning with errors

Abstract. We consider public key encryption based on the learning with errors problem (LWE). There are several reasons why this encryption scheme is not considered to be practical, and one of the most commonly cited is the size of the public key. However, there is a simple way to greatly reduce the size of the public key. The aim of this paper is to investigate such ideas and to consider some ways to implement LWE encryption on devices with relatively small storage. We remark that a more natural approach for such settings would be to use NTRU or Ring-LWE; we also apply our ideas to these cases. Some of the variants we propose no longer have the same rigorous security guarantees enjoyed by standard en-cryption based on LWE. Hence, the bulk of the paper consists of remarks about security issues. In particular, we study variants of LWE where the coefficients of the public key matrix are not chosen uniformly modulo q but are instead “small”. We give evidence that binary matrices might be secure for LWE encryption. We remark that binary matrices are not secure for Ring-LWE encryption. The aim of the paper is not to make a complete proposal for practical use, but to raise some questions and to introduce some computational problems that may be interesting targets for cryptanalysis. We hope that scrutiny of these problems will shed further light on the practical aspects of the standard LWE problem