用于双线性型的高效同态加密方案

摘要

在一个示例性实施例中，计算机可读存储介质有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接收信息B，该信息B将根据具有加密函数的加密方案被加密为密文C；以及根据加密函数来加密B以获取C，该方案使用公钥A，其中B、C和A是矩阵，加密函数接收A和B作为输入，并将C输出为C~AS+pX+B(modq)，S是随机矩阵，X是误差矩阵，p是整数，q是奇素数。在其他实施例中，加密方案包括解密函数，其接收至少一个私钥T（矩阵）和C作为输入，并将B输出为B=T

说明书

技术领域

本发明的示例性实施例通常涉及加密和解密算法，且更具体而言，涉 及用于双线性型的同态加密方案。

背景技术

支持对加密数据的操作（例如同态加密）的加密方案在安全计算中非 常有用。

同态加密方案是指这样的加密方案，其中，在两个或更多个密文上执 行的一个或更多个操作（例如加法、乘法）转化为被解密的明文（即密文 的解密）。例如，如果密文之和(C₁+C₂)的解密产生相应的明文之和(B₁+B₂) （可能模上（modulo）某个值）：dec(C₁+C₂)→B₁+B₂，则可称加密方 案是加法同态的。许多公钥密码系统支持加密数据的相加或相乘，但要同 时实现两者看来很难。

已知使用例如Yao的“加密电路”（garbled circuit）技术[16,12]，可 以实现对加密数据来计算任意函数，但是密文大小以及解密复杂度至少会 随着被计算的电路中的门数而线性增加。此外，Sander等[15]描述了一种 允许评估任意电路的技术，但是密文大小随着电路深度成指数增加。这两 种方法都可以仅使用“一般难度假设”（例如双流不经意传输协议（two-flow  Oblivious-Transfer protocol）的存在等）来实现。

Boneh、Goh和Nissim描述了一种密码系统，其允许任意数量的加法 和一次乘法，而不会增加密文大小[5]。该方案在这里被称为BGN密码系 统。BGN密码系统的安全性基于允许双线性映射（bilinear map）的组合 阶群（composite-order group）中的子群成员问题（sub-group membership problem）。该密码系统直接隐含了一种用于评估2-析取范式（2DNF）公 式（或更一般地双线性型）的高效协议。Boneh等还描述了应用BGN密 码系统来改进私密信息检索方案（PIR）的效率以及用于投票协议（voting  protocol）。

更近以来，Aguilar Melchor、Gaborit和Herranz在[2]中描述了一种 “模板”，其用于将某些加法同态的加密转换为同时允许加法和乘法的加 密系统。他们示出了如何使用该模板来将BGN密码系统与Kawachi等[11] 的密码系统进行组合，由此获得一种密码系统，其支持两次乘法和任意加 法，基于子群成员问题和格（lattice）中唯一最短向量问题两者的难度。 他们还示出了如何将该模板与Aguilar Melchor等[1]的密码系统一起使用， 以获得无限制的乘法深度，其中密文大小随着乘法深度成指数增加，但支 持加法而不会增加大小。（该最后实现的安全性基于相对未被研究的难度 假设，其被称为“微分背包向量问题”（Differential Knapsack Vector  Problem））。

已知人们可以从格或线性码来构造加法同态加密方案。密文中隐性地 包含“误差”，其随着密文被一起操作（例如相加、相乘）而增长。因此， 所产生的密文不会具有和原始密文（例如和单独解密的）一样的分布，并 且在某个点上，误差会变得足够大从而引起错误的解密。为此，在该情形 下，同态有时被称为“伪同态”（pseudohomomorphism）或“限界同态” （bounded homomorphism）。

最近，Gentry描述了一种完全同态的密码系统[9]，其支持多项式数量 （polynomially many）的加法和乘法，而不会增加密文大小，其安全性基 于在理想格（ideal lattice）中找到最短向量的难度[8]。

发明内容

在本发明的一个示例性实施例中，一种计算机可读存储介质有形地体 现了可由机器执行以执行操作的指令程序，所述操作包括：接收信息B， 该信息B将根据包含加密函数的加密方案被加密为密文C；以及根据该加 密方案的加密函数来加密信息B以获取密文C，其中，所述加密方案使用 对应于至少一个私钥T的至少一个公钥A，其中所述信息B、密文C、至 少一个公钥A和至少一个私钥T是矩阵，其中，所述加密函数接收至少一 个公钥A和信息B作为输入，并将密文C输出为C←AS+pX+B(modq)， 其中S是随机矩阵，其中X是误差矩阵，其中p是整数，其中q是奇素数。

在本发明的另一示例性实施例中，一种装置包括：至少一个存储介 质，其被配置为存储信息B，该信息B将根据包含加密函数的加密方案 被加密为密文C；以及至少一个处理器，其被配置为根据该加密方案的加 密函数来加密信息B以获取密文C，其中，所述加密方案使用对应于至少 一个私钥T的至少一个公钥A，其中所述信息B、密文C、至少一个公钥 A和至少一个私钥T是矩阵，其中，所述加密函数接收至少一个公钥A和 信息B作为输入，并将密文C输出为C←AS+pX+B(modq)，其中S是随 机矩阵，其中X是误差矩阵，其中p是整数，其中q是奇素数。

在本发明的又一示例性实施例中，一种计算机可读存储介质有形地体 现了可由机器执行以执行操作的指令程序，所述操作包括：接收密文C， 该密文C将根据包含解密函数的加密方案被解密为信息B；以及根据该加 密方案的解密函数来解密密文C以获取信息B，其中，所述加密方案使用 至少一个私钥T，其中所述信息B、密文C和至少一个私钥T是矩阵，其 中，所述解密函数接收至少一个私钥T和密文C作为输入，并根据B= T^-1·(TCT^tmod q)·(T^t)^-1modp来输出信息B，其中p是整数，其中q是 奇素数。

根据本发明的再一示例性实施例，一种装置包括：至少一个存储介质， 其被配置为存储密文C，该密文C将根据包含解密函数的加密方案被解密 为信息B；以及至少一个处理器，其被配置为根据该加密方案的解密函数 来解密密文C以获取信息B，其中，所述加密方案使用至少一个私钥T， 其中所述信息B、密文C和至少一个私钥T是矩阵，其中，所述解密函数 接收至少一个私钥T和密文C作为输入，并根据B=T^-1·(TCT^t mod q)·(T^t)^-1modp来输出信息B，其中p是整数，其中q是奇素数。

根据本发明的又一示例性实施例，一种计算机可读存储介质有形地体 现了可由机器执行以执行操作的指令程序，所述操作包括：接收信息B， 该信息B将根据包含加密函数和解密函数的加密方案被加密为密文C；以 及根据该加密方案的加密函数来加密信息B以获取密文C，其中，所述加 密方案使用至少一个公钥A和对应于该至少一个公钥A的至少一个私钥 T，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵， 其中且其中n表示安全参数且 m,q＝poly(n)，其中q是奇素数，其中p是整数，其中q＞p，其中，所 述加密函数接收A和B作为输入，并将密文C输出为C←AS+pX+B(mod q)，其中S是随机矩阵且其中X是误差矩阵且其中是误差分布，其中β是由β＝1/poly(n)给出的高斯误差参数， 其中，所述解密函数接收T和C作为输入，并根据B=T^-1·(TCT^t mod q)·(T^t)^-1modp来输出信息B，其中，所述加密方案是同态的并支持计算 双线性型。

附图说明

通过下列详细描述并结合附图，本发明的实施例的上述和其他方面将 变得更为明显，在附图中：

图1A示出了根据本发明的示例性实施例的示例性加密操作/函数；

图1B示出了根据本发明的示例性实施例的示例性解密操作/函数；

图1C示出了根据本发明的示例性实施例的示例性密钥生成（KeyGen） 操作/函数；

图1D示出了根据本发明的示例性实施例的示例性密文加法操作/函 数；

图1E示出了根据本发明的示例性实施例的示例性密文乘法操作/函 数；

图1F示出了根据本发明的示例性实施例的示例性“简单解密”操作/ 函数；

图2示出了系统的框图，本发明的各种示例性实施例可以在该系统中 实现；

图3描述了逻辑流图，其示出了根据本发明的示例性实施例的示例性 方法的操作以及示例性计算机程序的操作；

图4描述了另一逻辑流图，其示出了根据本发明的示例性实施例的示 例性方法的操作以及示例性计算机程序的操作；

图5描述了又一逻辑流图，其示出了根据本发明的示例性实施例的示 例性方法的操作以及示例性计算机程序的操作；

图6描述了再一逻辑流图，其示出了根据本发明的示例性实施例的示 例性方法的操作以及示例性计算机程序的操作；且

图7描述了又一逻辑流图，其示出了根据本发明的示例性实施例的示 例性方法的操作以及示例性计算机程序的操作。

具体实施方式

1.简介

