基于LWR问题的无证书全同态加密方案

无证书全同态加密(CLFHE)把全同态加密和无证书加密两者的优势结合了起来，它吸引了人们关注的目光。目前人们基于带误差学习(LWE)问题提出了几个CLFHE方案。带舍入学习(LWR)问题是LWE问题的变形。它免除了LWE问题中计算代价高昂的高斯噪声抽样。迄今为止人们尚未提出基于LWR问题的CLFHE方案。本文利用Gentry、Sahai和Waters提出的近似特征向量技术，基于LWR问题设计了一个CLFHE方案，并在随机预言机模型下证明了它满足INDr-CPA安全性。与已有的基于LWE问题的CLFHE方案相比，所设计的方案免除了耗时的高斯噪声抽样而具有更高的计算效率。

全同态加密(Fully Homomorphic Encryption, FHE)是一种具有特殊性质的公钥加密体制。它能在不解密的情形下对密文数据进行任意计算，即()()()()()11DecEnc, ,Enc, , µµµµ=ℓℓff，其中f 为任意函数。2009 年Gentry [1]基于理想格提出了第一个全同态加密方案。Genry 开拓性的工作迅速掀起了全同态加密研究的浪潮。2013 年Gentry、Sahai 和Waters [2]提出了一种构造全同态加密方案的新技术，他们称之为近似特征向量技术。

Gentry、Sahai 和Waters [2]利用近似特征向量技术， 基于带误差学习(Learning with Errors, LWE)问题[3]构造了一个层次型全同态加密(leveledFHE)方案。在层次型全同态加密方案中，方案的参数取决于方案所能计算的电路深度。

利用Gentry [1]提出的自举技术可以把层次型全同态加密方案转换为全同态加密方案。

本文的工作专注于层次型全同态加密方案， 故在下文的叙述中经常省去“层次型”一词。

无证书加密(Certificateless Encryption, CLE) [4]是一种新型公钥加密体制。它消除了基于身份的加密(Identity-Based Encryption, IBE) [5]固有的密钥托管问题，同时，它也避免了传统公钥加密系统中的公钥证书管理问题。无证书全同态加密(Certificateless Fully Homomorphic Encryption, CLFHE)结合了全同态加密和无证书加密两者的优势，它引起了人们的研究兴趣。2017 年Chen 等人[6]利用近似特征向量技术， 基于LWE 问题提出了一个无证书全同态加密方案，并在随机预言机模型下证明了它满足IND-CPA 安全性。最近，Li [7]利用近似特征向量技术，基于LWE 问题又提出了一个在随机预言模型下可证明安全的无证书全同态加密方案和一个在标准模型下可证明安全的无证书全同态加密方案。

带舍入学习(Learning with Rounding, LWR)问题[8]是LWE 问题[3]的变形。

LWE 问题需要进行高斯噪声抽样。高斯噪声抽样的计算开销非常大，严重制约了基于LWE 问题的全同态加密方案的计算性能。

LWR 问题不需要进行高斯噪声抽样。

近几年来， 人们基于LWR 问题构造了几个全同态加密方案[9] [10]。

与Gentry、Sahai 和Waters [2]提出的基于LWE 问题的全同态加密方案相比， 这些全同态加密方案[9] [10]由于舍弃了计算代价高昂的高斯噪声抽样其计算效率有了很大提高。截至目前，人们尚未提出基于LWR问题的无证书全同态加密方案。

鉴于无证书全同态加密的研究现状，本文致力于基于LWR 问题的无证书全同态加密方案的设计与分析。首先，利用Gentry、Sahai 和Waters [2]提出的近似特征向量技术，基于LWR 问题设计了一个无证书全同态加密方案。

其次， 在随机预言机模型下证明了所设计的方案满足INDr-CPA 安全性。

INDr-CPA比IND-CPA 的安全性更强，它包括IND-CPA 安全性和接收方匿名性。最后，本文具体给出了所设计的