Communication Cost of Two-Database Symmetric Private Information Retrieval: A Conditional Disclosure of Multiple Secrets Perspective
Communication Cost of Two-Database Symmetric Private Information Retrieval: A Conditional Disclosure of Multiple Secrets Perspective
复制标题
两库对称隐私信息检索的通信成本：有条件披露多个秘密的视角
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Ulukus
中科院分区：
文献类型：
--
作者：
Zhusheng Wang;S. Ulukus
本文通过考虑双数据库对称私有信息检索（SPIR）与条件秘密披露（CDS）的关系来考虑其总（上传+下载）通信成本。在SPIR中，用户希望从N个非串谋和复制数据库的K条消息中检索一条消息，而不学习检索消息之外的任何内容，同时没有单个数据库学习检索消息索引。在CDS中，当且仅当双方的输入满足公共确定性函数时，双方各自持有一个单独的输入并共享一个共同的秘密，希望以有效的方式向外部方披露该秘密。作为CDS的自然扩展，我们引入了多秘密的条件披露（CDMS），其中双方共享多个i.i.d公共秘密，而不是像CDS那样共享单个公共秘密。我们证明了CDMS的一种特殊配置相当于双数据库SPIR。受此等价性的启发，我们利用CDS和CDMS的二部图表示设计了下载成本高效的SPIR方案，并确定了K = 3条消息时N = 2个数据库SPIR在消息长度为1时的确切最小总通信成本。
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 when the message length is 1.
登录
查看更多内容
影响因子：
2.5
作者：
Karim A. Banawan;S. Ulukus
通讯作者：
Karim A. Banawan;S. Ulukus
DOI：
10.1109/isit45174.2021.9517867
发表时间：
2021
期刊：
2021 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Li, Zhou;Sun, Hua
通讯作者：
Sun, Hua
影响因子：
2.5
作者：
Karim A. Banawan;Batuhan Arasli;Yi-Peng Wei;S. Ulukus
通讯作者：
Karim A. Banawan;Batuhan Arasli;Yi-Peng Wei;S. Ulukus
影响因子：
2.5
作者：
Zhusheng Wang;Karim A. Banawan;S. Ulukus
通讯作者：
Zhusheng Wang;Karim A. Banawan;S. Ulukus
影响因子：
2.5
作者：
Sajani Vithana;Karim A. Banawan;S. Ulukus
通讯作者：
Sajani Vithana;Karim A. Banawan;S. Ulukus