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">pk 所有参与者都知道，并拆分了秘密密钥 ski">ski， i&＃x2208;[1:d]">i∈[1:d]，在哪里 [1:d]">[1:d] 表示的所有整数的集合 1">1 至 d">d。在MSQP协议中，秘密解密密钥ski">ski 仅数据库所有者知道 Di">Di。所有秘密密钥的集合表示为sk">sk。公钥pk">pk只需要所有数据库所有者知道；客户或外部人员不应将其告知。因此，当选择特定的密码系统时，数据库所有者可以使用它们之间的安全加密通信来共享公共密钥。这使得数据库所有者可以轻松地在彼??此之间共享公共密钥。

pk">ski">i&＃x2208;[1:d]">[1:d]">1">d">ski">Di">sk">pk">对于纯文本 t">t，其加密表示为 E(t,pk)">E(t,pk)。给定密文 c">c，使用密钥对其进行解密 ski">ski 用表示 D(c,ski)">D(c,ski)。的解密c">c通过依次应用所有拆分键来执行以下操作：

密码系统的以下属性至关重要。 

（P1）拆分键的属性。使用所有拆分的秘密密钥进行的解密必须正确还原原始明文t">

 （P2）广义同态性质。对于任何kk">明文 ，k">tj">j&＃x2208;[1:k]">给定产品 解密算法（1）必须恢复其明文的总和：

k">k">tj">j&＃x2208;[1:k]">

 k">k">tj">j&＃x2208;[1:k]">D&＃x220F;j=1kE(tj,pk)=&＃x2211;j=1ktj.">在这种情况下，我们也可以说密码系统满足广义加法同态性质。

7.2 。MSQP协议的阶段

MSQP协议使用一台查询服务器 Q">问。该协议的各个阶段在图2中进行了描述。数据流在图3中示出。