一种基于LWE的同态加密方案

摘要

目前同态加密体制主要建立在2个主要的问题之上：Regev的错误学习问题（LWE）和Howgrave-Graham的近似最大公因子问题（AGCD）.首先把LWE问题规约到AGCD问题上,然后基于AGCD问题,提出一种加法同态加密体制.与之前的体制相比较,其安全性不依赖于所谓的稀疏子集合求和问题（SSSP）的假定困难性,而是仅仅依赖于LWE问题的困难性.最后,给出了正确性分析和安全性证明.