Efficient Fully Homomorphic Encryption from (Standard) LWE

+1.FHE from (standard) LWE.pdf

522.2KB

Abstract

基于LWE假设的方案

Introduction

指出本文是基于LWE的方案并不直接依赖于格

We introduce the re-linearization technique, and show how to use it to obtain a somewhat homomorphic encryption that does not require hardness assumptions on ideals.

再线性化，并展示如何使用它来获得一个不需要对理想进行严格假设的同态加密

We present a dimension-modulus reduction technique, that turns our somewhat homomorphic scheme into a fully homomorphic one, without the need for the artificial squashing step and the sparse subset-sum assumption.

提出了一种维数模约化的方法（降维），该方法不需要人为的压缩步骤和稀疏子集和假设，将部分同态格式转化为全同态格式。

由此产生的全同态方案的密文非常短。这是非常理想的属性，将其他技术一起使用，可以实现非常有效的私有信息检索协议

1.1 Re-Linearization: Somewhat Homomorphic Encryption without Ideals

C-同态方案是允许对任一电路进行评估的方案。若一个C-同态方案的一个（略微增广）揭秘电路留在C中，那么这个方案就能转换（自举）成全同态加密方案。（类似python用自己写自己，能够解释自己）

（1）结果发现，能够计算一个非平凡的加法和乘法运算的加密方案已经很难实现。纵使不要求自举。Gentry的解决方案是基于环中理想的代数概念。在一个非常高的层次，信息被认为是一个环元素，密文是被一些“噪声”掩盖的信息。这种想法的新颖之处在于，噪声本身属于一个理想。

（2）密文的形式为（对于环中的某些）直接观察到该方案是加法同态的，事实上本文考虑的所有方案都是这样的。

这个理想的主要有两个性质：

假设理想中的一个随机元素，“掩盖”消息；

可以生成一个“毁灭”理想的秘密陷门，即实现

第一点保证安全性，第二点使密文相乘成为可能。

c1和c2分别是m1和m2明文加密后的密文

透过上面的式子可以看到，解密的时候，这个理想被毁灭，明文的乘积得以保留。

根据这个巧妙的解决方案，由第一个属性，需要对某些环中的理想（）做困难假设。Gentry的原始工作就是依赖于对理想格的困难假设。[DGHV10]则提出了一个不同的示例，它考虑了理想的整数。

Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In EUROCRYPT, pages 24–43, 2010. Full Version in http://eprint.iacr.org/2009/616.pdf.

这篇文章的一些同态方案是基于Regev[Reg05]首次提出的”带错误的学习”(LWE)。LWE假设指出，如果是一个维的“秘密”向量，那么的系数的“噪声”随机线性组合的多项式数在计算上与中的均匀随机元素是不可区分的。

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, STOC, pages 84–93. ACM, 2005.

其中和是均匀随机的，噪声是从一个输出数远小于的噪声分布中取样得到的（标准差较小的上的离散高斯分布）

LWE假设并不是指理想，事实上LWE问题至少和在任何格中寻找短向量一样困难。本段指出，求解LWE问题的最好已知算法在时间上几乎在维上呈指数运行。

LWE假设也特别适用于构造简单、高效和高表达能力的密码方案。本文作者从LWE构造一全同态加密方案证明了LWE的优势所在。