ElGamal密码系统、多级分离查询处理（MSQP）协议
1、介绍
当多个数据库所有者希望通过创建分布式云数据库以协作方式使用其单独的云数据库时，可能需要创建并维护一个具有隐私保护的超大型分布式云数据库，但不允许共享其个人中包含的机密数据数据库。
例如，大量的记录可以存储在一个分布式数据库中，该数据库结合了来自不同医院甚至几个不同国家的数据。这种类型的数据库可以由世界卫生组织管理，并且可以是巨大的。未经患者法律许可，可能会阻止不同的医院重新分配其数据存储。在数据库所有者位于不同国家的情况下，其中一些国家可能已制定法律，要求将患者的机密数据存储在实际位于同一国家的数据中心中。其他国家将来可能会考虑引入类似的隐私法。对于包含不同公司的置信度商业数据的大型云数据库，可能会出现类似情况。同样，这可能为不愿共享其客户信息的几个在线交易站点的协作带来好处。结合来自不同地区的患者数据来分析大型数据集的能力可以改善医学数据的统计分析结果（参见[3]，[4]）。重要的是，必须在整个非常大的分布式云数据库中发布对某些聚合查询的答案，尤其是因为统计查询可以帮助改善疾病的预测和患者的治疗质量（参见[5]）。数据库所有者可能需要以某种方式回答客户提出的汇总统计查询，就像来自所有数据库的所有记录都包含在单个公共数据库中一样。但是，法律要求不允许数据库所有者将其患者的记录转移到其他实体。因此，必须保护机密数据的隐私。同时，由于分布式数据库可能非常大，因此计算期间的通信成本必须最小。
采用多级分离查询处理（MSQP）协议，该协议采用具有分裂密钥的同态加密
统计查询私有处理的新颖的MSQP协议。MSQP协议的参与者是数据库所有者，他们代表官方注册实体，并且没有匿名参与者。因此，很自然地假设数据库所有者是诚实的。例如，数据库所有者可能是不同的医院，这绝对是诚实的，甚至他们可能并不好奇。这就是为什么在MSQP协议中，我们可以将所有数据库所有者视为诚实但好奇的参与者，因为在任何情况下，由于法律要求，都必须保护数据的机密性，以防止所有参与者的好奇心。
7.1 。具有用于MSQP协议的分割密钥的密码系统
在MSQP协议中，数据库所有者使用同态加密来安全地组合其计算的辅助结果。MSQP可以使用满足以下规定的属性（P1）和（P2）的任何密码系统。本节仅介绍可用于描述MSQP协议的密码系统的一般符号和属性。满足所要求的性能（P1）和（P2）密码系统的两个例子在章节中给出 5次预赛的ElGamal加密方案的，6多部分的ElGamal密码系统。
MSQP协议使用具有一个公共密钥的密码系统 pk 所有参与者都知道，并拆分了秘密密钥 ski， i∈[1:d]，在哪里 [1:d] 表示的所有整数的集合 1 至 d。在MSQP协议中，秘密解密密钥ski 仅数据库所有者知道 Di。所有秘密密钥的集合表示为sk。公钥pk只需要所有数据库所有者知道；客户或外部人员不应将其告知。因此，当选择特定的密码系统时，数据库所有者可以使用它们之间的安全加密通信来共享公共密钥。这使得数据库所有者可以轻松地在彼??此之间共享公共密钥。
对于纯文本 t，其加密表示为 E(t,pk)。给定密文 c，使用密钥对其进行解密 ski 用表示 D(c,ski)。的解密c通过依次应用所有拆分键来执行以下操作：
密码系统的以下属性至关重要。
-
（P1）
拆分键的属性。
使用所有拆分的秘密密钥进行的解密必须正确还原原始明文
-
（P2）广义同态性质。对于任何k明文 
，给定产品 
解密算法（1）必须恢复其明文的总和：
在这种情况下，我们也可以说密码系统满足广义加法同态性质。
7.2 。MSQP协议的阶段
MSQP协议使用一台查询服务器 问。该协议的各个阶段在图2中进行了描述。数据流在图3中示出。
在下面的第7.5节的算法1中提供了MSQP协议步骤的一般说明 。算法1中提供了应用MEC的协议步骤的更多详细信息。
（图2。MSQP协议的阶段。）
（图3。MSQP协议的数据流程图，用于计算和返回查询结果）
7.3 。查询样本并在MSQP协议中记录
主要功能的选择 F当客户端通过指示请求哪个统计信息作为查询样本的输出传达查询时，进行查询。对于众所周知的统计数据，用户足以表明该术语。另一方面，用户也很容易提交数学表达式作为要在查询输出中使用的公式。
通过指定条件为查询选择的记录集称为查询样本或查询集。属于查询样本的记录也称为样本记录。为了选择查询样本，客户端可以使用各种逻辑运算符，通过指定要保留的属性不等式来组合记录中属性的条件，并使用布尔运算符来组合这些条件。然后，数据库所有者可以将条件应用于其数据库部分，以选择查询样本中的记录部分。
假设每条记录a的分布式数据库包含n属性，在哪里n是一个正整数。我们假定所有属性都是数字，因为分类属性也可以编码为数字。表示记录中存储的属性a通过
要选择分布式数据库中的记录样本，每个查询都使用布尔表达式。表示为
所有布尔表达式的集合。可以通过以下两个规则来归纳定义此集合。
表2。数据库所有者，子样本及其记录。
在整个过程中，我们考虑使用布尔表达式的查询
。它选择存储在数据库中的记录。表示为小号=乙（d） 查询样本，即整个分布式数据库中满足条件的所有记录的集合 乙。让米=|小号| 是样本中的记录数 小号。