本发明的示例性实施例构造了一种简单的公钥加密方案，其支持计算 双线性型（例如多项式数量的加法和一次乘法），类似于Boneh、Goh和 Nissim的密码系统（BGN）。安全性基于带误差学习（learning with errors， LWE）问题的难度，已知该问题和某些最坏情形的格问题难度一样。

示例性密码系统的某些特征包括支持大的消息空间、容易获得公式私 密性、比BGN有更好的消息到明文扩张率、以及容易将两个加密的多项 式相乘。此外，可以使得该方案是基于身份且泄露弹性的（leakage resilient） （以更高的消息到明文扩张率为代价）。

这里对“Z”的任何和所有提及（例如）都应被理解为对应 于所有整数的集合。此外，这里对秘密、密钥或陷门（trapdoor）的任何 和所有提及都应被理解为对应于私钥（例如，如在公钥－私钥加密方案中）， 反之亦然。

这里使用的术语是为了描述本发明的各种示例性实施例的目的，而不 是要限制本发明。如这里所使用的，单数形式“一个”和“该”旨在也包 含复数形式，除非上下文明确另外说明。还应该理解，术语“包含”和/ 或“包括”在本说明书中使用时，表示所述特征、整体、步骤、操作、元 素和/或组件的存在，但不是要排除一个或多个其他特征、整体、步骤、操 作、元素、组件和/或其组合的存在或添加。

1.1.引言

在本文中，描述了一种示例性加密方案，它是加法同态的，并且还支 持一次乘法。该示例性方案基于Gentry、Peikert和Vaikuntanathan[10]提 出的陷门函数（以下将被称为GPV陷门函数）。在GPV陷门函数中，“公 钥”是矩阵（对于参数q＞p且m＞n），且相应的陷门是具有小的 条目的满秩整数矩阵T∈Z^m×m，从而TA＝0(mod q)。该示例性密码系统中 的公钥和私钥和GPV陷门函数中的完全一样。通过设置

C＝AS+pX+Bmodq

来加密矩阵其中，S是随机“系数矩阵”且X是具有 条目的“噪声矩阵”X ∈Z^m×m，从而X的条目比q要小很多。密文矩阵可 以被相加，并且支持单次矩阵相乘（C^t是C的转置矩阵）。 为了解密，令

B＝T^-1·(TCT^tmodq)·(T^t)^-1modp

示例性方案的安全性等价于带误差学习（LWE）的难度。该问题与众 所周知的“具有噪声的奇偶性学习”（learning parity with noise）相关， 它在基于格的密码学的研究中已经成为标准。该问题最初由Regev[14]提 出，并由Regev[14]和Peikert[14]表明，它和整数格中的各种问题的最坏 情形实例的难度一样。这里简要地指出，LWE问题与关联误差分布相关。

1.2贡献

该示例性方案与以前的工作的主要区别可能在于作为基础的难度假 设。特别地，示例性方案是所报告的第一种基于LWE且不限于加法同态 的密码系统。此外，示例性方案非常高效：它可以在时间内对m²个 元素的矩阵进行加密，且解密所花的时间相当。

示例性方案与BGN密码系统的一个重要区别是，BGN密码系统只能 对来自小的空间的消息加密（因为在解密时，只能恢复群元素g^m，并且然 后需要搜索消息m）。在示例性方案中，可以对于任何p对Z_p上的矩阵加 密，只要q比p足够大。一个相关的优势是，通过选择大的模数p，可以 使得示例性方案具有O(1)的密文扩张（而BGN密码系统将O(logn)比特的 明文扩展为O(n)比特密文）。

需要注意，在示例性方案中定义消息空间的模数p可以由加密机动态 选择：同一公钥/私钥对可以被用来加密/解密消息模上很多个不同的域（或 环）。示例性方案还支持密文隐藏（blinding）（即，给定的密文被转换为 加密同一事物的随机密文），以及更强的模隐藏属性：给定加密了矩阵 的密文，且给定p的某个除数p^t，可以生成随机密文来加密 Bmodp^t。例如，如果原始明文矩阵具有n比特的数字（例如在中）， 则可以隐藏密文，从而消去除了B中条目的最低有效位之外的一切。

（标准）隐藏属性以及消息空间选择灵活性的一个结果是，示例性系 统提供了用于公式私密安全计算的非常简单的过程。即，很容易在密文上 计算2DNF公式（或更一般的双线性型），而同时向私钥的持有者隐藏关 于公式本身的一切（除了在给定输入上应用它的结果）。

最后，示例性方案继承了基于LWE的密码系统带有的大量灵活性。 特别地，使用Gentry等[10]的构造，可以使得它是基于身份的，并且使用 Dodis等[6]的最近结果，可以使得它是泄露弹性的。这两种应用都来源于 观察到[10]中的“对偶Regev密码系统”（dual Regev cryptosystem）可以 被描述为示例性密码系统的特殊情形。

应用

很明显，示例性方案可以在应用中被用作Boneh等[5]在论文中讨论的 投票和PIR的简易替代（drop-in replacement）。此外，由于示例性方案 天然地加密矩阵，对受益于批处理（batching）的应用，以及在高效线性 代数很重要的时候，它是很好的匹配。批处理的某些例子包括（例如需要） 将多项式（其系数将被编码在明文矩阵的条目中）或大整数（其比特被编 码表示将在明文矩阵的条目中）相乘的应用。在5.3节中，描述了这些是 如何在矩阵中加密的，从而m×m矩阵的单次相乘可以被用来将两个阶 -(m-1)的多项式（或两个m比特的整数）相乘，从而结果不会泄露除了其 乘积以外的关于输入的任何信息。

1.3示例性方案总览

下面简要描述了示例性方案的构造的主要思想。示例性方案基于决策 LWE问题的难度，该问题描述了对于安全参数n和多项式大小 （polynomially large)的m，给定均匀随机矩阵向量As+x是伪 随机的（对于均匀的以及“小的误差向量”）。决策LWE 的难度目前是基于格的密码系统的研究中的一个标准假设，Regev[14]和 Peikert[13]表明该问题和解决若干最坏情形下的标准格问题难度一样。 示例性方案的公钥是随机矩阵且私钥是具有小的条目的“陷 门矩阵”T，满足T·A＝0(mod q)。加密方案的消息空间为m乘m整数矩阵 modp的环（具有矩阵相加和相乘的操作）。该方案可以工作于任何环Z_p上，只要p比LWE模数q足够小。见第3节中更详细的描述。

为了加密矩阵加密机从LWE误差分布中选择随机矩阵 和“小误差矩阵”X。然后密文C为

C＝A·S+p·X+B

需要留意，密文是（低阶矩阵）+（可被p整除的小噪声）+（消息） 的形式。对密文解密涉及在密文左侧乘上陷门矩阵T（其除去了低阶矩阵）， 然后乘上T^-1modp来消去噪声，

B＝T^-1·(T·Cmodq)modp.

这是可行的，因为T、X和B都小，从而T·(pX+B)中的所有条目都 小于q，这意味着(T·Cmodq)在整数上等于T·(pX+B)（不仅是mod q）， 且因此它等于T·Bmodp。

容易看到，若干个矩阵的加密之和将被解密为这些矩阵之和，只要（例 如T·∑C_imodq中的）所有条目仍然小。为了获得两个矩阵的相乘的加密， 令

这看起来和的加密类似（且确实误差矩阵X很小），除了额外的 交叉项（cross term）S′A^t。为了解密该乘积密文，首先令M＝T·C·T^t modq， 由此消去AS和S′A^t两项，然后B＝T^-1·M·(T^t)^-1 modp。

现在清楚了为什么该方案（例如，仅）支持单次乘法：超出此之外将 存在S·A·S′形式的交叉项，其不能再用陷门T来消除。

预备条件

符号表示

用小写字母（a,b,…）来表示标量，用小写黑体字母（a,b,…）来表示 向量，并用大写黑体字母（A,B,…）来表示矩阵。用||v||来表示向量v的欧 几里得范数（Euclidean norm），并用||v||_α或||M||_α来分别表示向量或矩 阵中的最大条目。将操作(amod q)认为是将整数a映射到区间 (-q/2，+q/2]。

2.1带误差学习（LWE）

LWE问题是由Regev[14]作为“具有噪声的奇偶性学习”的一般化引 入的。对于正整数n和q≥2、向量以及Z_q上的概率分布χ，令A_s，χ为通过随机地均匀选择向量及噪声项x←χ、并输出 $(a,<a,s>+x)\in Z_q^n\times Z_q$来获得的分布。

