具有串通服务器的语义私密信息检索的能力-计算机科学-机器学习-语义私有信息检索-算法.pdfVIP

具有串通服务器的语义私密信息检索的能力

MohamedNomeirAlptugAytekinSennurUlukus

DepartmentofElectricalandComputerEngineering

UniversityofMaryland,CollegePark,MD20742

mnomeir@umd.eduaaytekin@umd.eduulukus@umd.edu

摘要—我们研究了语义私有信息检索（Sem-PIR）问题，其。我们扩展了这个模型并在此研究共

中个服务器串通（Sem-TPIR），即这些服务器共同分享用户谋Sem-PIR（Sem-TPIR）。我们展示了如果先验和消息长

查询。在Sem-TPIR中，消息的大小不同，并且任何用户检索消度相同，则Sem-TPIR的容量为

息的概率也不均匀。这是经典PIR问题的一种推广，在经典PIR

问题中，消息的大小相等并且检索概率相同。早期关于Sem-PIR。为了展示该容量，我们找到了一个可实

的工作考虑了没有串通的情况，即串通参数为。在本文中，现速率的上限，并提供了一个达到此上限的方案。

本我们研究了一般情况下任意的问题。我们找到了检索率

的一个上限，并设计了一个达到此速率的方案，即我们推导出了II.问题表述

译Sem-TPIR的确切容量。

中I.介绍令表示服务器的数量，表示消息的数量，

1表示串通参数。每个消息符号都是独立且均匀随机生成的，

v在[1]中，介绍了私有信息检索（PIR）的问题。在对所有符号和所有消息均如此。第条消息的长度是，

8PIR中，有条消息，，每条消息的长度均为我们将第条消息表示为。因此，消息的熵由

1

8，并且这些消息被复制到了个服务器上。用户从集合

5(1)

1中均匀随机选择，并希望以私密的方式检索相

7.应消息，即不向任何服务器透露所需消息的索引，发送

0查询给每个服务器。收到查询后，每个服务器根据其数据集给出用户向服务器发送查询以检索第条

5

2和接收到的查询发送一个答案，然后将其传送给用户。在接消息，其中表示发送给第个服务器以检索第条消

:收所有答案后，用户应能够解码所需的消息。在[2]中表息的查询。用户在方案启动前对任何消息内容一无所知，

v

i明，该问题的容量，即消息位数与下载符号数之间的最高可因此，

x

r能比率是。在[3]中，

a(2)