同态加密算法毕业论文

所有的更新都放在我的博客中, 本文地址为 GSW同态加密方案确实如论文标题一样, 概念清晰明了, 其Intuition简单到一个刚学完线性代数的大一新生也能理解. GSW还支持基于属性的加密, 但本文中我们将不介绍这一部分内容. 当然, 完全理解GSW方案仍然需要用到一些比较进阶的知识, 如LWE问题的困难性等. 我们在本文中不会对这些知识做过多的介绍, 这些知识将在今后其他的博文中介绍. 关于同态加密的基础知识可以参阅博文 同态加密(0) 基础概念 , 这篇博文完成后, 地址将被更新到这里. GSW方案是由Craig Gentry [1] , Amit Sahai与Brent Waters于2013年提出的方案, 发表于论文[GSW13] [2] 中. 最基本的GSW同态加密方案的私钥( )是一个向量 [3] , 而所有的明文 都被加密一个矩阵 中, 其中 是以 为近似特征向量并以 为近似特征值的矩阵, 即我们要求这里可以看出， 我们只需要挑选 中非 的位(最好是选较大的位), 如第 位 , 并比较 与 的值就可以解出 的值. 一个需要注意的地方就是, 虽然 取自 , 但被视作是 中的元素, 因此具体的运算也是按照 的运算方式来进行. 我们也可以将噪声(error)显式地写出来, 记作 其中 是非常小的向量. 因此可以看出, 如果 确实是一个较小的噪声, 那么我们就可以正确地解出 . 现在我们来验证该加密方案具有同态性质. 现在假设有两个密文 , 对对应的明文分别是 , 即 其中 均为较小的噪声, 那么令 , 我们检验 的解密结果 这里可以看出, 确实是一个比较小的噪声项, 但是要让 的噪声比较小, 那么就需要让 是一个较小的矩阵(即其最大的元素较小), 我们稍后会解释如何做到这一点. 虽然说是乘法同态性质, 但是由于 , 我们也可以将 视作是做了同态的与(AND)运算. 与运算相对来说是比较简单的, 但是仅有与运算是不够的, 因为与运算是单调的, 单调的电路不可能是完备的, 我们需要实现一个超强的逻辑门----与非门的同态运算. 设 , 其中 为 阶单位矩阵, 则 根据之前的讨论, 如果 是一个较小的项, 我们有把握能从 中解出 . 到这里有没有一种心情舒畅的感觉? 与非门生万物, 我们确实可以通过不断地叠加与非门来实现相当复杂的函数运算, 并且由于与非门是完备的, 仅用与非门可以实现任何一个布尔函数. 虽然与非门非常强大, 但是每一次进行与非门运算, 都会导致新密文得噪声变得更大, 因此较多层的运算后, 噪声可能大得导致解密错误! 因此我们必须评估我们究竟能进行多少次的运算, 以及在快要达到极限的时候使用Bootstrapping技术. 这一点我们将在详细介绍方案的时候来说明. 这里我们要首先介绍一种工具, 我们称其为Lattice Gadget, 它的本质是一些代数运算, 能够辅助我们从标准的LWE加密方案生成满足同态性质的密文. 第一个运算是 , 它的作用是将一个 [4] 向量的每一位按照二进制展开, 即每一个元素 表示成二进制的形式 , 其中 [5] . 即 即将 的每一位都展开成了二进制, 变成 位, 整个结果一共是 位. 显然, . 类似的, 我们可以定义 的反函数 , 令 即将每一位的二进制表示重新组合成了 表示. 但是要注意的是, 并没有要求参数一定要是只由 构成的向量, 我们可以定义一个全新的函数 这个操作有什么意义? 它将那些不是全由 构成的 重新"抹平"成了由 中的元素构成, 并且能够保持其一定的性质. 下面介绍另一个不是那么好看, 但是却非常简单的操作 . 的功能也是将一个 向量转换为 向量, 但是却使用的是完全不一样的方式. 即将 的每一位, 展开为 位, 并且后一位是前一位的两倍. 使得整个向量变成 . 这样做的好处是, 如果 分别是 中的一位, 那么 前面一部分就是 中第 组的第 位, 而后一部分就是 中第 组的第 位, 那么显然有 如果将 直接写成 的形式, 我们还有实际上左右两边的两项都是由中间得到的, 这样就可以将左右两边连接在一起. 这样我们发现一个惊人的事实: 如果内积的第二项是标准的 结果的形式, 那么对第一项做 操作不会改变内积的结果! 实际上这也不难理解, 因为Flatten操作就是把数值过高的位分到权重更高的位而已. 但是这样做有一个好处就是, 使得 变成每一位都是 的 . 我们将以上几种记号都推广到对矩阵可用, 例如对于 , 令 其余几种记号也做类似的推广, 总之就是, 对矩阵的每一列的列向量做相应的操作. 这时我们发现, 如果密钥 确实是某个向量 进行 的结果, 即 , 那么就有 这可以使得 变成一个较小的矩阵, 而不改变最后与 的相乘的结果! 这样使得 可以代替 进行下一层的同态运算使得我们要求的 项较小! 我们直接将 的结果记作现在我们开始具体介绍方案. 我们要说的是, GSW方案根据解密算法的选区不同, 实际上有构造两套方案. 第一种是选择 作为解密算法, 该算法仅能解出 , 因此整个同态运算中主要用与非门构建逻辑电路进行计算. 另一个解密算法 可以解出 , 这样就可以自然地使用加法与乘法进行运算. 首先我们要说的是, GSW并不是一个标准假设下的全同态加密方案. GSW如果要做到全同态加密, 需要用到Bootstrapping, 进而需要用到LWE加密方案的Circular Security假设(即用一对公私钥中的公钥来加密私钥相关信息的加密结果是安全的). 我们这里不介绍Bootstrapping的具体过程, 仅介绍Somewhat HE. 这里的参数较多, 需要逐一解释一下. 首先 是安全参数, 表示密码方案中基于的困难的问题的复杂程度, 所有的参数都应该(直接或间接)基于这个参数选择. 参数 表示同态运算的层数, 由于同态运算的层数由噪声的占比决定, 因此想要做更多的同态运算次数, 那么噪声就不应该太快掩盖 , 就应该相应地选择大一些. 而LWE问题的错误分布 还有维数 按理来说是应该根据 来选择, 但是这两个参数是可以根据 来进行权衡(tradeoff)的, 这里直接用基础参数 来代替 . 而参数 则是为了方便我们进行表示而引入的记号, 并且他们在前面也出现过. 实际上这里就是变相生成了一组LWE问题的实例, 如果对这里不熟悉, 可以跟进我的Blog学习知识. 相关博文更新后会在这里补充地址. 这就是整个加密的过程, 其中 操作是为了保证 是一个较小的矩阵, 我们知道 是一个 向量, 那么 也是一个小噪声, 因此密文符合我们的要求. 实际上这里的解密过程就是比较 与 的值. 而为了使得解密出错的概率最低, 所以选择 较大的一项, 这样使得错误最多可以积累到 而解密不出错. 接下来我们看一下进行 层同态运算后, 噪声的增长. 我们知道, 两个噪声为 的密文行一次加法运算, 噪声增长到 . (这里 , 表示解密中的噪声项), 而两个噪声为 的密文乘法结果的的噪声项为 , 最多为 . 如果初始噪声为 的密文进行 层运算, 则噪声最多增长为 , 由这一点可以看出, 我们最多可以进行对数次数的同态运算. 但是对数次的运算已经足够用于解密运算, 因此我们可以基于Circular Security假设, 使用Bootstrapping技术实现全同态.