定义1（LWE）：对于整数q＝q(n)和Z_q上的误差分布χ＝χ(n)，带 误差学习问题LWE_{n，m，q，χ}被定义为：给定来自A_s，χ的m个独立样本(对于 某个），以显著的概率来输出s。

LWE问题的决策变量被表示为distLWE_{n，m，q，χ，}其用来（以不可忽略的 优势）将根据A_s，χ(对于均匀随机的）选择的m个样本与根据上的均匀分布来选择的m个样本进行区分。

对于加密应用，主要兴趣是决策问题distLWE。Regev[14]表明，对 于素数模数q，distLWE可以被约简为最坏情形的LWE，其中参数m中 有达到q·poly(n)因数的损失。

有时，可以发现使用紧密的矩阵符号来描述LWE问题LWE_{n，m，q，χ}是方 便的：给定(A,As+x)，其中是均匀随机的，是LWE秘密， 且x←χ^m，找到s。类似的矩阵符号也被用于决策版本distLWE。

高斯误差分布

主要兴趣是LWE和distLWE问题，其中，Z_q上的误差分布χ是由高 斯分布导出的。对于任何β＞0，实数上的高斯分布的密度函数由 D_β(x)＝1/β·exp(-π(x/β)²)给出。对于整数q≥2，将定义为通过抽取 y←D_β并输出而得到的Z_q上的分布。将LWE_{n，m，q，β}记为 的简写。

这里是关于高斯分布（适应于误差分布）的几个基本事实；例如见 [7]。（在下面，压倒性概率意味着概率1-δ，对于在n中可以忽略的δ）。

事实1：令β＞0且q∈Z，并令向量x被选为此外，令y∈Zⁿ 为任意向量并令则以压倒性概率|<x，y>|≤βq·g·PyP。

事实2：令y∈R为任意的。分布和之间的统计距离至多为 |y|/(βq)

LWE_{n，m，q，β}的难度的证据来自于Regev[14]的结果，其给出了从逼近最坏 情形下的n维格上的某些问题到在因数之内在时对于任 何希望的m＝poly(n)解决LWE_{n，m，q，β}的量子约简（quantum reduction）。最 近，Peikert[14]也给出了针对有类似参数的其他问题的经典约简（classical  reduction）。

如这里所使用，相对属性“小的”是从中抽取的。通常，“小的” 值或整数的大小达到q·β。类似的，“大的”值或整数比q·β大很多。

2.2陷门抽样（trapdoor sampling）

示例性加密方案的基础是最初由Ajtai[3]所构造、而后由Alwen和 Peikert[4]改进的陷门抽样函数。陷门抽样过程生成（几乎）均匀随机的矩 阵以及T∈Z^m×m从而：(a)T·A＝0(mod q)，(b)T是可逆的，且(c)T 的条目是小的（例如大小为O(nlog q)）。

陷门T可以被用来解决相对于A的LWE问题，即，给定y=As+x， 其中x是任何“足够短”的向量，它可以被用来恢复s。这可以如下来实 现：计算

Ty＝T(As+x)＝TAs+Tx＝Tx(mod q)

其中，最后的等式成立，因为T的行属于格Λ^⊥(A)。现在，由于T和x两 者都包含小的条目，向量Tx的每个条目都要小于q，且由此Txmodq是 Tx本身。最后，乘上T^-1（其是定义良好的（well-defined），因为T是基 并由此具有满秩）将给出x。LWE秘密s然后可以用高斯消去法来恢复。 Alwen和Peikert[4]的结果在下面描述。

引理1（[3,4]）存在高效的算法TrapSample（陷门抽样），其对于输 入1ⁿ、正整数q≥2以及poly(n)限界的正整数m≥8nlog q，输出矩阵 以及T ∈Z^m×m从而：

·A在上统计地接近于均匀，

·T的行构成格${\Lambda }^{\perp }\left(A\right)\stackrel{\mathrm{def}}{=}\{w\in Z^m:w·A=0\left(\mathrm{mod}q\right)\}$的基，

·T的所有行的欧几里得范数(且因此|T|_∞）由O(nlogq)限界。(Alwen 和Peikert[4]断言O(·)中隐藏的常数不大于20）。

注意到由于T的行跨越格Λ^⊥(A)，可得出det(T)＝qⁿ，由此对于与q 互素的任何p，可知T是modp可逆的。

3.示例性加密方案

令n表示安全参数。系统的其他参数为三个数字m，p，q＝poly(n) （q＞p，奇素数）和高斯误差参数β＝1/poly(n)。

见3.2节中这些参数的具体和示例性的实例化。对于这些参数，消息 空间是m乘m矩阵的集合，即公钥为矩阵私钥为矩阵 且密文为矩阵

示例性加密方案包括（例如，至少）下列三个算法：

KeyGen(1ⁿ)：运行引理1中的陷门抽样算法TrapSample来获取矩阵 及陷门矩阵(A，T)←TrapSample(n，q，m)。公钥为A且私 钥为T。

选择随机矩阵（例如均匀随机矩阵）和“误 差矩阵”输出密文

C←AS+pX+B(mod q)

（这里，pX表示将矩阵X的每个条目乘以p）。

Dec(T,C)：令E ←TCT^tmodq，然后输出B←T^-1E(T^t)^-1modp。

为了表明解密可行，回想T·A＝0(mod q)且由此 TCT^t＝T(pX+B)T^t(modq)。如果此外T(pX+B)T^t的所有条目都小于q， 则还可以得到整数上的等式E＝(TCT^tmod q)＝T(pX+B)T^t以及因此 T^-1E(T^t)^-1＝B(modp)。这意味着，可以进行正确的解密，只要将参数β 设置为足够小，从而T(pX+B)T^t的所有条目有很大的概率都小于q/2。

备注1：注意到，解密时在右侧乘上T^t和(T^t)^-1在这里是冗余的—— 相反可以仅计算B←T^-1(TCmodq)modp。如下所述，为了解密乘积密文， 右侧相乘是需要的。和GBN密码系统不同，在示例性方案中，“正常密 文”和“乘积密文”位于同一空间，且可以用相同的解密过程来对两者进 行解密。

此外，可以使用修改的陷门T′＝(T^-1modp)·T（整数上的乘积）来优 化掉乘以T^-1和（T^t)^-1的需要。很清楚，有T′A＝0(mod q)，且T′的条目 不会比T的那些条目大很多（因为(T^-1modp)中的所有条目的绝对值最 多为p/2）。

3.1同态操作

加法

给定将分别被解密为B₁、B₂的两个密文C₁、C₂，很容易看到矩阵 C＝C₁+C₂modq将解密为B₁+B₂mod p，只要任何条目都没有“溢出”。 特别地，如果有C₁＝AS₁+pX₁+B₁且C₁＝AS₂+pX₂+B₂，则

C＝C₁+C₂＝A(S₁+S₂)+p(X₁+X₂)+(B₁+B₂)

其将被解密为B₁+B₂，只要T(p(X₁+X₂)+B₁+B₂)T^t中的所有条目都小 于q/2。见3.2节中精确参数的例子。

乘法

给定将分别被解密为B₁、B₂的两个密文C₁、C₂，计算乘积密文 如果有C₁＝AS₁+pX₁+B₁且C₁＝AS₂+pX₂+B₂， 则

于是，乘积密文具有AS+pX+B+S^tA^t的形式。

和前面一样，可以看到TCT^t＝T(pX+B)T^t(modq)，且如果T(pX+B)T^t中的所有条目都小于q/2，则有整数上的E＝(TCT^tmod q)＝T(pX+B)T^t，且 因此T^-1E(T^t)^-1＝B(modp)。下面讨论了允许该结果成立的示例性参数。

3.2设置参数

定理2：固定安全参数n、参数p和任何c＝c(n)＞0。令q，m，β被设置 为

q＞2²⁰p²(c+4)³n^3c+4log⁵n，q为素数，

$\beta =\frac{1}{27p{n}^{1+(3c/2)}\log n\log q\sqrt{\mathrm{qm}}}$

则上述具有参数p，n，m，q，β的示例性加密方案支持矩阵环上的 (任意阶中的）n^c次加法和一次乘法。

备注3：注意到定理2中，对于非常数c允许n^c次加法。需要这样做 的原因是为了获得具有大系数的密文的线性组合。特别地，如果有密文矩 阵C₁，C₂，...，可以同态地计算∑α_iC_i，只要|∑α_i|＜n^c。

4.扩展和应用

4.1作为基础的环的动态选择

注意一旦参数固定，可由加密机适应性地对用于明文的基础环进行选 择。即，使用相同的公钥和私钥T，加密机可以选择基础环为Z_r，对于任 何r≤p（由此计算密文为C=AS+rX+B），且解密机可相应地解密。

4.2公式私密性

如到目前所描述的，该方案并不保证针对私钥持有者的“公式私密性”。 例如，给定一个密文矩阵C，解密机能够对通过将身份加密与零矩阵加密 相乘来获取该密文的情形和通过将零矩阵的两个加密相乘来获取该密文的 情形进行区分。

这种缺陷可以用标准技术来补救。首先稍微增加模数的大小：从如定 理2规定的q变成q′≥q·2^ω(logn)。然后，给定加密某个明文矩阵mod p的 密文矩阵C^＊，通过设置

$C\leftarrow C^{*}+{\mathrm{AS}}_1+{\mathrm{pX}}^{*}+S_2^t{A}^t,$

来隐藏它。其中S、S’在中是均匀的，且X’的每个条目是从中 选择的，β’超多项式地（super-polynomially）大于在方案中使用的参数 β。

根据事实2可以表明，所添加的X’中的噪音“淹没了”该密文的来 源的所有痕迹。也就是，产生的密文是C＝AS′₁+pX′+B+(S′₂)^tA^t的形式，其 中S′₁、S′₂是随机的（例如，均匀随机），B是对应的明文，且X’的分布 几乎独立于该密文矩阵的起源。

注意，即使加密的明文矩阵是在更大的环Z_p’中选择的，也可以使用 相同的隐藏技术，只要在隐藏过程中参数p能整除原始的p’。

4.3加密多项式和大整数

为了加密多项式或大数，以这样的方式将其编码为矩阵，从而可以利 用由示例性方案天然支持的矩阵运算，以便对这些多项式或数进行操作。

从多项式开始：众所周知如何将两个多项式的系数嵌入到两个矩阵中， 从而将这些矩阵相乘将产生最终乘积多项式的所有系数。例如，对于两个 多项式和可使用：

$A=\left(\begin{array}{ccc}{a}_3& a_2& a_1\\ & a_3& a_2\\ & & a_3\end{array}\right)B=\left(\begin{array}{ccc}{b}_1& b_2& b_3\\ & b_1& b_2\\ & & b_1\end{array}\right)\Rightarrow {\mathrm{AB}}^t=\left(\begin{array}{ccc}{a}_1{b}_3+a_2{b}_2+{a3b}_1& a_1{b}_2+a_2{b}_1& a_1{b}_1\\ a_2{b}_3+a_3{b}_2& *& *\\ a_3{b}_3& *& *\end{array}\right)$

注意以上乘积矩阵不是私密的，因为其不仅揭示了乘积多项式的系数。 这可以通过添加具有零第一列和第一行以及其他各处都为随机条目的矩阵 的加密来容易地解决。而且，这种简单的嵌入是“浪费的”，因为其会导 致O(m)的密文扩张率（使用m×m矩阵来加密阶-（m-1）多项式）。更经 济的嵌入是可能的。

转到整数乘法，使两个m比特整数相乘的一种明显的方式是，仅将明 文空间设置为Z_p，对于某个p≥2^2m，但使用这么大的明文空间来工作很不 方便。因此，希望寻找一种使用小的输入空间来实施大整数乘法的方法。 一种可能性是使用用于多项式的同样技术，将具有二进制表示a＝∑α_i2ⁱ的 整数视为在x=2处评估的二进制多项式给定两个整数a、b，在明文 空间Z_p对于某个p≥m上加密对应的多项式的二进制系数。读取乘积多 项式的系数，随后计算整数上的

但是，这种解决方案不是私密的，因为其泄露了更多关于a、b的信息， 而不仅是它们的整数乘积。使其私密的一种方法是向乘积矩阵的第一列和 行中加入随机元素r_i∈Z_p，使得∑_i2_ir_i＝0(modp)。这将使得私钥持有者能恢 复a·b(modp)。用不同的p’重复若干次，随后可使用中国剩余（Chinese  remaindering）来完全恢复a·b。

4.4两个中的两个（Two-Out-Of-Two）解密

注意到对于示例性密码系统，如果具有在两个不同的公钥下的两个矩 阵的加密，可将这两个密文相乘，由此获得对应于两个明文矩阵的乘积的 “密文”。然后，通过将两个秘密密钥放在一起，该“密文”可被解密。

更详细地，假设具有两个公钥A₁和A₂，以及对应的两个秘密密钥T₁和T₂，这两对都被定义为模上相同的素数q。（还假设为了简单起见，两 对都使用相同的参数n和m，尽管这种假设不是必须的）。随后，给定两 个密文：

C₁＝A₁S₁+pX₁+B₁和C₂＝A₂S₂+pX₂+B₂，

可计算“乘积密文”C=C₁C₂^t（mod q），其对应于明文B₁B₂^t（modp）。 如果知道T₁和T₂两者，通过进行以下设置，可以恢复该明文：

$B\leftarrow T_1^{-1}·\left(T_1{\mathrm{CT}}_2^t\mathrm{mod}q\right)·{\left(T_2^t\right)}^{-1}\mathrm{mod}p$

4.5基于身份和泄露弹性的BGN-类型的加密

下面示出了如何将一次乘法同态性扩展至仅仅标准公钥加密之外，以 获得更多“先进特征”，例如作为非限制性的例子的基于身份的加密和泄 露弹性。这来自于如下简单的观察，即[10]中的“对偶Regev密码系统” （具有不同的输入编码）可被视为示例性加密方案的特例（针对矩阵的特 定形式），且因此其支持相同的同态操作。IBE（在随机预言模型（random  oracle model）中）直接成立，因为Gentry等人在[10]中示出了如何从主 密钥中导出对偶Regev密钥，且泄露弹性成立，因为Dodis等人在[6]中证 明对偶Regev密码系统是泄露弹性的。

回想[10]中的“对偶Regev密码系统”：公钥是矩阵且秘密 密钥是对偶中的一个短向量，即，短的从而而且， 中的最后一项总是-1。

在[10]中描述的密码系统中，通过选择均匀的向量和小的误差 向量来加密比特b，且随后将比特b编码在密文向量的一个条目的 “最高有效位”中，即，但是为了获得同态 性，将输入编码最低有效位中，设置利用 这样的输入编码，可将对偶Regev密码系统视为示例性密码系统的特例， 其中公钥是相同的矩阵A，且私钥不是满秩矩阵，而是秩1矩阵。矩阵T、 S、X、B被定义为：

$T=\left(\begin{array}{c}-\overrightarrow{u}-\\ 0\end{array}\right),S=\left(O\overrightarrow{s}\right),X=\left(O\overrightarrow{x}\right),B=\left(\begin{array}{cc}0& \\ & b\end{array}\right)$

（即，除了T的顶行之外都是零，除了S、X的最右边的列之外都是零， 且除了B的右下角元素外都是零。）

很容易看到语义安全可从LWE得出。由于密钥仅是对偶Regev密钥， [6]中同样的证据表明其能保持安全，即使面对密钥的部分泄露。而且，在 [10]中示出了该密钥可以如何从（随机预言模型中的）基于身份的设置中 的主密钥来计算。

利用这些选择，大部分“密文矩阵”是零，从而需要输出为密文的确 实只是一个向量，其隐含地编码了矩阵 随后对隐含的矩阵应用同态操作，即，加法仅是逐元素相加模 上q，且两个向量的乘法是外积（outer-product）运算。

为了解密密文矩阵，将它从左侧和右侧乘以密钥向量模上q然后 模上2，来约简该结果。由于明文矩阵B的特殊形式，这跟在左边与T相 乘和在右边与T’相乘且随后仅获取结果的右下元素是一样的。

尽管矩阵T不再具有逆矩阵，仍然可以恢复隐藏的比特b。这可以通 过设置来简单地实现，而不需要乘以逆矩阵，因为有：

$\left(\overrightarrow{u}C{\overrightarrow{u}}^t\mathrm{mod}q\right)=\overrightarrow{u}\left(\begin{array}{cc}0& \\ & b\end{array}\right){\overrightarrow{u}}^t=b·u_m^2\left(\mathrm{mod}2\right)$

回想在对偶Regev密码系统中u_m=-1，该过程确实给出了正确的答案。

4.6简单解密

如上所述，根据以下来解密密文：

B＝T^-1·(TCT^tmod q)·(T^t)^-1mod p

该方法的一种扩展是转而使用“简单的”解密公式：

B＝T^-1·(TCmod q)mod p

这种简单的解密对于解密应是足够准确的（例如，足够好），只要密 文不经历乘法。

5.更多的示例性实施例

图1A示出了根据本发明的示例性实施例的示例性加密操作/函数。图 1B示出了根据本发明的示例性实施例的示例性解密操作/函数。图1C示出 了根据本发明的示例性实施例的示例性密钥生成（KeyGen）操作/函数。 图1D示出了根据本发明的示例性实施例的示例性密文加法操作/函数（例 如，用于i个密文，用于n^c个密文）。图1E示出了根据本发明的示例性 实施例的示例性密文乘法操作/函数（例如，用于两个密文C₁和C₂）。图 1F示出了根据本发明的示例性实施例的示例性“简单解密”操作/函数。

图2示出了系统200的框图，在该系统中可实施某些示例性实施例。 在某些示例性实施例中，可根据系统200共同地或单独地实施图1中示出 的各个框。系统200可包括至少一个电路202，其可在一些实施例中包括 至少一个处理器204。系统200也可包括至少一个存储器206（例如，易失 性存储装置），和/或至少一个存储设备208。存储设备208可包括作为非 限制性例子的非易失性存储装置（例如，EEPROM、ROM、PROM、RAM、 DRAM、SRAM、闪存、固件、可编程逻辑等）、磁盘驱动器、光盘驱动 器和/或磁带驱动器。存储设备208可包括作为非限制性例子的内部存储装 置、附加的存储装置和/或网络可访问的存储装置。系统200可包括至少一 个程序逻辑210，其包括可被加载到存储器206并被处理器204和/或电路 202执行的代码212（例如程序代码）。在某些示例性实施例中，包括代码 212的程序逻辑210可被存储在存储设备208中。在其他某些示例性实施 例中，程序逻辑210可在电路202中实现。因此，尽管图2示出了独立于 其他元件的程序逻辑210，程序逻辑210可在存储器206和/或电路202中 实现。

系统200可包括至少一个通信组件214，其使能与至少一个其他系统、 设备和/或装置的通信。通信组件214可包括一个被配置为发送和接收信息 的收发器、被配置为发送信息的发射器和/或被配置为接收信息的接收器。 作为非限制性例子，通信组件214可包括调制解调器或网卡。图2中的系 统200可在诸如作为非限制性例子的桌上型计算机、便携式计算机或服务 器的计算机或计算机系统中实现。图2示出的系统200的组件可使用作为 非限制性例子的一条或多条内部总线、连接、电线和/或（印刷）电路板而 被连接或耦合到一起。

需要注意，根据本发明的示例性实施例，电路202、处理器204、存 储器206、存储设备208、程序逻辑210和/或通信组件214中的一个或多 个可存储这里讨论的各个项目（例如，矩阵、变量、等式、公式、运算、 运算逻辑、逻辑）中的一个或多个。作为非限制性例子，以上定义的一个 或多个组件可接收并/或存储信息B（例如，将被加密，由解密生成）以及 /或密文C（例如，将被解密，由加密生成）。作为进一步的非限制性例子， 以上识别的一个或多个组件可接收和/或存储这里描述的加密函数和/或解 密函数。

以下是关于本发明的各种非限制性的示例性实施例的进一步讨论。为 清楚起见，以下讨论的示例性实施例被分别编号。编号不应被理解为完全 地将各种示例性实施例分离，因为一个或多个示例性实施例的方面可结合 一个或多个其他方面或示例性实施例来实施。

（1）在一个示例性实施例中，如图3所示，一种计算机可读存储介 质有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接 收信息B，该信息B将根据包含加密函数的加密方案被加密为密文C(301)； 以及根据该加密方案的加密函数来加密信息B以获取密文C(302)，其中， 所述加密方案使用对应于至少一个私钥T的至少一个公钥A，其中信息B、 密文C、至少一个公钥A和至少一个私钥T是矩阵，其中，所述加密函数 接收至少一个公钥A和信息B作为输入，并将密文C输出为C← AS+pX+B(mod q)，其中S是随机矩阵，其中X是误差矩阵，其中p是整 数，其中q是奇素数。

如上所述的计算机可读存储介质，其中， 且$X\stackrel{\$}{\leftarrow }{\bar{\Psi }}_{\beta }{\left(q\right)}^{m\times m},$其中，n 表示安全参数且m,q＝poly(n)，其中，是误差分布，其中，β是 由β＝1/poly(n)给出的高斯误差参数。如以上任一个所述的计算机可 读存储介质，其中，所述加密方案是同态的，并支持计算双线性 型（例如，多项式数量的加法和一次乘法）。如以上任一个所述的 计算机可读存储介质，其中p=2，且信息B包括二进制值的矩阵。 如上任一个所述的计算机可读存储介质，其中，c＝c(n)＞0， 且

$\beta =\frac{1}{27p{n}^{1+(3c/2)}\log n\log q\sqrt{\mathrm{qm}}}.$如以上任一个所述的计算机可读 存储介质，其中，所述加密方案支持矩阵环上的任何阶中的 n^c次加法和一次乘法。

如以上任一个所述的计算机可读存储介质，所述操作还包括：输出密 文C。如以上任一个所述的计算机可读存储介质，其中p是包含信息B的 空间的阶。如以上任一个所述的计算机可读存储介质，其中，p是空间的阶且如以上任一个所述的计算机可读介质，其中，所述加密 方案还使能公式私密安全计算，从而私钥的持有者被配置为解密密文，而 不会获取关于解密函数的公式的更多信息。如以上任一个所述的计算机可 读存储介质，其中q＞p。如以上任一个所述的计算机可读存储介质，其中， 所述加密方案包括一种同态加密方案，其用于对数乘法深度的电路，其具 有任意数量的加法，并且其中同态加密方案的安全性基于带误差学习问题 的难度。如以上任一个所述的计算机可读存储介质，其中，T、X和B（的 条目）是小的，从而T·(2X+B)中的条目小于q。如以上任一个所述的计算 机可读存储介质，其中，密文C的大小大约（例如基本上）是明文B的三 倍大小。

如以上任一个所述的计算机可读存储介质，其中，所述加密方案还包 括密钥生成函数，其中，该密钥生成函数接收1ⁿ、q和m作为输入，并输 出所述至少一个公钥A和至少一个私钥T。如以上任一个所述的计算机可 读存储介质，其中，所述密钥生成函数通过运行陷门抽样算法来操作，该 函数针对输入1ⁿ、正整数q≥2以及poly(n)限界正整数m≥8nlogq，输出 矩阵和如以上任一个所述的计算机可读存储介质，其 中，A在统计上接近于在上均匀，T的行构成格 的基，且T的行的欧几里得范数由 O(nlogq)限界。如以上任一个所述的计算机可读存储介质，其中， T·A＝0(mod q)，T是可逆的且T的条目是小的。

如以上任一个所述的计算机可读存储介质，其中，所述加密方案还包 括解密函数，其中，该解密函数接收至少一个私钥T和密文C作为输入， 并根据B＝T^-1·(TCT^tmod q)·(T^t)^-1mod p来输出信息B。如以上任一 个所述的计算机可读存储介质，其中，

如以上任一个所述的计算机可读存储介质，还包括这里描述的本发明 的示例性实施例的一个或多个额外的方面。

(2)在本发明的另一示例性实施例中，一种装置包括：至少一个存储 介质，被配置为存储信息B，该信息B将根据包含加密函数的加密方案 被加密为密文C；以及至少一个处理器，被配置为根据该加密方案的加密 函数来加密信息B以获取密文C，其中，所述加密方案使用对应于至少一 个私钥T的至少一个公钥A，其中信息B、密文C、至少一个公钥A和至 少一个私钥T是矩阵，其中，所述加密函数接收至少一个公钥A和信息B 作为输入，并将密文C输出为C←AS+pX+B(mod q)，其中S是随机矩阵， 其中X是误差矩阵，其中p是整数，其中q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

(3)在本发明的又一示例性实施例中，如图3所示，一种方法，包括： 由至少一个处理器来接收信息B，该信息B将根据包含加密函数的加密方 案被加密为密文C(301)；以及由该至少一个处理器，根据该加密方案的加 密函数来加密信息B以获取密文C(302)，其中，所述加密方案使用对应于 至少一个私钥T的至少一个公钥A，其中信息B、密文C、至少一个公钥 A和至少一个私钥T是矩阵，其中，所述加密函数接收至少一个公钥A和 信息B作为输入，并将密文C输出为C←AS+pX+B(mod q)，其中S是随 机矩阵，其中X是误差矩阵，其中p是整数，其中q是奇素数。

如以上任一个所述的方法，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

(4)在本发明的又一示例性实施例中，一种装置包括：用于存储信息 B的装置，该信息B将根据包含加密函数的加密方案被加密为密文C；以 及用于根据该加密方案的加密函数来加密信息B以获取密文C的装置，其 中，所述加密方案使用对应于至少一个私钥T的至少一个公钥A，其中信 息B、密文C、至少一个公钥A和至少一个私钥T是矩阵，其中，所述加 密函数接收至少一个公钥A和信息B作为输入，并将密文C输出为C← AS+pX+B(mod q)，其中S是随机矩阵，其中X是误差矩阵，其中p是整 数，其中q是奇素数。

如以上所述的装置，其中，所述用于存储的装置包含至少一个存储介 质、存储器或存储器介质，且其中，所述用于加密的装置包含至少一个处 理器、至少一个电路或至少一个集成电路。如以上任一个所述的装置，还 包括这里描述的本发明的示例性实施例的一个或多个额外的方面。

(5)在本发明的又一示例性实施例中，一种装置包括：存储电路，其 被配置为存储信息B，该信息B将根据包含加密函数的加密方案被加密 文为密文C；以及加密电路，其被配置为根据该加密方案的加密函数来加 密信息B以获取密文C，其中，所述加密方案使用对应于至少一个私钥T 的至少一个公钥A，其中信息B、密文C、至少一个公钥A和至少一个私 钥T是矩阵，其中，所述加密函数接收至少一个公钥A和信息B作为输入， 并将密文C输出为C←AS+pX+B(mod q)，其中S是随机矩阵，其中X是 误差矩阵，其中p是整数，其中q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

(6)在本发明的另一示例性实施例中，如图4所示，一种计算机可读 存储介质，其有形地体现可由机器执行以执行操作的指令程序，所述操作 包括：接收密文C，该密文C将根据包含解密函数的加密方案被解密为信 息B（401）；以及根据该加密方案的解密函数来解密密文C以获取信息B （402），其中，所述加密方案使用至少一个私钥T，其中信息B、密文C 和至少一个私钥T是矩阵，其中，所述解密函数接收至少一个私钥T和密 文C作为输入，并根据B=T^-1·(TCT^t mod q)·(T^t)^-1mod p来输出信息B， 其中p是整数，其中q是奇素数。

如以上所述的计算机可读存储介质，所述操作还包括：输出信息B。 如以上任一个所述的计算机可读存储介质，其中所述至少一个私钥T对应 于至少一个公钥A。如以上任一个所述的计算机可读存储介质，其中所述 至少一个私钥T是对称密钥。如以上任一个所述的计算机可读存储介质， 还包括这里描述的本发明的示例性实施例的一个或多个额外的方面。

（7）在本发明的另一示例性实施例中，一种装置包括：至少一个存储 介质，其被配置为存储密文C，该密文C将根据包含解密函数的加密方案 被解密为信息B；以及至少一个处理器，其被配置为根据加密方案的解密 函数来解密密文C以获取信息B，其中加密方案使用至少一个私钥T，其 中信息B、密文C以及至少一个私钥T是矩阵，其中解密函数接收至少一 个私钥T和密文C作为输入，并根据B=T^-1·(TCT^t mod q)·(T^t)^-1modp 输出信息B，其中p是整数，其中q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（8）在本发明的又一示例性实施例中，且如图4所示，一种方法包括： 接收密文C，该密文C将根据包含解密函数的加密方案被解密为信息B （401）；以及根据加密方案的解密函数来解密密文C以获取信息B（402）， 其中，所述加密方案使用至少一个私钥T，其中所述信息B、密文C和至 少一个私钥T是矩阵，其中解密函数接收至少一个私钥T和密文C作为输 入，并根据B=T^-1·(TCT^t mod q)·(T^t)^-1modp输出信息B，其中p是整 数，q是奇素数。

如以上任一个所述的方法，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（9）在本发明的另一示例性实施例中，一种装置包括：用于存储密文 C的装置，该密文C将根据包含解密函数的加密方案被解密为信息B；以 及用于根据加密方案的解密函数来解密密文C以获取信息B的装置，其中， 所述加密方案使用至少一个私钥T，其中，所述信息B、密文C和至少一 个私钥T是矩阵，其中解密函数接收至少一个私钥T和密文C作为输入， 并根据B=T^-1·(TCT^tmod q)·(T^t)^-1modp输出信息B，其中p是整数，q 是奇素数。

如以上所述的装置，其中所述用于存储的装置包括至少一个存储介质、 存储器或存储器介质，且其中所述用于解密的装置包括至少一个处理器、 至少一个电路或至少一个集成电路。如以上任一个所述的装置，还包括这 里描述的本发明的示例性实施例的一个或多个额外的方面。

（10）在本发明的另一示例性实施例中，一种装置包括：存储电路， 其被配置为存储密文C，该密文C将根据包括解密函数的加密方案被解密 为信息B；以及解密电路，其被配置为根据加密方案的解密函数来解密密 文C以获取信息B，其中，所述加密方案使用至少一个私钥T，其中，所 述信息B、密文C和至少一个私钥T是矩阵，其中，解密函数接收至少一 个私钥T和密文C作为输入，并根据B=T^-1·(TCT^tmod q)·(T^t)^-1modp 输出信息B，其中p是整数，q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（11）在本发明的另一示例性实施例中，一种计算机可读存储介质， 其有形地体现了可由执行操作的机器来执行的指令程序，所述操作包括： 接收信息B，该信息B将根据包含加密函数和解密函数的加密方案被加密 为密文C；以及根据所述加密方案的加密函数来加密信息B以获得密文C， 其中加密方案使用至少一个公钥A和对应于该至少一个公钥A的至少一个 私钥T，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是 矩阵，其中，且其中n表示安 全参数，且m，q＝poly(n)，其中q是奇素数，其中p是整数，其中q>p， 其中加密函数接收A和B作为输入，且将密文C输出为 C←AS+pX+B(modq)，其中S是随机矩阵，且其中X是 误差矩阵，且其中是误差分布，其中β是由β=1/poly(n) 给出的高斯误差参数，其中解密函数接收T和C作为输入，并根据 B＝T^-1·(TCT^t modq)·(T^t)^-1modp输出信息B，其中加密方案是同态的，并支 持计算双线性型（例如，多项式数量的加法和一次乘法）。

如以上任一个所述的计算机可读存储介质，还包括这里描述的本发明 的示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于以上描述的计算机可读存储介质。

（12）在本发明的另一示例性实施例中，一种计算机可读存储介质， 其有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接 收至少一个第一信息B₁，该第一信息B₁将根据包含加密函数和解密函数 的加密方案被加密为第一密文C₁，以及第二密文C₂，该第二密文C₂将根 据所述加密方案被解密为第二信息B₂；以及根据所述加密方案中的加密函 数来加密第一信息B₁以获取第一密文C₁和根据所述加密方案中的解密函 数来解密第二密文信息C₂以获取第二信息B₂中的至少一个，其中，所述 加密方案使用至少一个公钥A和对应于该至少一个公钥A的至少一个私钥 T，其中信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵，其 中加密函数接收至少一个公钥A和信息B作为输入，并将密文C输出为 C←AS+pX+B(mod q)，其中S是随机矩阵，其中X是误差矩阵，其中p 是整数，其中q是奇素数，其中，解密函数接收至少一个私钥T和密文C 作为输入，并根据B＝T^-1·(TCT^tmodq)·(T^t)^-1mod p输出信息B。

如以上任一个所述的计算机可读存储介质，还包括这里描述的本发明 的示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于上述计算机可读存储介质。

（13）在本发明的另一示例性实施例中，如图5所示，一种计算机可 读存储介质，其有形地体现了可由机器以执行操作的指令程序，所述操作 包括：接收多个信息B_i，该多个信息B_i将根据包含加密函数和解密函数的 加密方案被加密为多个密文C_i（501）；根据所述加密方案的加密函数来 加密多个信息B_i中的每一个以获取密文C_i中的每一个（502）；通过对密 文C_i应用二次多项式来计算结果密文C_poly，其 中在索引i和j的一个子集上求和（503）；以及根据所述加密方案的解密 函数来解密结果密文C_poly以获取结果信息B_poly（504），其中，所述加密 方案使用对应于至少一个私钥T的至少一个公钥A，其中所述多个信息B_i、 密文C_i、至少一个公钥A和至少一个私钥T是矩阵，其中加密函数接收至 少一个公钥A和信息B_i作为输入，并将密文C_i输出为 C_i←AS+pX+B_i(mod q):，其中S是随机矩阵，其中X是误差矩阵，其中 p是整数，其中q是奇素数，其中i是整数，其中j是整数，其中解密函数 接收至少一个私钥T和结果密文C_poly作为输入，并根据索引i和j的子集 上的$B_{\mathrm{poly}}=T^{-1}·\left({\mathrm{TC}}_{\mathrm{poly}}{T}^t\mathrm{mod}q\right)·{\left(T^t\right)}^{-1}\mathrm{mod}p={\Sigma }_i{B}_i\times B_j^t\mathrm{mod}p$输出 结果信息B_poly。

如以上任一个所述的计算机存储介质，还包括这里描述的示例性实施 例的一个或多个额外的方面。一种方法、装置或计算机程序，对应于上述 计算机可读存储介质。

（14）在本发明的另一示例性实施例中，一种计算机可读存储介质， 其有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接 收密文C，该密文C将根据包含解密函数的加密方案被解密为信息B；以 及根据所述加密方案的解密函数来解密密文C以获取信息B，其中所述加 密方案使用至少一个私钥T，其中所述信息B、密文C和至少一个私钥T 是矩阵，其中解密函数接收至少一个私钥T和密文C作为输入，并根据 B＝T^-1·(TC modq)mod p输出信息B，其中p是整数，其中q是奇素数。

如以上任一个所述的计算机可读存储介质，还包括这里描述的本发明 的示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于上述计算机可读存储介质。

（15）在本发明的另一个示例性实施例中，一种装置包括：至少一个 存储介质，其被配置为存储密文C，该密文C将根据包含解密函数的加密 方案被解密为信息B；以及至少一个处理器，被配置为根据所述加密方案 的解密函数来解密密文C以获取信息B，其中所述加密方案使用至少一个 私钥T，其中所述信息B、所述密文C和至少一个私钥T是矩阵，其中解 密函数接收至少一个私钥T和密文C作为输入，并根据 B＝T^-1·(TC mod q)mod p输出信息B，其中p是整数，q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（16）在本发明的又一个示例性实施例中，且如图6所示，一种方法 包括：接收密文C，该密文C将根据包含解密函数的加密方案被解密为信 息B（601）；以及根据所述加密方案的解密函数来解密密文C以获取信 息B（602），其中所述加密方案使用至少一个私钥T，其中所述信息B、 密文C和至少一个私钥T是矩阵，其中所述解密函数接收至少一个私钥T 和密文C作为输入，并根据B＝T^-1·(TC mod q)mod p输出信息B，其 中p是整数，q是奇素数。

如以上任一个所述的方法，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（17）在本发明的另一示例性实施例中，一种装置包括：用于存储密 文C的装置，该密文C将根据包含解密函数的加密方案被解密为信息B； 以及用于根据所述加密方案的解密函数来解密密文C以获取信息B的装 置，其中，所述加密方案使用至少一个私钥T，其中所述信息B、密文C 和至少一个私钥T是矩阵，其中所述解密函数接收至少一个私钥T和密文 C作为输入，并根据B＝T^-1·(TC mod q)mod p输出信息B，其中p是整 数，其中q是奇素数。

如以上所述的装置，其中所述用于存储的装置包括至少一个存储介质、 存储器或存储器介质，且其中所述用于解密的装置包括至少一个处理器、 至少一个电路或至少一个集成电路。如以上任一个所述的装置，还包括这 里描述的本发明的示例性实施例中的一个或多个额外的方面。

（18）在本发明的另一示例性实施例中，一种装置包括：存储电路， 其被配置为存储密文C，该密文C将根据包含解密函数的加密方案被解密 为信息B；以及解密电路，其被配置为根据所述加密方案的解密函数来解 密密文C以获取信息B，其中，所述加密方案使用至少一个私钥T，其中 所述信息B、密文C和至少一个私钥T是矩阵，其中解密函数接收至少一 个私钥T和密文C作为输入，并根据B＝T^-1·(TC mod q)mod p输出信 息B，其中p是整数，其中q是奇素数。

如以上任一个所述的装置，还包括这里描述的本发明的示例性实施例 的一个或多个额外的方面。

（19）在本发明的又一示例性实施例中，一种计算机可读存储介质， 其有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接 收信息B，该信息B将根据包含加密函数和解密函数的加密方案被加密为 密文C；以及根据所述加密方案的加密函数来加密信息B以获得密文C， 其中，所述加密方案使用至少一个公钥A和对应于该至少一个公钥A的至 少一个私钥T，其中所述信息B、密文C、至少一个公钥A和至少一个私 钥T是矩阵，其中，且且其中 n表示安全参数，且m,q＝poly(n)，其中q是奇素数，其中p是是整数，且 q>p，其中加密函数接收A和B作为输入，并将密文C输出为 C←AS+pX+B(mod q)，其中S是随机矩阵，且其中X是误 差矩阵，且其中是误差分布，其中β是由β=1/poly(n) 给出的高斯误差参数，其中，解密函数接收T和C作为输入，并根据 B＝T^-1·(TC mod q)mod p输出信息B，其中加密方案是同态的且支持多 项式数量的加法。

以上任一个所述的计算机可读存储介质，还包括这里描述的本发明的 示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于上述计算机可读存储介质。

（20）在本发明的另一示例性实施例中，一种计算机可读存储介质， 其有形地体现了可由机器执行以执行操作的指令程序，所述操作包括：接 收至少一个第一信息B₁，该第一信息B₁将根据包含加密函数和解密函数 的加密方案被加密为第一密文C₁，以及第二密文C₂，该第二密文C₂将根 据所述加密方案被解密为第二信息B₂；以及根据所述加密方案的加密函数 来加密所述第一信息B₁以获取第一密文C₁，并根据所述加密方案的解密 函数来解密第二密文C₂以获取第二信息B₂中的至少一个，其中，所述加 密方案使用至少一个公钥A和对应于该至少一个公钥A的至少一个私钥 T，其中所述信息B、密文C、至少一个公钥A和至少一个私钥T是矩阵， 其中，加密函数接收至少一个公钥A和信息B作为输入，并将密文C输 出为C←AS+pX+B(mod q)，其中S是随机矩阵，其中X是误差矩阵，其 中p是整数，其中q是奇素数，其中，解密函数接收至少一个私钥T和密 文C作为输入，并根据B＝T^-1·(TC mod q)mod p输出信息B。

以上任一个所述的计算机可读存储介质，还包括这里描述的本发明的 示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于上述计算机可读存储介质。

（21）在本发明的另一示例性实施例中，且如图7所示，一种计算机 可读存储介质，其有形地体现了可由机器执行以执行操作的指令程序，所 述操作包括：接收多个信息B_i，该多个信息B_i将根据包含加密函数和解密 函数的加密方案被加密为多个密文C_i（701）；根据所述加密方案的加密 函数来加密多个信息B_i中的每一个以获取密文C_i中的每一个（702）；通 过对密文C_i进行求和，C_sum←∑_tC_tmod q，来计算结果密文C_sum，其中在 索引i的子集上求和（703）；以及根据加密方案的解密函数来解密结果密 文C_sum以获取结果信息B_sum（704），其中，所述加密方案使用对应于至 少一个私钥T的至少一个公钥A，其中所述多个信息B_i、密文C_i、至少一 个公钥A和至少一个私钥T是矩阵，其中加密函数接收至少一个公钥A 和信息B_i作为输入并将密文C_i输出为C_i←AS+pX+B_i(mod q)，其中S是 随机矩阵，其中X是误差矩阵，其中p是整数，其中q是奇素数，其中i 是整数，其中j是整数，其中，解密函数接收至少一个私钥T和结果密文 C_sum作为输入，并根据索引i的子集上的 B_sum＝T^-1·(TC_sum mod q)mod p＝∑_iB_imod p输出结果信息B_sum。

以上任一个所述的计算机可读存储介质，还包括这里描述的本发明的 示例性实施例的一个或多个额外的方面。一种方法、装置或计算机程序， 对应于上述计算机可读存储介质。

这里描述的本发明的示例性实施例可以结合程序存储装置（例如，至 少一个存储器、至少一个计算机可读存储介质）来实现，该程序存储装置 可被（例如，机器、计算机、处理器）读取，并有形地体现（例如，存储） 可由机器（或计算机或处理器）执行以执行操作的指令程序（例如，程序、 计算机程序、程序代码、程序指令）。所述操作包括使用（例如实现）本 发明的示例性实施例的步骤或方法的步骤。

图3-7示出的框可被进一步认为对应于由一个或多个组件、电路、芯 片、装置、处理器、计算机程序和/或功能块执行的一个或多个功能和/或操 作。以上任何和/或所有方面都可以任何适用的解决方案或安排来实施，所 述解决方案或安排实现了根据这里描述的本发明的示例性实施例的操作。

此外，图3-7中示出的框的布置可被考虑为仅是示例性的和非限制性 的。将理解，图3-7示出的框可对应于可以任何顺序（例如，任何合适的、 适用的和/或可行的顺序）和/或同时（例如，合适地，适用地和/或可行地） 执行的一个或多个功能和/或操作，以执行本发明的一个或多个示例性实施 例。此外，可结合图3-7示出的功能、操作和/或步骤来利用一个或多个额 外的功能、操作和/或步骤，以执行本发明的一个或多个进一步的示例性实 施例。

即，图3-7示出的本发明的示例性实施例可结合任何组合（例如，任 何合适的、适用的和/或可行的组合）中的一个或多个进一步的方面来利用、 实施或实现，且不限于图3-7示出的步骤、框、操作和/或功能。

图3-7中的流程图和框图示出了根据本发明的各种示例性实施例的系 统、方法和计算机程序产品的各种示例性实施例的结构、功能和操作。在 这方面，流程图或框图中的每个框可代表代码的模块、段或部分，其包括 用于实施指定的逻辑功能的一个或多个可执行指令。也将注意到，在一些 可替换实施中，在框中标注的功能可不按照图中的顺序来发生。例如，连 续示出的两个框实际上可以基本上同时被执行，或框有时候可以相反的顺 序被执行，这取决于所涉及的功能。还应注意，作为非限制性的例子，框 图和/或流程图说明中的每个框，以及框图和/或流程图说明中框的组合可由 执行指定的功能或行为的基于硬件的专用系统或专用硬件和计算机指令的 组合实施。

再进一步地，用于此处描述的参数、操作和功能的各种名称在任何方 面都不是限制性的，因为这些参数、操作和功能可用任何合适的名称来标 识。

这里描述的任何和所有的装置加功能元件或步骤加元件元件的对应结 构、材料、操作和等价物以及旨在包括用于与如具体声明的那样的其他所 声明的元件结合执行所述功能的任何结构、材料或操作。已出于说明和描 述的目的展示了本发明的示例性实施例的描述，但所述描述并非旨在是详 尽的或将本发明限定于公开的形式。对于本领域技术人员来说，许多修改 和改变是明显的，而不脱离本发明的范围和精神。选择和描述了示例性实 施例以便最佳地解释本发明的示例性实施例的原理和实际应用，并使得本 领域普通技术人员能针对具有各种修改的适于所构想的特定使用的各种示 例性实施例理解本发明。

本领域技术人员将理解，作为非限制性的例子，本发明的示例性实施 例的方面可被实施为系统、方法或计算机程序产品。因此，作为非限制性 的例子，本发明的示例性实施例的方面将采取完全的硬件实施例、完全的 软件实施例（包括固件、驻留件、微代码等）或组合了在此通常被称为“电 路”、“模块”或“系统”的软件和硬件方面的实施例。而且，本发明的 示例性实施例的方面可采取体现在一个或多个计算机可读介质中的计算机 程序产品的形式，所述计算机可读介质在其上实现有计算机可读程序代码。

可使用一个或多个计算机可读介质的任意组合。所述计算机可读介质 可以是计算机可读信号介质或计算机可读存储介质。作为非限制性的例子， 计算机可读的存储介质可包括以下各项中的一个或多个：电子、磁、光、 电磁、红外线或半导体的系统、装置或器件，或前述任何合适的组合。计 算机可读存储介质的更具体的非限制性例子包括：有一个或多个导线的电 连接、便携式计算机磁盘、硬盘、随机存取存储器（RAM）、只读存储器 （ROM）、可擦除可编程只读存储器（EPROM或闪存）、光纤、便携式 紧凑盘只读存储器（CD-ROM）、光存储器件、磁存储器件，或前述的任 何合适的组合。在本文件的语境中，计算机可读存储介质可以是任何被配 置为/可操作以含有或存储程序的有形介质，该程序可供指令执行系统、装 置或器件使用或与其结合使用。

计算机可读的信号介质可包括例如在基带中或者作为载波一部分传播 的、在其中实现计算机可读程序码的数据信号。这样传播的信号可采取多 种形式中的任一个，包括但不限于电磁、光或其任意合适的组合。计算机 可读的信号介质可以是任何除了计算机可读存储介质外的计算机可读介 质，该计算机可读介质可发送、传播或传输供指令执行系统、装置或器件 使用或与其结合使用的程序。

在计算机可读介质上实现的程序码可以用任何适当的介质传输，包括 但不限于：无线、电线、光缆、RF等，或上述的任意合适的组合。

用于执行本发明的各方面的操作的计算机程序码，可以以一种或多种 程序设计语言的任何组合来编写，作为非限制性例子，所述程序设计语言 包括面向对象的程序设计语言—诸如Java、Smalltalk、C++之类，还包括 常规的过程式程序设计语言—诸如“C”程序设计语言或类似的程序设计 语言。作为非限制性例子，程序代码可以完全地在用户的计算上执行、部 分地在用户的计算机上执行、作为一个独立的软件包执行、部分在用户的 计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执 行。在后一种情形中，作为非限制性例子，远程计算机可以通过任何种类 的网络—包括局域网(LAN)或广域网(WAN)—连接到用户的计算机，或者， 可以（例如，利用因特网服务提供商来通过因特网）连接到外部计算机。

这里参考根据本发明实施例的方法、装置（系统）和计算机程序产品 的流程图描述和/或框图来说明本发明的各个方面。将理解，流程图和/或框 图描述的每个方框，以及流程图和/或框图描述中的方框组合，可由计算机 程序指令来实施。作为非限定性的例子，这些计算机程序指令可以提供给 通用计算机、专用计算机或其他可编程数据处理装置的处理器，从而生产 出一种机器，使得通过计算机或其他可编程数据处理装置执行的这些指令， 产生实现流程图和/或框图中的方框中规定的功能/操作的装置。

也可以把这些计算机程序指令存储在能指导计算机或其他可编程数据 处理装置以特定方式工作的计算机可读介质中，这样，存储在计算机可读 介质中的指令产生一个包括实现流程图和/或框图中的方框中规定的功能/ 操作的指令的制造品。

也可以把计算机程序指令加载到计算机、其他可编程数据处理装置或 其他装置上，使得在计算机、其他可编程数据处理装置或其他装置上执行 一系列操作步骤，以产生计算机实现的过程，从而在计算机、其他可编程 装置或其他装置上执行的指令能提供实现流程图和/或框图中的方框中规 定的功能/操作的过程（例如，本发明的示例性实施例）。

术语“连接”、“耦合”或其变体的任何使用应被理解为表示标识的 元件之间任何这样的连接或耦合，不管是直接还是间接的。作为非限制性 的例子，可在“耦合的”元件之间出现一个或多个中间元件。根据所描述 的示例性实施例，作为非限制性的例子，标识的元件之间的连接或耦合可 以是物理的、电的、磁的、逻辑的或其任意合适的组合。作为非限制性的 例子，所述连接或耦合可包括印刷电路连接、有线、线缆、介质或其任意 合适的组合中的一个或多个。

通常，本发明的各种示例性实施例可在不同的介质中实施，所述介质 诸如软件、硬件、逻辑、专用电路或其任意组合。作为非限制性的例子， 一些方面可被实施在可在计算装置上运行的软件中，而其他方面可被实施 在硬件中。

通过示例性和非限制性例子的方式，以上描述已提供了发明人用于实 现本发明而在当前所考虑的最佳方法和装置的完整和有教益的描述。但是， 当结合附图和所附权利要求书来阅读前述描述时，各种修改和适应对于本 领域技术人员来说将变得明显。但是，所有这样和类似的修改将仍然落在 本发明的示例性实施例的教导的范围内。

而且，本发明的优选实施例的一些特征可被使用来产生良好效果，而 不需要其他特征的相应使用。这样，前述描述应被理解为仅是本发明的原 理的描述，而不是对其的限制。

6.参考文献

[1]C.Aguilar Melchor,G.Castagnos,和P.Gaborit.Lattice-based  homomorphic encryption of vector spaces.来自IEEE International  SymposiumonInformation Theory,ISIT′2008,页1858-1862,2008.

[2]C.Aguilar Melchor,P.Gaborit,和H.Javier.Additive Homomorphic  Encryption with t-Operand Multiplications.Technical Report 2008/378, IACR ePrint archive,2008.http://eprint.iacr.org/2008/378/.

[3]M.Ajtai.Generating hard instances of the short basis problem.来自 ICALP,页1{9,1999.

[4]J.Alwen和C.Peikert.Generating shorter bases for hard random  lattices.来自STACS,页75-86,2009.

[5]D.Boneh,E.-J.Goh,和K.Nissim.Evaluating 2-DNF formulas on  ciphertexts.页325-341,2005.

[6]Y.Dodis,S.Goldwasser,Y.T.Kalai,C.Peikert,和V.Vaikuntanathan. Public-key encryption schemes with auxiliary inputs.来自TCC，页 361-381,2010.

[7]W.Feller.An Introduction to Probability Theory and Its Applications，卷 1.Wiley,1968.

[8]C.Gentry.A fully homomorphic encryption scheme.博士论文,斯坦福 大学,2009.http://crypto.stanford.edu/craig.

[9]C.Gentry.Fully homomorphic encryption using ideal lattices.来自 STOC′09,页169-178.ACM,2009.

[10]C.Gentry,C.Peikert,和V.Vaikuntanathan.Trapdoors for hard  latticesand new cryptographic constructions.来自STOC，页197-206, 2008.

[11]A.Kawachi,K.Tanaka,和K.Xagawa.Multi-bit Cryptosystems  Based on Lattice Problems.来自Public Key Cryptography(PKC′07), Lecture Notes in Computer Science的卷4450,页315-329.Springer,2007.

[12]Y.Lindell和B.Pinkas.A proof of security of yao′s protocol for  two-party computation.J.Cryptology,22(2),2009.

[13]C.Peikert.Public-key cryptosystems from the worst-case shortest  vector problem.来自STOC′09,页333-342.ACM,2009.

[14]O.Regev.On lattices,learning with errors,random linear codes,and  cryptography.J.ACM，56(6),2009.STOC′05中的初步版本.

[15]T.Sander,A.Young,和M.Yung.Non-interactive CryptoComputing  for NCI.来自40^th Annual Symposium on Foundations of Computer  Science,页554-567.IEEE,1999.

[16]A.C.Yao.Protocols for secure computations(扩展摘要).来自23rd Annual Symposium on Foundations of Computer Science-FOCS′82,页 160-164.IEEE,1982.