论文标题
两个数据库对称私人信息检索的沟通成本：多个秘密的有条件披露观点
Communication Cost of Two-Database Symmetric Private Information Retrieval: A Conditional Disclosure of Multiple Secrets Perspective
论文作者
论文摘要
我们考虑了两个数据库对称私人信息检索（SPIR）的总（上传下载）通信成本（通过其与秘密（CDS）的有条件披露）的关系。在SPER中，用户希望从$ n $ not-colluding和Repliced数据库中检索消息，而无需学习除了检索消息之外的任何内容，而没有单独的数据库学习检索到的消息索引。在CD中，两个各方各自持有个人意见，并共享一个共同的秘密希望在且仅当他们的投入满足公共确定性功能时，以有效的方式向外部方披露此秘密。作为CD的自然扩展，我们介绍了多个秘密（CDM）的条件披露，其中两个方共享多个i.i.d.〜公共秘密，而不是CD中的一个共同秘密。我们表明，CDM的特殊配置等效于两个数据库螺旋。受此等价的启发，我们使用CD和CDM的双分图表设计下载的下载效率螺旋方案，并确定$ k = 3 $消息的确切最低总通信成本$ n = 2 $数据库Spir。
We consider the total (upload plus download) communication cost of two-database symmetric private information retrieval (SPIR) through its relationship to conditional disclosure of secrets (CDS). In SPIR, a user wishes to retrieve a message out of $K$ messages from $N$ non-colluding and replicated databases without learning anything beyond the retrieved message, while no individual database learns the retrieved message index. In CDS, two parties each holding an individual input and sharing a common secret wish to disclose this secret to an external party in an efficient manner if and only if their inputs satisfy a public deterministic function. As a natural extension of CDS, we introduce conditional disclosure of multiple secrets (CDMS) where two parties share multiple i.i.d.~common secrets rather than a single common secret as in CDS. We show that a special configuration of CDMS is equivalent to two-database SPIR. Inspired by this equivalence, we design download cost efficient SPIR schemes using bipartite graph representation of CDS and CDMS, and determine the exact minimum total communication cost of $N=2$ database SPIR for $K=3$ messages.
