Alice如何使Bob能够在私有映射中查找值？

Question

我认为这个问题类似于私有集交集，但在以下方面是不同的：

Alice有一个扩展的id到name映射

id1 ->无名氏id2 -> Jane Doe id3 -> Edgar Poe

鲍勃有一个简短的身份证的名单

id1 (爱丽丝知道这个人的名字) id3 (爱丽丝知道这个人的名字) id4 (爱丽丝不知道这个人的名字)

Bob和Alice都不想彼此共享他们所有的数据资产。然而，爱丽丝已经同意分享鲍勃所知道的身份的人的名字。另一方面，鲍勃不想让爱丽丝知道他有什么身份。

是否有任何已知的、安全的协议只涉及双方？(不信任第三方等)

Answer 1

很多(大多数？)领先的PSI协议可以很容易地调整以提供此功能。它有时被称为“带关联数据的PSI”或“带有数据传输的PSI”。例如，您可以看到在以下文件中显式地描述了PSI的这个变体：

埃米利亚诺·德·克里斯托法罗和吉恩·铁迪克。实用的具有线性复杂度的私有集交集协议。金融密码2010年。

甚至许多没有显式提及“关联数据”的协议也可以很容易地进行修改以提供它。我确信以下文件(这是最快的两党半诚实的PSI)将支持它：

本尼·平卡斯，托马斯·施耐德，吉尔·塞格夫，迈克尔·佐纳：分阶段:使用基于置换的散列的私有集交集。。Usenix 2015。Vladimir Kolesnikov，Ranjit Kumaresan，Mike，Ni Trieu：高效批处理，不经意的PRF与应用到专用集交集。 CCS 2016。

这些协议为PSI使用了一个“不经意的PRF”范例，其工作原理大致如下：

1. 各方执行一个不经意的PRF，其中爱丽丝学习(描述)一个随机函数F和鲍勃学习F(y)在他的集合中的每一个y。
2. 爱丽丝可以计算和发送F(x)为他的集合中的每一个x。现在，Bob可以与他的一组F-values进行比较，并识别交集。对于Alice拥有但Bob没有的值x，对应的F(x)值在Bob看来是随机的，因此没有泄漏关于该x的信息。

在这些协议中还有相当多的算法/组合内容，但最终在某种程度上，该协议正在完成我前面描述的任务。

若要向此协议大纲添加关联数据，只需使用F(x)值作为密钥对关联数据进行加密。就像这样：

• 对于每一个y，Bob都有F(y)，并且(如果不够长的话)用PRG对其进行扩展，以获得两个值tag_y和k_y。
• 对于每一个x，Alice类似地将F(x)扩展为tag_x和k_x。她发送(tag_x, \mathsf{Enc}(k_x, data[x]))，其中data[x]是与键x相关联的记录/数据。
• Bob可以查找表单(\tau, c)的元组，其中\tau是他识别为tag_y的标记。然后，他可以用相应的密钥c对k_y进行解密，以获得与y关联的数据。