用于数据库查询的同态加密

1.一种计算机实现的方法，其用于对数据库执行查询，其中，所述查询的数值对象被表示为使用加法同态加密确定的密文，并且所述密文包括多个部分，所述多个部分包括至少第一子密文和第二子密文，所述方法包括：
将所述第一子密文和所述第二子密文存储在所述数据库中，其中，所述第一子密文和所述第二子密文是所述密文的部分分量，以使得对所述密文的解密需要至少所述第一子密文和所述第二子密文，所述第一子密文和所述第二子密文在所述数据库中在单独的属性中存储，并且所述第一子密文和所述第二子密文中的每个是基于整个数值来确定的，其中，对所述第二子密文进行确定是独立于对所述第一子密文的确定的；
生成查询，所述查询涉及要对存储在所述数据库中的所述第一子密文和所述第二子密文执行的计算；以及
对所述第一子密文和所述第二子密文执行所述计算以确定针对所述查询的加密答案，而不需要解密所述第一子密文和所述第二子密文。
2.根据权利要求1所述的计算机实现的方法，其中所述加法同态加密也是乘法同态的。
3.根据权利要求1所述的计算机实现的方法，其中所述方法还包括以下步骤：
基于包括一组密钥分量的密钥来确定所述密文，其中在该组密钥分量中的密钥分量的数目等于子密文的数目。
4.根据权利要求3所述的计算机实现的方法，其中所述方法还包括：
基于子密文的数目确定该组密钥分量。
5.根据权利要求3所述的计算机实现的方法，其中所述密钥满足以下等式：
其中，
V是所述数值，
n是子密文的数目，
K(n)是所述密钥，
fi是所述密钥的第i个函数，且
Valuei是K(n)和V的第i个函数。
6.根据权利要求3所述的计算机实现的方法，其中确定所述密文包括确定满足以下等式的子密文：
其中，
V是所述数值，
n是子密文的数目，
K(n)是所述密钥，
fi是所述密钥的第i个函数，且
Vi是第i个子密文。
7.根据权利要求3所述的计算机实现的方法，其中确定所述密文包括确定满足以下等式的子密文：
Vi＝Valuei(K(n),V)+Noisei(K(n),R)
其中，
V是所述数值，
n是子密文的数目，
K(n)是所述密钥，
R是一组随机数，
Vi是第i个子密文，
Valuei是K(n)和V的第i个函数，且
Noisei是K(n)和R的第i个函数。
8.根据权利要求1所述的计算机实现的方法，其中所述方法包括以下步骤：
通过以下来确定所述密文：针对每一子密文，将第一结果和第二结果相加，其中所述第一结果是基于与该子密文相关联的密钥和所述数值的函数的值，且所述第二结果是基于与该子密文相关联的所述密钥和一个或多个随机数的函数的值。
9.根据权利要求1所述的计算机实现的方法，其中所述方法包括以下步骤：
确定所述密文，其不包括使用取模或地板算术运算。
10.根据权利要求1所述的计算机实现的方法，其中所述方法还包括如下步骤：
确定一组随机数分量；以及
基于该组随机数分量确定所述密文。
11.根据权利要求10所述的计算机实现的方法，其中确定所述密文基于包括一组密钥分量的密钥，其中该组密钥分量中的密钥分量的数目等于子密文的数目，且确定该组随机数分量包括确定满足如下等式的一组随机数：
其中，
n是子密文的数目，
K(n)是所述密钥，
fi是所述密钥的第i个函数，
R是一组随机数分量；且
Noisei是K(n)和R的第i个函数。
12.根据权利要求11所述的计算机实现的方法，其中所述等式可组合且所述方法还包括：
将所述密钥的多个实例融合以创建新的密钥实例。
13.根据权利要求1所述的计算机实现的方法，其中所述方法还包括：
基于用于对数值进行加密的密钥来解密针对所述查询的加密的答案。
14.根据权利要求1所述的计算机实现的方法，其中所述计算是基于乘法的对所述数据库的查询，所述计算包括：
针对所述查询的每一对数值对象，执行用于该对数值的所述子密文的外积，以确定加密的相乘值。
15.根据权利要求1所述的计算机实现的方法，其中存储所述第一子密文和所述第二子密文是通过创建具有用于存储所述第一子密文的第一属性和用于存储所述第二子密文的第二属性的表来执行的。
16.根据权利要求1所述的计算机实现的方法，其中所述方法包括通过将记录插入到具有所述单独的属性的所述数据库中来存储所述第一子密文和所述第二子密文。
17.一种非暂态计算机可读介质，包括存储在其上的计算机可执行指令，所述指令当被执行时使得所述计算机执行对数据库的查询，其中，所述查询的数值对象被表示为使用加法同态加密确定的密文，并且所述密文包括多个部分，所述多个部分包括至少第一子密文和第二子密文，所述方法包括：
将所述第一子密文和所述第二子密文存储在所述数据库中，其中，所述第一子密文和所述第二子密文是所述密文的部分分量，以使得对所述密文的解密需要至少所述第一子密文和所述第二子密文，所述第一子密文和所述第二子密文在所述数据库中在单独的属性中存储，并且所述第一子密文和所述第二子密文中的每个是基于整个数值来确定的，并且其中，对所述第二子密文进行确定是独立于对所述第一子密文的确定的；
生成查询，所述查询涉及要对存储在所述数据库中的所述第一子密文和所述第二子密文执行的计算；以及
对所述第一子密文和所述第二子密文执行所述计算以确定针对所述查询的加密答案，而不需要解密所述第一子密文和所述第二子密文。
18.一种用于加密要在非暂态数据库中存储的数值的计算机系统，包括：
处理器，用于：
使用加法同态加密确定针对所述数值的密文，其中所述密文包括多个部分，所述多个部分包括至少第一子密文和第二子密文，所述第一子密文和所述第二子密文是所述密文的部分分量，以使得对所述密文的解密需要至少所述第一子密文和所述第二子密文，并且所述第一子密文和所述第二子密文是基于整个数值来确定的，并且对所述第二子密文进行确定是独立于对所述第一子密文的确定的；以及
使所述第一子密文和所述第二子密文在所述数据库中在单独的属性中存储，以使得对所述第一子密文和所述第二子密文的计算确定加密结果而不解密所述第一子密文和所述第二子密文，其中所述加密结果是对所述数值执行的所述计算的结果的密文。
19.一种服务器，包括：
数据库，记录在非暂态计算机可读介质上，其中，所述数据库存储具有两个或更多个属性的记录，其中每一记录包含使用加法同态加密确定的表示数值的密文，并且所述密文包括多个部分，所述多个部分包括至少第一子密文和第二子密文，所述第一子密文和所述第二子密文是所述密文的部分分量，以使得对所述密文的解密需要至少所述第一子密文和所述第二子密文，并且所述第一子密文和所述第二子密文是基于整个数值来确定的，并且对所述第二子密文进行确定是独立于对所述第一子密文的确定的，并且所述第一子密文和所述第二子密文是在单独的属性中存储的，以使得，基于所述第一子密文和所述第二子密文的计算确定加密结果，其中所述加密结果是对所述数值执行的所述计算的结果的密文。
20.一种用于对在数据库中存储的密文进行解密的计算机实现的方法，所述方法包括：
接收或访问使用加法同态加密确定的密文，其中所述密文包括多个部分，所述多个部分包括至少第一子密文和第二子密文，所述第一子密文和所述第二子密文是所述密文的部分分量，以使得对所述密文的解密需要至少所述第一子密文和所述第二子密文，所述第一子密文和所述第二子密文是基于整个数值来确定的并且是在单独的属性中存储的，并且对所述第二子密文进行确定是独立于对所述第一子密文的确定的；以及
基于所述第一子密文和所述第二子密文且使用包括一组密钥分量的加密密钥来解密所述密文，其中密钥分量的数目与密文的数目相同。

