具有一致秘密和错误的LWE问题及其应用  

LWE Problem with Uniform Secret and Errors and Its Application

作　　者：孙小超[1,2] 李宝[1,2] 路献辉[1,2] 

机构地区：[1]中国科学院信息工程研究所,北京100093 [2]中国科学院数据与通信保护研究教育中心,北京100195

出　　处：《计算机研究与发展》2014年第7期1515-1519,共5页Journal of Computer Research and Development

基　　金：中国科学院信息工程研究所密码研究专项基金项目(Y3Z0027103)

摘　　要：提出了一种新的带错误学习问题(learning with errors,LWE)的变种,这种变种中的秘密向量和错误向量的每一个分量都是取自于一个小区间上的一致分布,其中,运用了Applebaum等人提出的转换技术.这种技术将一致秘密的LWE样本映射到另一些LWE样本,这些样本的秘密是服从和错误一样的分布,同时只损失了一小部分的样本.这个变种有和标准LWE一样的最坏情形到平均情形的归约性,同时,它去除了标准LWE问题中的高斯抽样算法.基于新的变种,构造了一个密钥相关消息安全的公钥加密方案.方案去除了原来方案中的高斯抽样算法,取而代之的是小区间上的一致分布的抽样算法,从而降低了密钥生成算法和加密算法的开销.The learning with errors （LWE） assumption has been widely applied in cryptography for its unique properties in complexity. It is viewed as linear random decoding problem in Euclidian norm. Many variants of its average hardness are given in recent years. We introduce a variant of learning with errors problem in which the coordinates of secret and errors are all chosen from the uniform distribution over a small interval, where we use a transformation technique given by Applebaum et al. It maps LWE samples with uniform secret to LWE samples with the secret which accords to the same distribution of the errors. Meanwhile, there are only a small number of samples lost. The average hardness of our variant is based on the LWE with uniform errors. It enjoys a worst-to-average-case reduction and removes the gaussian sampler. We also construct a public-key encryption with key- dependent message security based on our new LWE variant. It is a variant of Regev＇s LWE-based schemes. Our scheme reduces the computational overhead of algorithms of key-generation and encryption by replacing the gaussian sampler, which costs a lot of time and space in practice, with the uniform sampler in small interval.

关 键 词：带错误学习问题 一致错误 秘钥相关消息 公钥加密算法 可证明安全 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]