论文标题
多用户私人信息检索用于计算有限数据库的能力
The Capacity of Multi-user Private Information Retrieval for Computationally Limited Databases
论文作者
论文摘要
我们提出了一个私人信息检索（PIR）方案，该方案允许用户通过与其他用户勾结，同时隐藏所需的消息索引，从任意数量的数据库中检索单个消息。当只有一个可访问的数据库时，该方案特别重要 - 在多数据库情况下，PIR对PIR的特殊情况更具挑战性。 The upper bound for privacy-preserving capacity for these scenarios is $C=(1+\frac{1}{S}+\cdots+\frac{1}{S^{K-1}})^{-1}$, where $K$ is the number of messages and $S$ represents the quantity of information sources such as $S=N+U-1$ for $U$ users and $N$数据库。我们表明，提议的信息检索方案即使仅存在一个数据库，也可以达到限制的容量，这与大多数现有的作品不同，这些作品在访问多个数据库中以掩盖用户隐私。与多数据库案例不同，该方案将数据库无法用于由于计算复杂性而由多个用户进行的交叉引用查询。
We present a private information retrieval (PIR) scheme that allows a user to retrieve a single message from an arbitrary number of databases by colluding with other users while hiding the desired message index. This scheme is of particular significance when there is only one accessible database -- a special case that turns out to be more challenging for PIR in the multi-database case. The upper bound for privacy-preserving capacity for these scenarios is $C=(1+\frac{1}{S}+\cdots+\frac{1}{S^{K-1}})^{-1}$, where $K$ is the number of messages and $S$ represents the quantity of information sources such as $S=N+U-1$ for $U$ users and $N$ databases. We show that the proposed information retrieval scheme attains the capacity bound even when only one database is present, which differs from most existing works that hinge on the access to multiple databases in order to hide user privacy. Unlike the multi-database case, this scheme capitalizes on the inability for a database to cross-reference queries made by multiple users due to computational complexity.
