论文 2012/078

源于经典 GapSVP 的全同态加密，无需模数切换

Zvika Brakerski

摘要

我们提出了一种新的基于 LWE 的全同态加密张量技术。在以往的所有工作中，每次乘法（在“刷新”之前）密文噪声都会二次增长 ($B \to B^2\cdot\poly(n)$)，而我们的噪声仅线性增长 ($B \to B\cdot\poly(n)$)。我们使用该技术构建一个\emph{尺度不变}的全同态加密方案，其属性仅取决于模数 $q$ 和初始噪声水平 $B$ 之间的比率，而不取决于它们的绝对值。我们的方案比以前的候选方案具有许多优势：它在整个评估过程中使用相同的模数（无需“模数切换”），并且该模数可以采用任意形式，包括 2 的幂，这对于实现具有明显的优势。此外，安全性可以\emph{经典地}简化为 GapSVP 问题的最坏情况困难度（具有准多项式逼近因子），而以前的构造只能展示 GapSVP 的量子简化。

注意： 由于拼写错误已修订。