用于数据库查询的同态加密\n技术领域\n[0001] 本公开涉及用于数据库查询的同态加密。\n[0002] 本公开包括用于对要存储在数据库中的数值进行加密、对数据库中存储的密文进行解密、对存储密文的数据库执行聚合和乘法查询、在数据库中创建表格以存储密文、以及插入包括密文的记录的计算机实现的方法。\n[0003] 其他方面包括数据库、软件和计算机系统。\n[0004] 本领域的技术人员(除了其他的以外)已经知道通用计算机系统，包括硬件和软件。\n背景技术\n[0005] 在诸如金融应用和医疗电子健康应用之类的许多应用中，数据库是集成的部分。\n数据库可能非常敏感，其包含对企业或个人有价值的数据。对个人、企业和政府而言，偷窃敏感数据越来越受到关注。\n[0006] 通过使用诸如Oracle Database、MySQL、Microsoft SQL Server等之类的数据库管理系统(DBMSs)来管理数据库。数据库可以部署在企业内的服务器上、云中的虚拟服务器上、或云中的DBMS服务上。对于部署的每一种类型，数据偷窃都是关注点。\n[0007] 当在企业的经营场所内的服务器上部署数据库时，服务器物理上在企业的控制之下。如果服务器受到恶意软件或病毒的入侵或感染，则攻击者可能能够通过绕过任何企业访问控制机制，来访问原始数据库数据文件并偷窃数据。在另一方面，由于企业中的数据库管理员能够访问所存储的数据以执行数据库管理任务，因此其有机会(故意地或者意外地)违反数据的隐私和完整性。\n[0008] 数据库系统也可以被企业部署在虚拟服务器上，其运行在像Amazon Elastic Compute Cloud(Amazon EC2)的云上。在该情况下，在数据库底层的虚拟服务器在物理上处于云提供商的控制之下，且企业在虚拟服务器上安装DBMS来管理其数据库。类似于上面的情况，在该情况下，如果云基础设施被攻击者入侵、被恶意软件或病毒感染，则也会发生数据偷窃，且企业数据库管理员可能违反数据库的隐私和完整性。此外，如果云提供商不值得信任，则他们可以偷窃在他们所提供的虚拟服务器中的数据库数据。\n[0009] 当前存在由云提供商提供的DBMS服务，例如Amazon Relational Database \nService(Amazon RDS)和Micros SQL Azure Database。通过使用DBMS服务，企业可以将其数据库放入云上的虚拟DBMS中。在该情况下，企业无需购买并安装其自身的DBMS软件，且可以减少雇佣高技能的数据库管理员(DBA)的成本。云提供商负责数据库系统的管理、升级和性能调优。类似地，如果入侵了数据库服务，则攻击或病毒感染可以偷窃数据。此外，由于数据库直接在云提供商的管理之下，则提供商仅通过使用标准的数据库访问接口就可以容易地偷窃企业数据。\n[0010] 针对数据库的数据偷窃问题的直截了当的方法是对数据库中的数据进行加密。\n即，数据在被存入数据库中时被加密，或整个数据文件被加密，如Microsoft SQL Server \n2008和Oracle 10g Database所允许的。以此方式，可以保护数据库中的数据不受入侵服务器的攻击者和数据库管理员(如果他们不知道加密密钥)的危害。但是，在加密之后，在Microsoft SQL Server 2008和Oracle 10g数据库中不再可以直接查询数据库了，或者在执行查询之前不得不先解密数据。\n发明内容\n[0011] 在第一方面，提供了一种计算机实现的方法，其用于加密要存储在数据库中的数值，该方法包括：\n[0012] 使用加法同态加密确定针对数值的密文，其中密文包括两个或更多个子密文；以及\n[0013] 使每一子密文单独地并在单个记录中存储在数据库中。\n[0014] 一优点是，数字(纯文本)值不被加密为单个密文。任何用于确定数值的密文或纯文本攻击将需要解密使加密方法健壮的多个子密文。此外，在不访问数据库模式的情况下(通过使用适当的不提供信息的名称，这可能会混淆例如数据库的表的属性的本质)，恶意的第三方可能不知道多少子密文或哪个子密文表示哪个纯文本值。\n[0015] 此外，单独存储子密文意味着子密文也与记录中的其他值分开存储。这提供了更大的灵活性，包括对包含记录的特定值执行查询的能力，而无需解密整个记录。\n[0016] 重要的是，另外的优点是加密是加法同态的。这允许在不解密密文的情况下，对数据库中的数值执行聚合查询，例如使用求和和平均操作的查询。\n[0017] 该加法同态加密也可以是乘法同态。\n[0018] 确定密文的步骤可以是基于包括一组密钥分量的密钥的，其中在该组密钥分量中的密钥分量的数目等于子密文的数目。\n[0019] 每一密钥分量可以包括一个或多个子分量，且密钥或每一密钥子分量可以是加密密钥。\n[0020] 一优点是，使用多个密钥分量使加密方法对密文或纯文本攻击而言是健壮的。更多的子密文意味着使用更多的密钥，且继而加密更安全。另一优点是，可以在不增加每一子密文的存储大小的情况下增加加密的健壮性。\n[0021] 每一密钥分量可以基于包含密文的子密文的数目。\n[0022] 该方法还可以包括：\n[0023] 基于子密文的数目确定该组密钥分量。\n[0024] 一优点是，该方法适合用于包括大量子密文的两个或更多的子密文。\n[0025] 密钥可以满足以下等式：\n[0026]\n[0027] 其中，\n[0028] V是该值，\n[0029] n是子密文的数目，\n[0030] K(n)是密钥，\n[0031] fi是密钥的第i个函数，且\n[0032] Valuei是K(n)和V的第i个函数。\n[0033] fi和Valuei可以相对于n具有线性的时间复杂度。\n[0034] 确定密文可以包括确定用于满足以下等式的子密文：\n[0035]\n[0036] 其中，\n[0037] V是该值，\n[0038] n是子密文的数目，\n[0039] K(n)是密钥，\n[0040] fi是密钥的第i个函数，且\n[0041] Vi是第i个子密文。\n[0042] fi可以相对于n具有线性的时间复杂度。\n[0043] 一优点是，本实施例不需要知道所有可能的输入的最大和，且适合用于现有数据库中而无需修改，且其中无需限制聚合值。还有一优点是，在加密时无需知道要添加到数据库的记录的数目，且可以被添加到数据库的密文记录的数目可以任意大。不使用减小加密方法的健壮性和对密文执行的查询的准确性的取模(modulo)或地板算术(floor \narithmetic)操作来获得该优点。\n[0044] 确定密文可以包括确定满足以下等式的子密文：\n[0045] Vi＝Valuei(K(n),V)+Noisei(K(n),R)\n[0046] 其中，\n[0047] V是该值，\n[0048] n是子密文的数目，\n[0049] K(n)是密钥，\n[0050] R是一组随机数，\n[0051] Vi是第i个子密文，\n[0052] Valuei是K(n)和V的第i个函数，且\n[0053] Noisei是K(n)和R的第i个函数。\n[0054] Valuei和Noisei相对于n可能具有线性的时间复杂度。\n[0055] 每一子密文可以包括将第一结果和第二结果相加，其中第一结果是基于与该子密文相关联的密钥和数值的函数的值，且第二结果是基于与该子密文相关联的密钥和一个或多个随机数的函数的值。\n[0056] 这两个函数都可以相对于子密文的数目具有线性时间复杂度，即这些函数相对于子密文的数目不成指数时间复杂度，从而可扩展以增加子密文数目。\n[0057] 确定密文可能与密钥的存储大小在复杂度上成线性。\n[0058] 确定每一子密文可以基于数值和密钥的乘法(或除法)。与也由该方法加密的、每个与不同密钥相关联的其他数值相比，该密钥对于该数值而言可以是唯一的。\n[0059] 每一子密文可以基于整个数值或根本不基于数值。在确定子密文时，没有数值的总计(summary)、取整(rounding)或子部分(sub-part)。\n[0060] 每一子密文可以独立于数值的其他子密文。即，子密文不用于确定数值的其他子密文。\n[0061] 该方法还可以包括以下步骤：\n[0062] 确定一组随机数分量；\n[0063] 其中确定密文的步骤还基于该组随机数分量。\n[0064] 随机数分量可以包括一个或多个随机数。\n[0065] 一优点是，由随机数将噪声引入密文中，使产生的密文难以破解。在该情况下，使用的子密文越多，随机数越多，则继而加密越安全。\n[0066] 确定密文的步骤可以基于包括一组密钥分量的密钥，其中该组密钥分量中的密钥分量的数目等于子密文的数目，且确定该组随机数分量的步骤包括确定满足如下等式的一组随机数：\n[0067]\n[0068] 其中，\n[0069] n是子密文的数目，\n[0070] K(n)是密钥，\n[0071] fi是密钥的第i个函数，\n[0072] R是一组随机数分量；且\n[0073] Noisei是K(n)和R的第i个函数。\n[0074] fi和Noisei相对于n可能具有线性的时间复杂度。\n[0075] 至少一些实施例的优点是，通过遵守正确性条件，该方法是可定制的，即用户可以定义满足上文的公式的特定同态加密算法。\n[0076] 该等式可能是可组合的且该方法还包括：\n[0077] 将加密的方法的一个或多个实例的加密的方法的密钥融合，以创建\n[0078] 该加密的方法的新的实例。\n[0079] 该数据库在包括属性的结构中可以存储值，且使每一子密文被存储的步骤还包括在单独的属性中存储每一子密文。\n[0080] 一优点是，标准数据库结构可被用于存储密文。因而，由于无需扩展或改变当前的数据库管理系统，从而避免了使用特殊设计的存储结构，且仍然可以使用使用数据库的标准协议。\n[0081] 每一子密文具有数值类型。\n[0082] 数据库可以是关系数据库。\n[0083] 可以重复该方法以使多个数值的密文存储在数据库中，其中每一密文作为单独的记录存储在单个数据库中的相同的表或相关的表中。\n[0084] 由于该加密方法对于选择密文或纯文本的攻击是健壮的，所以一优点是，不同且相关的值的密文可以存储在单个数据库中且避免了扩展不同数据库之间的密文以提高加密的健壮性的需要。\n[0085] 每一子密文可以存储在数据库中作为数值类型。一优点是，子密文不会太大而不能被存储为数值。通过将子密文存储为数值，允许类似于要对那些子密文执行的求和以及平均这样的操作。\n[0086] 在第二方面，提供了软件，其是存储在计算机可读介质上的计算机可读指令，该指令当由计算机执行时使计算机执行前述权利要求中任何一项的方法。\n[0087] 在第三方面，提供了一种用于加密要在数据库中存储的数值的计算机系统，其包括：\n[0088] 处理器，用于使用加法同态加密确定针对该数值的密文，其中该密\n[0089] 文包括两个或更多个子密文；且用于使每一子密文单独地且在单个记录\n[0090] 中存储在数据库中。\n[0091] 该方法可以由安全管理系统执行，该安全管理系统与数据库和由用户使用以查询数据库的客户端应用进行通信。\n[0092] 在又一方面，提供了一种记录在计算机可读介质上的数据库，其中该数据库存储具有两个或更多属性的记录，其中每一记录包含表示数值并使用加法同态加密确定的密文，该密文被存储在记录中作为两个或更多个子密文，且每一子密文被存储在不同的属性中。\n[0093] 数值也可以表示成第二密文，第二密文与原始密文不同。数据库还可以包括用于存储第二密文的子密文的第二组属性。一优点是，密文形式的数值的冗余拷贝被存储意味着可以使用第二版本来验证对原始密文的任何处理，例如查询。\n[0094] 数据库可以由数据库管理系统(DBMS)管理。\n[0095] 在另外的方面，提供了一种用于对存储在数据库中的密文进行解密的计算机实现的方法，该方法包括：\n[0096] 接收或访问使用加法同态加密来确定的密文，其中该密文表示数值且其包括两个或更多个子密文；以及\n[0097] 基于每一子密文且使用包括一组密钥分量的加密密钥来解密该密文，其中密钥分量的数目与密文的数目相同。\n[0098] 在合适的情况下，该解密的方法可以满足上文陈述的公式。\n[0099] 上述方法的另外的方面包括计算机系统和软件。\n[0100] 另一方面提供了一种计算机实现的方法，其用于对数据库执行聚合查询，其中查询的每一数值对象被存储为使用加法同态加密确定的密文，该密文包括单独存储在记录中的两个或更多个子密文，且记录的每一子密文与不同的属性关联，该方法包括：\n[0101] 对于每一属性，聚合与该属性相关联的每一子密文以确定加密的聚合值；以及[0102] 通过聚合每一加密的聚合值确定针对该查询的加密答案。\n[0103] 聚合可以通过求和计算或平均值计算。每一加密的聚合值可以任意大。\n[0104] 上文的方法还包括：\n[0105] 基于用于对该查询的所有数值对象进行加密的密钥来解密针对查询的加密的答案。\n[0106] 上文的方法还可以包括：\n[0107] 基于用于对该查询的所有数值对象进行加密的随机数来解密针对查询的加密答案。\n[0108] 上文的方法的另外的方面包括计算机系统和软件。\n[0109] 另一方面提供了一种计算机实现的方法，其用于执行基于乘法的对数据库的查询，其中该查询的每一数值对象被存储为使用乘法同态加密确定的密文，该密文包括单独存储在记录中的两个或更多个子密文，该方法包括：\n[0110] 针对该查询的每一对数值对象，执行该对数值的子密文的外积，以确定加密的相乘值。\n[0111] 基于用于对该查询的所有数值进行加密的密钥来解密针对该查询的加密的答案。\n[0112] 该方法还可以包括聚合加密的相乘值。这可以通过上文所描述的方法。\n[0113] 该方法还可以包括以上文描述的方式乘以聚合的加密的相乘值。上文的方法的另外的方面包括计算机系统和软件。\n[0114] 在另一方法中，提供了一种计算机实现的方法，其在数据库中创建表以存储表示数值并使用加法同态加密确定的密文，其中每一密文包括两个或更多个子密文，其中该方法包括：\n[0115] 创建两个或更多个属性，以每一个存储每一密文的不同子密文；\n[0116] 其中子密文的数目与所创建的属性的数目相同。\n[0117] 用于确定存储在属性中的每一子密文的加密方法可以是相同的但是通常具有不同的参数，例如密钥值和随机数值。\n[0118] 表中的属性的顺序可以被随机化。\n[0119] 该表可能与表名称相关联，且该方法还可以包括存储表名称的加密版本。\n[0120] 每一属性可以与属性名称相关联，且该方法还可以包括针对每一属性存储相关联的属性名称的加密版本。\n[0121] 上文的方法的另外的方法包括计算机系统和软件。\n[0122] 在另外的方面提供了一种将记录插入到数据库的表中的计算机实现的方法，该记录包括表示数值并使用加法同态加密确定的密文，其中该密文包括两个或更多子密文，其中该方法包括：\n[0123] 将记录插入到数据库中，其中每一子密文存储在不同的属性中。\n[0124] 上文的方法的另外的方面包括计算机系统和软件。\n[0125] 第一方面的可选特征也是(在适当的情况下)也在此描述的其他方面的可选特征。\n附图说明\n[0126] 现在将参考下面的附图来描述非限制性的示例，其中：\n[0127] 图1至图3示出了DBMS的不同部署(应用环境)；\n[0128] 图4是示出加密的方法的流程图；\n[0129] 图5提供了5个数值；\n[0130] 图6提供了包括加密密钥的示例密钥组件值；\n[0131] 图7提供了一组示例的随机数值；\n[0132] 图8至图11示出了使用在图5至图7中的值的加密、解密和查询方法的第一实例；\n[0133] 图12至图15示出了使用在图5至图7中的值的加密、解密和查询方法的第二实例；\n[0134] 图16至图19示出了使用在图5至图7中的值的加密、解密和查询方法的第三实例；\n以及\n[0135] 图20示出了调整记录/元组内的分享以适应表的随机属性/列。\n具体实施方式\n[0136] 介绍\n[0137] 该示例描述了技术的使用，包括云计算，其应用到许多区域或领域，其使用数据库来包含敏感数据，例如银行中的金融数据库、医院和保险公司中的健康记录数据库、军事和政府数据库、以及在云上外包和部署的其他数据库。根据该示例，数据库是安全的，即使当数据库底层的服务器受到攻击者的入侵、被恶意软件或病毒感染、或甚至由不信任的数据库管理员或数据库服务提供商管理时。\n[0138] 在该示例中，这一点通过用于在一个或多个数据库中加密数值并对加密的数据直接执行查询的同态加密方法和系统来实现。具体地，在该示例中提供了有效地执行和(SUM)和平均值(AVG)的聚合操作，且不改变或扩展当前的DBMS。该示例还包括验证查询结果的完整性的方法。\n[0139] 在该示例中，将数值(纯文本)加密到密文中，其中密文由多个部分组成，上述多个部分中的每一部分称为子密文(秘密分享(secret share))。由加密密钥来确定分享的数目。可以将秘密分享存储到数据库表中的不同属性(列)中但是在相同的元组(当在数据库中执行时的记录)中。每一分享包括噪声(随机数)，使得相同的数值被加密到不同的密文中，从而使得加密健壮以对抗选择纯文本的攻击和选择密文的攻击。加密方案的安全性只取决于加密密钥的保密性。\n[0140] 为了对加密的值进行解密，该方法指示DBMS将该值的所有的秘密分享返回。将这些分享与秘密密钥组合允许将加密的值从分享解密。\n[0141] 为了对一个表记录或属性执行SUM和AVG的聚合操作，该方法指示DBMS单独对属性的每一相关的分享列来执行SUM或AVG操作，并且然后如果已知秘密密钥，则可以从聚合分享的和或者平均值解密所期望的和或者平均值。\n[0142] 为了对两个属性值执行乘法，该方法指示DBMS计算子密文的两个向量的外积，其中的每一个与一个属性值的密文对应，且然后如果已知秘密密钥，则可以从外积解密乘积。\n属性值的乘积可以被进一步聚合。\n[0143] 该示例还提供了对查询结果的完整性的验证，所述查询结果包括SUM和AVG的结果。这涉及将值存储到冗余拷贝中，其中每一拷贝在数据库表中具有其加密的分享。对每一拷贝执行查询，且然后通过比较每一拷贝上的结果来验证其结果，如果上述结果底层的分享没有被篡改，则所述结果应该相等。\n[0144] 在该示例中，通过以本领域的技术人员理解的方式定义数据库模式(表及其属性)来设计数据库。但是，当在DBMS中实现数据库设计时，创建了表及其属性，其中无意义的散列值作为其名称。此外，设计中的属性通常被实现成若干属性，其中的每一个对应于：由加密方案生成的秘密分享或用于支持具有相等或不相等比较的查询的索引。以此方式，该实现中的数据库模式(表及其属性)在设计中不泄漏关于数据库的任何信息。\n[0145] 此外，在该示例中，当查询数据库时，仍然是基于设计中的数据库模式来制定查询。由于DBMS所看见的数据库模式是不同的，所以这样的查询不能直接由DBMS执行。该示例包括一种将基于设计中的数据库模式制定的查询重新写为可以在加密的数据库(在其中模式被散列)上直接执行的一个查询或多个查询的方法。在将结果返回数据库应用之前，通过使用该示例的方法来处理和验证来自DBMS的查询结果。\n[0146] 示例部署\n[0147] 本领域的技术人员将明白可以部署许多不同的计算系统来支持DBMS。在此我们提供了这样的计算系统的三个示例。在第一个部署(应用)环境中，企业使其数据库在DBMS中管理，其运行在物理上在企业内维护的服务器上，如图1中所示出的。在第二个应用环境中，企业仍然具有其自身的DBMS，但是其运行在云中的虚拟服务器上，如图2中所示出的。即，服务器未处于企业的物理控制下。在第三个环境中，企业在云中设置的DBMS服务上维护其数据库，如在图3中所示出的。现在将更详细地描述这三个计算系统。\n[0148] 在图1中，服务器108位于企业100的管理界限之内，所述企业还管理多个机器客户端101和安全管理机器103。在此，机器被理解为任何适当的计算系统。客户端101运行数据库应用102。为了执行查询(包括数据库创建和更新语句)，数据库应用102向安全管理机器\n103上的查询代理104发送查询。基于秘密密钥105，查询代理104将查询翻译成将由DBMS \n107执行以创建、查询或更新加密的数据库106的一个或多个查询。当从DBMS107返回查询结果时，查询代理104处理该结果并向应用102发送最后的查询结果。\n[0149] 现在转向在图1中示出的第一个应用环境中的数据库的安全性，DBMS107运行在服务器108上，其处于企业100的物理控制之下。当服务器108被入侵或感染时，攻击者或病毒或恶意软件可以访问数据库106中的数据。但是，由于其被加密，所以数据仍然是安全的。在另一方面，由于根据单独的职责原则的原则，数据库管理员不应访问秘密密钥105，因此其无法读取数据库106的数据内容。通过使用其他的分离机制，可以提高应用环境的安全性。\n例如，105中的密钥可以在加密之后存储，且可以在访问控制下调节对来自查询代理104的DBMS 107的访问。\n[0150] 在图2中，企业200安装其DBMS 207，并且然后将其加密的数据库206加载到运行在云209中的虚拟服务器208上。在图3中，企业300依赖于DBMS服务307来管理其加密的数据库\n306。DBMS服务由云308提供。在这两个应用环境中，由于底层的虚拟服务器208和DBMS服务器307在物理上是由云209或云308的提供商管理的，所以企业200或300失去了对其自身加密的数据库206或306的物理控制。但是，加密的数据库206或306中的数据内容由于是加密的，所以其对云提供商或攻击者而言是安全的。查询代理204和304分别处于企业200和300的物理控制下。它们由数据库应用202和302访问(当数据库应用102访问查询代理104时)。\n[0151] 要注意的是，在此描述的加密方案可以被应用于与上文所描述的三个环境不同的环境。例如，如下文所示出的，加密密钥由多个独立的分量组成，且如果这些分量由不同的主体保管，则仅当所有的主体都同意使用其密钥分量时才可以解密值。在另一方面，加密的值由多个分享组成，其可以分布地存储在多个加密的数据库中。\n[0152] 在相关的应用环境中，通过安全管理模块103、203或303来实现下文进一步描述的方法。安全管理模块与客户端和DBMS服务通信。安全管理模块应该被视为软件和硬件的混合，其为根据形成软件的计算机指令作用于指令的计算机处理器。安全管理系统可以访问(通常是本地访问)存储了相关密钥和模式105、205或305信息的存储介质。未被示出的是，由安全管理系统用来执行诸如从客户端接收查询以及从DBMS接收数据之类的方法的输入和输出。本领域的技术人员将明白在客户端、安全管理计算机系统以及服务器/云之间可以使用不同的通信协议，例如适合在安全管理系统与客户端之间的LAN通信、以及在安全管理系统与作为DBMS服务的主机的计算机系统之间的WAN通信的协议。\n[0153] 现在将参考图4中的流程图描述该示例的方法。首先，适合与这些方法一起使用的数据库必须被创建400并存储在存储器106、206或306中。数据库的模式也存储在存储器\n105、205或305中。\n[0154] 然后，针对每一数值，确定402分享。这参考也存储在存储器105、205和305中的密钥和随机数来完成。然后，安全管理模块103、203、或303使这些分享存储404在数据库106、\n206或306中。这通过向然后存储406分享的DBMS 107、207和307发送相关指令来完成。\n[0155] 从而，一旦利用分享填充数据库，就可以对数据库106、206和306执行操作，例如更新记录408、删除记录410以及执行查询412。由安全管理模块执行的这些方法中的每一个经由加密数据库上的DBMS进行通信。\n[0156] 下面将进一步详细描述这些步骤中的每一个。\n[0157] 加密和解密算法\n[0158] 我们在此描述了同态加密方案的通用定义。同态是一种允许对密文执行特定类型的计算并获得加密结果的加密的形式，其中该加密结果也是对纯文本执行的操作的结果的密文。\n[0159] 在这部分中，加密方案中的密钥由K(n)来表示，其中n(n＞1)是密钥K中包含的用于指示在加密结果中的秘密分享的数目的信息。较大的n导致对蛮力攻击(brute-force)更健壮的加密结果。\n[0160] 让Enc为加密方案的加密算法，其被称为加密方案的实例。假设V是要加密的数值。\n要注意的是，可以将其他数据类型(像字符串)转换成数值类型以使用加密方案。然后，加密方案被设计成具有如下形式。\n[0161] Enc(V，K(n))＝(V1，...，Vn)  (1)\n[0162] 在(1)中，加密结果是n个分量的元组，其对应于n个子密文(秘密分享)，其可以被放入数据库表中的n个列中。在加密期间，算法Enc将噪声(随机数)添加到每一分享Vi。让R表示在V的一个加密中使用的该组随机数。然后，将加密结果中的Vi定义为如下。\n[0163] Vi＝Valuei(K(n)，V)+Noisei(K(n)，R)  (2)\n[0164] 在(2)中Vi的定义中，Valuei是K(n)和V的函数，尤其是与V成线性关系；Noisei是K(n)和R的函数，计算用于将Vi随机化的随机数。为了使我们的方案随着分享数目的增加可扩展，函数Valuei和Noisei相对于分享数目n的数目具有线性时间复杂度。由于R，由于在每一加密中的不同随机数，加密方案确保了利用相同的密钥对相同值的两个加密具有不同的结果。以此方式，因为由于每一密文中的噪声和包含更多噪声的更多对，导致了秘密密钥无法通过选择纯文本及其密文的对而被恢复，所以加密方案相对于选择纯文本的攻击和选择密文的攻击是健壮的。\n[0165] 解密方案被设计成具有以下形式，从该形式我们可以看见所有的秘密分享都需要执行成功的解密。\n[0166] Decry((V1，...，Vn)，K(n))＝V  (3)\n[0167] 为了其正确性，加密方案必须具有以下属性。即，解密结果应该与正被加密的值相同。\n[0168] Decry(Enc(V，K(n))，K(n))＝V  (4)\n[0169] 在本发明中Decry算法被定义为下面的表达式，其中秘密分享Vi上的系数fi(K(n))是密钥K(n)上的函数。再次，为了使我们的方案在分享数目n增加时可扩展，函数fi相对于分享数目n在时间复杂度上为线性的。该表达式使得加密方案同态，如下文进一步描述的。\n[0170]\n[0171] 基于(2)中Vi的定义，表达式(5)被重新写入表达式(6)中，其等于表达式(7)。\n[0172]\n[0173]\n[0174] 为了满足正确性的属性(4)，必须由函数fi(K(n))、Noisei和Valuei确保下面的两个条件成立，其确定加密方案中的加密算法和解密算法。\n[0175]\n[0176]\n[0177] 即，如果已知秘密密钥K(n)，则根据条件(8)可以抵消所有分享中的噪声，且可以根据条件(9)恢复原始值V。当已知秘密密钥时，通过线性地处理所有分享可以抵消分配到所有分享中的噪声。下面将进一步描述加密方案的三个实例，其中通过表明其满足条件(8)和(9)来证明其正确性。\n[0178] 同态\n[0179] 加密方案是加法同态且其也被示出是乘法同态。这使得加密方案能够支持在对加密的数据库的查询中的SUM和AVG的聚合操作。在下文中，将证明的是，当满足条件(8)和(9)时，加密方案是同态的。\n[0180] 假设K(n)是秘密密钥。如下面所示出的，存在全部都是利用K(n)加密的m个值V1,…,Vm。\n[0181] Enc(V1，K(n))＝(V11，...，V1n)  (10)\n[0182] Enc(Vm，K(n))＝(Vm1，...，Vmn)  (11)\n[0183] 为了证明本发明中的加密方案针对SQL中的SUM操作是同态的，则下面的约束必须成立。要注意的是，以分量方式将加密的值添加到(12)中。\n[0184]\n[0185] 基于(5)中的Decry定义，等式(12)的左手侧等于下面的表达式，通过用 来\n替换(5)中的Vi来获得。\n[0186]\n[0187] 通过使用初等代数中的分配律，可以将表达式(13)重新写入下面的表达式。\n[0188]\n[0189] 通过使用初等代数中的交换律，将表达式(14)重新写入下面的表达式中。\n[0190]\n[0191] 如果满足了条件(8)和(9)，根据(5)中Decry的定义，我们有Vj＝\n从而，表达式(15)等于 且当满足条件(8)和(9)时，约束条件(12)成立。\n[0192] 对于针对AVG操作的加密方案的同态，证据表明针对本发明中的正确加密和解密算法，下面的约束条件被满足。要注意的是，通过将每一分享的和除以加密的值的数目m来获得加密的值的平均值。\n[0193]\n[0194] 在用于SUM操作的证明过程之后，等式(16)的左手侧等于下面的表达式。\n[0195]\n[0196] (17)中的表达式被进一步减少为以下的表达式。\n[0197]\n[0198] 基于减少的(15)的结果，如果条件(8)和(9)都被满足，则上面的表达式等于等式(16)的右手侧。从而，对于正确的加密和解密算法，约束条件(16)成立。\n[0199] 此外，也通过乘法同态，加密方案可以是完全同态的。在数据库上对需要乘法操作的加密的值运行查询的场景是有用的场景。例如，员工表包括速率列和小时列。然后，来自员工的SQL查询“选择SUM(速率*小时)”需要是加法和乘法同态。\n[0200] 假设存在两个纯文本消息V和V’、以及两个密钥K(n)和K’(n’)，其可以是相同的密钥或不同密钥。使用上文的加密方案，可以产生下文的密文。\n[0201] Enc(V，K(n))＝(V1，...，Vn)\n[0202] Enc(V′，K′(n′))＝(V′1，...，V′n′)\n[0203] 然后，两个密文乘法是其外积，如下文所示出的。\n[0204] (V1*V′1，...，V1*V′n′，\n[0205] Vn*V′1，...，Vn*V′n′)\n[0206] 解密该密文将产生期望的乘法V*V’。解密由以下的步骤组成。\n[0207] 步骤1：针对i，从1到n，执行以下的解密以得到Vi*V’。\n[0208] Decry((Vi*V′1，...，Vi*V′n′)，K′(n′))＝Vi*V′\n[0209] 步骤2：执行以下的解密以得到V*V’。\n[0210] Decry((V1*V′，...，Vn*V′)，K(n))＝V*V′\n[0211] 加密方案的实例\n[0212] 通过给出对在Enc和Decry算法的定义中使用的函数值、噪声和f(K(n))的不同定义，加密方案可以被实现成不同的实例。在此描述了加密方案的5个实例，其正确性条件(8)和(9)被证明。其可以在应用环境中使用以保护数据库数据的隐私性，且也被用作用于指导其他实例的定义的示例。\n[0213] 在该第一实例中，密钥K(n)是具有n个元素(n＞1)的列表，其被写为[k1，...，kn]，其中每一ki是实数。对于攻击者而言，猜测实数密钥来执行蛮力攻击更难，这是因为即使是在小范围(例如，从1到10)内，也存在可以在计算机中表示的大量的实数。对于该实例，需要k1+...+kn-1≠0且kn≠0。要加密的数值被表示成V且加密结果被表示成元组(V1，...，Vn)。对于该实例，通过以下步骤来定义加密算法Enc。\n[0214] 步骤1：生成n-1个随机数{r1，...rn-1}的集合R。\n[0215] 步骤2：通过估计表达式k1*V+ri来产生Vi(1≤i≤n-1)。即，对于1≤i≤n-1，Valuei(K(n)，V)＝ki*V且Noisei(K(n)，R)＝ri。\n[0216] 步骤3：通过估计表达式kn*(r1+...+rn-1)生成最后的分量Vn。即，Valuen(K(n)，V)＝0且Noisen(K(n)，R)＝kn*(r1+...+rn-1)。\n[0217] 让(V1，...，Vn)成为要解密的元组。在这个实例中由以下步骤来定义解密算法Decry。\n[0218] 步骤1：计算L，其被定义成\n[0219] 步骤2：针对该结果估计表达式 即，针对1≤i≤n-1，\n[0220] fi(K(n))＝1/L，且fn(K(n))＝-1/(L*kn)。\n[0221] 针对该实例，等式(8)的左手侧是 其被减小至0，且等式(9)的\n左手侧是 其被减小至V。从而，在该实例中，Enc和Decry算法满足该正确性\n条件。\n[0222] 在第二实例中，更多的随机噪声被添加到加密的元组。在该实例中，密钥K(n)是一组实数对的列表，其由[(k1,s1),…,(kn,sn)]表示，其中n＞1。对于1≤i≤n需要ki≠0，s1+…+sn-1≠0且sn≠0。让V成为要加密的数值。加密算法Enc采用以下步骤来产生加密的元组(V1,…,Vn)。\n[0223] 步骤1：产生n-1对随机数{(r1,p1),…,(rn-1,pn-1)}的组R。\n[0224] 步骤2：通过使用表达ki*(si*V+pi)+ri产生Vi(1≤i≤n-1)。即，对于1≤i≤n-1，Valuei(K(n),V)＝ki*si*V且Noisei(K(n),R)＝ki*pi+ri。\n[0225] 步骤3：通过估计表达式 来计算Vn。即，Valuen(K(n),V)＝\n0且\n[0226] 算法Decry通过以下步骤将元组(V1,…,Vn)解密成V：\n[0227] 步骤1：计算S，其为\n[0228] 步骤2：针对该结果，减小表达式 即，对于1≤i≤n-1，fi(K(n))\n＝1/(kiS)，且fn(K(n))＝-1/(kn*sn*S)。\n[0229] 与第一实例中的解密相比，如果所有的密钥ki都不同，则该解密算法中的每一Vi具有不同的系数fi(K(n))。这增加了蛮力攻击的困难，其中为了解密V，不得不全面地搜索每一Vi的系数。\n[0230] 根据如下所述的检查该实例的正确性。对于该实例，等式(8)的左手侧是表达式其被减小至0。对于该实例，\n等式(9)的左手侧是以下表达式 如所期望的，其被减\n小至V。\n[0231] 在该第三实例中，密钥K(n)被表示成[(k1,s1),…(kn,sn)]，其中n＞1，且ki和si是实数。该第三实例针对1≤i≤n需要ki≠0，s1+…+sn≠0。假设值V将被加密到元组(V1,…,Vn)中。下文示出了Enc算法的加密步骤。\n[0232] 步骤1：产生n对随机数{(r1,p1),…,(rn,pn)}的组R。\n[0233] 步骤2：通过使用表达式 产生V1。即，Value1(K(n),V)\n＝k1*s1*V且\n[0234] 步骤3：对于2≤i≤n-1，通过估计表达式 来计算\n每一Vi。即，对于2≤i≤n-1，Valuei(K(n),V)＝ki*si*V且\n[0235] 步骤4：通过使用表达式 来计算Vn。即，Valuen(K\n(n),V)＝kn*sn*V且 为了解密元组(V1,…,\nVn)，算法Decry采用以下步骤。\n[0236] 步骤1：计算S，其为\n[0237] 步骤2：针对该结果，减小表达式 即，对于1≤i≤n，fi(K(n))＝1/(ki*S)。\n[0238] 下面是该实例的正确性验证。针对该实例的等式(8)的左手侧是表达式N1+N2+N3，其每一项在下面定义。\n[0239]\n[0240]\n[0241]\n[0242] 由于每一正项 或 分别具有相应的负项 或\n且每一正项 具有相应的负项，这一表达式被减小至0。\n[0243] 对于该实例，等式(9)的左手侧是表达式 其被减小至V。\n[0244] 通过在子密文中添加更多的噪声项，从第二实例导出第四实例。该实例中的密钥K(n)是列表[k1,…,kn]，且n≥4。从而，存在正整数h和m，使得n＝h+m+2。基于h和m的选择，n个密钥分量是实数的元组，如下文所定义的。\n[0245] ●对于1≤i≤h，每一ki是元组(wi,si1,…,sim,ti)；\n[0246] ●对于h+1≤i≤h+m，每一ki是元组(siu,…,sim,ti)，其中u＝i-h；\n[0247] ●对于h+m+1≤i≤n，每一ki是单元组(singleton tuple)(ti)。\n[0248] 对于值V，加密算法Enc通过使用以下的步骤利用密钥K(n)来产生密文(V1,…,Vn)。\n[0249] 步骤1：产生n-1个随机数：r1,r2,…,rh,rr,rs1,rs2,…和rsm；\n[0250] 步骤2：对于1≤i≤h，\n[0251] 步骤3：对于i＝h+1，\n[0252] 步骤4：对于h+2≤i≤h+m, 其中u＝i–(h+1)；\n[0253] 步骤5：Vn-1＝rsm+tn-1*rr；\n[0254] 步骤6：Vn＝tn*rr。\n[0255] 给定密文(V1,…,Vn)，解密算法采用以下步骤来产生V。\n[0256] 步骤1：RR＝Vn/tn；\n[0257] 步骤2：RSm＝Vn-1–tn-1*RR；\n[0258] 步骤3：对于m-1≤u≤1且i＝u+h+1，\n[0259] 步骤4：对于i＝h+1，\n[0260] 步骤5：\n[0261] 步骤6：\n[0262] 通过在子密文中添加更多的噪声项从第三实例导出第五实例。该实例中的密钥K(n)也是列表[k1,…kn]，且n≥4。从而，存在正整数h和m，使得n＝h+m+2。基于选择的h和m，n个密钥分量是实数的元组，如下文所定义的。\n[0263] ●对于1≤i≤h+1，每一k1是元组(wi,si1,…,sim,ti)；\n[0264] ●对于h+2≤i≤h+m，每一k1是元组(siu,…,sim,ti)，其中u＝i–h；\n[0265] ●对于h+m+1≤i≤n，每一ki是单元组(ti)。\n[0266] 对于值V，加密算法Enc通过使用以下的步骤利用密钥K(n)来产生密文(V1,…,Vn)。\n[0267] 步骤1：产生n个随机数：r1,r2,…,rh,rh+1,rr,rs1,rs2,…和rsm；\n[0268] 步骤2：\n[0269] 步骤3：对于2≤i≤h+1，\n[0270] 步骤4：对于h+2≤i≤h+m， 其中u＝i–(h+1)；\n[0271] 步骤5：Vn-1＝rsm+tn-1*rr；\n[0272] 步骤6：Vn＝tn*rr。\n[0273] 给定密文(V1,…,Vn)，解密算法Decry工作如下来产生V。\n[0274] 步骤1：RR＝Vn/tn；\n[0275] 步骤2：RSm＝Vn-1–tn-1*RR；\n[0276] 步骤3：对于m–1≤u≤1且i＝u+h+1，\n[0277] 步骤4：\n[0278] 步骤5：\n[0279] 本发明中的加密方案的实例是可组合的。想法是来自一个实例的一个分享可以被另一实例进一步加密，而对于解密，该过程反过来。此外，可以融合来自两个实例的密钥、加密和解密算法，这提供一种容易的创建新实例的方法。即，通过创建新的等同的实例，融合实现对两个实例的组合。\n[0280] 在下文中，以上文的第一实例和上文也阐述的第二实例作为用来解释密钥的融合、其加密和解密算法的融合的示例。\n[0281] 新实例中的融合的密钥具有以下的形式，其组合了第一和第二实例的密钥。\n[0282] [(k1,k11,s11),(k1,k12,s12),….,(k1,k1n’,s1n’),\n[0283] …,\n[0284] (kn,kn1,sn1),(kn,kn2,sn2),….,(kn,knn’,snn’)]。\n[0285] 直观地，[k1,…,kn]是针对第一实例的密钥，且针对来自第一实例的每一分享i，针对第二实例的密钥是[(ki1,si1),…,(kin’,sin’)]。即，通过第二实例利用不同的密钥来对来自第一实例的每一分享进行加密。\n[0286] 融合加密：\n[0287] 步骤1：产生随机数：一组n-1个随机数{r1,…,rn-1}以及其它的n组(n’-1)对随机i i i i\n数{(r1,p1),…,(r (n’-1),p (n’-1))}，其中i是从1到n。即，通过第二实例利用不同的随机数对来自第一实例的每一分享进行加密。\n[0288] 步骤2：针对每一密钥分量产生以下的n*n’分享：\n[0289] (V11,V12,….,V1n’,\n[0290] …,\n[0291] Vn1,Vn2,….,Vnn’)。\n[0292] 对于与密钥分量 对应的分享Vij，其在以下的情况中的一个\n[0293] 中计算：\n[0294] 情况1：如果i＜n且j＜n’，则\n[0295] 情况2：如果i＝n且j＜n’，则\n[0296] 情况3：如果j＝n’，则对于1＜＝i＜＝n， 融合\n的加密：\n[0297] 步骤1：计算L，其被定义成\n[0298] 步骤2：对于每一i，其中1＜＝i＜＝n，执行以下的两个步骤\n[0299] 步骤2a：计算Si，其是\n[0300] 步骤2b：计算中间分享\n[0301] 步骤3：计算最后的值\n[0302] 加密示例\n[0303] 图5给出了将通过使用先前所描述的三个算法加密的5个值。值I1和I3被设计成为相同的值1383.2。值I2和I4非常接近，一个为2965.8，另一个为2965.7。值I5是3196.1。\n[0304] 图6中给出了加密算法所使用的密钥。第一算法仅使用k1、k2和k3，而第二和第三也使用s1，s2和s3。要注意的是，三个加密算法允许密钥为实数，因此密钥可以是负数。\n[0305] 每一个值的密钥需要一组随机数。图7给出了要在示例中使用的该组随机数。并非全部的三个加密算法的都需要图7中的所有随机数。每一随机数为了引用都有名字。例如，随机数178.2具有名字r11。\n[0306] 在第一个加密算法示例中，这5个值被加密成图8中示出的值。由于密钥具有分量k1、k2和k3，密钥结果由三个分享组成。例如，利用用符号I1E11、I1E12和I1E13提及的三个分享-1016888.76、7284791.54以及26137991.5将值I1加密成I1E1。在图8中，在分享下面给出了计算每一分享的表达式。例如，分享I1E11来自表达式k1*I1+r11。\n[0307] 在图9中示出了使用第一算法的解密结果。值I1D1是I1E1的解密，其与I1相同。其他的四个解密值也类似命名且等于其相应的纯文本。用于解密的表达式被示出在解密的值下方。在图9中，L是解密算法所使用的中间值。\n[0308] 图10示出了值SumIE1，其是解密值的和。SumIE1由三个分享组成，其每一个是相应分享的和。例如，第一分享是5个加密值中第一分享的和。图10也示出了值SumID1，其是SumIE1的解密结果。在解密SumIE1的表达式中，SumIE11表示第一解密分享的和。值SumID1与I1+I2+I3+I4+I5的和相同。L在图9中定义。与图10类似，图11示出了5个加密值的平均值，以及平均值的解密。解密的平均值是2378.8，等于所期望的平均值(I1+I2+I3+I4+I5)/5。\n[0309] 图12给出了使用第二算法来加密第二示例中图5中的5个值的结果。利用I1E2、I2E2、I3E2、I4E2和I5E2来表示解密的结果。由于密钥具有三个分量[(kl,s1),(k2,s2),(k3,s3)]，所以每一结果具有三个分享。在图11中在分享下方示出了用于产生每一分享的表达式。\n[0310] 在图13中示出了针对单个值的解密结果，其中S是由解密算法使用的中间值。可以检查的是，所有解密的值I1D2、I2D2、I3D2、I4D2和I5D2等于相应的值I1、I2、I3、I4和I5。用于解密的表达式也示出在每一解密结果的下方。\n[0311] 解密的值I1E2、I2E2、I3E2、I4E2和I5E2在图14中求和。和SumIE2中的每一分享是相应分享的和。在图14中也示出了使用第二解密的和SumIE2的解密。解密结果是11894，与I1、I2、I3、I4和I5的和相同。图15给出了加密值的平均值，且其解密使用第二解密算法。\n[0312] 在该示例中，第三算法被应用于加密I1、I2、I3、I4和I5，且在图16中示出了结果。\n在该算法中，使用了图7中的所有随机数。用于产生每一分享的表达式在每一解密结果下方示出。\n[0313] 图17示出了每一单个加密值的解密，且图18示出了解密加密值的和的结果。所有解密的值是正确的，由于其等于相应的值(I1、I2、I3、I4和I5)或那些值的和。最后，在图19中解密加密值的平均值。\n[0314] 对加密数据库的管理\n[0315] 图1、图2和图3中示出的、在三个应用环境中的查询代理充当创建加密数据库、查询加密数据库、以及更新加密的数据库的角色。\n[0316] 数据库通常由一组表组成，且每一表包括一组记录。表的结构由一模式(schema)描述。我们将记录表示成元组(V1,...,Vn)，且相应的模式表示为(A1:Type1,....,An:\nTypen)，其中Ai是表的属性，且Typei是属性Ai的类型。记录必须符合表模式。即，Vi必须具有类型Typei。\n[0317] 在此，示例涉及数字数据的加密以及如何对其执行SUM和AVG的聚合操作。从而，我们聚焦在表中的数字属性上。数值类型，表示成NUM，可以是整数、浮点数、或双精度数。此外，在本发明中，独立地保护表中的属性。于是我们在下面描述如何保护一个数值属性。\n[0318] 对于数值属性，我们可以为其加密分配一个或多个密钥。所有的密钥通过查询代理单独用于加密属性值。如果存在m个密钥，则属性值被单独加密m次，产生m个加密值。为了检查加密值的完整性，查询代理对其全部进行解密，并且然后检查其是否相等。在下文中，我们说明了通过向数值属性分配两个密钥K1(n)和K2(n)进行管理。\n[0319] 为了利用相等和不相等比较来支持查询，查询代理需要散列算法，例如SHA1算法，以及保序加密(OPE)算法。所以查询代理需要保留用于OPE算法的其他密钥。为了简单起见，我们假定OPE算法针对一个属性使用密钥ikey。\n[0320] 用于将值V散列的算法被表示成Hash(V)。散列算法也用于散列数据库名称、表和属性名称。让OPE(ikey,V)表示通过使用OPE算法利用密钥ikey的V的加密。然后，针对两值V1＜V2，OPE算法在加密之后保持其顺序，即OPE(ikey,V1)OPE(ikey,V)。\n[0387] 公式colname＜V被转换成\n[0388] Hash(colname+”neq”)