Space-efficient variants of cryptosystems based on learning with errors
Space-efficient variants of cryptosystems based on learning with errors
复制标题
基于错误学习的密码系统的空间有效变体
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Galbraith
中科院分区：
文献类型：
--
作者：
S. Galbraith
我们考虑基于带错误学习问题（LWE）的公钥加密。这种加密方案不被认为是实用的原因有几个，最常被引用的原因之一是公钥的大小。但是，有一种简单的方法可以大大减少公钥的大小。本文的目的是调查这样的想法，并考虑一些方法来实现LWE加密的设备相对较小的存储。我们注意到，一个更自然的方法，这样的设置将使用NTRU或环LWE，我们也适用于这些情况下，我们的想法。我们提出的一些变体不再具有基于LWE的标准加密所享有的同样严格的安全保证。因此，文件的大部分内容都是关于安全问题的评论。特别是，我们研究LWE的变体，其中公钥矩阵的系数不是以q为模均匀选择的，而是“小”的。我们给出的证据表明，二进制矩阵可能是安全的LWE加密。我们注意到二进制矩阵对于Ring-LWE加密是不安全的。本文的目的不是提出一个完整的建议，实际使用，但提出一些问题，并介绍一些计算问题，可能是有趣的目标密码分析。我们希望对这些问题的研究将进一步阐明标准LWE问题的实际方面。
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 encryption 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.