趣题:如何在数据库中秘密地查询隐私数据

    日常生活中经常会出现这样的场景:你想在数据库上查询某个东西,但却不希望留下线索,让别人知道你查询了什么。比方说,投资人可能会在数据库上查询某支股票的信息,但却不希望任何人知道他感兴趣的股票究竟是哪一支。看上去,似乎唯一的办法就是把整个数据库全部拷回家。然而,这些数据往往都拥有非常庞大的体积,全部拷走通常都是很不现实的;另外,考虑到数据内容的隐私性和数据本身的宝贵价值,数据的持有者通常也不允许其他人把整个数据全盘拷走。不过,随着分布式数据库的广泛应用,上面的难题有了一个两全其美的好办法:假设有两个内容完全相同的数据库,投资人可以先在第一个数据库上执行一个不会透露目的的查询,再在另一个数据库上执行另一个不会透露目的的查询,两次查询结合起来便能推出想要的结果。只要没有人刻意去收集并且对比两个数据库的查询记录,那么谁也不会知道投资人真正想要查询的是什么。在这个背景下,我们有了下面这个有趣的问题。

    服务器随机产生了一个 {1, 2, …, 100} 的子集 S ,并且同时发送给了 A 和 B 两名前台工作人员。 A 、 B 两名前台都接受其他人的提问,但为了保护数据,两个人都只能用“是”或者“否”来回答问题,并且都不允许同一个人重复提问。你非常关心某个数 n 是否在这个子集里。其实,你本来可以直接问 A 和 B 中的任何一个人“数字 n 是否在集合 S 里”,但是这样一来,对方就知道了你想要查询的是什么。为此,你可以向 A 和 B 各问一个问题(结合两人的回答便能推出集合 S 里是否包含数字 n ),但却不能让 A 和 B 当中的任何一个人知道你查询的是哪个数(我们假设 A 、 B 两人不会串通起来,把他们各自收到的问题联系在一起)。事实上,你需要保证 A 和 B 两人都不能从你的问题中获取到任何信息,也就是说,对于 A 和 B 当中的任何一个人来说,各种问题出现的概率不会随着 n 值的改变而改变。再换句话说,如果 n 的值变了,那么 A 和 B 各自将会听到的问题应该拥有和原来相同的概率分布。


 
 
 
 
 
 
 
 
 
 
 
 
 

    答案:首先,自己随机生成一个 {1, 2, …, 100} 的子集 T1 (每个数都有 1/2 的概率被选进 T1 )。如果 T1 里面正好包含数字 n ,那么就把 T1 里的数字 n 去掉,把所得的结果记作 T2 ;如果 T1 里面没有数字 n ,那么就在 T1 中加入数字 n ,从而得到 T2 。现在,将 T1 发送给 A ,并询问 T1 里面是否有偶数个数正好也在 S 里。类似地,再将 T2 发送给 B ,并且询问同样的问题:在 T2 里面是否有偶数个数同时也属于 S 。注意, T1 和 T2 的唯一差别,就是一个里面有 n 一个里面没有 n 。因此,如果 A 和 B 的回答是一致的,就说明数字 n 不在 S 里面;如果 A 和 B 的回答不一致,就说明数字 n 在 S 里面。另外,容易看出,不管是 T1 还是 T2 ,从 1 到 100 每个数在里面出现的概率都是 1/2 。因此,不管是 A 还是 B ,他被问到的问题都总是具有完全相同的概率分布,这不随 n 的变化而变化。

 
 
    这种方案的缺陷就是,每条询问都非常长。为了描述 T1 或者 T2 ,我们需要使用一个 100 位的 01 串,它一共有 100 个 bit 。如果 S 不是 {1, 2, …, 100} 的子集,而是 {1, 2, …, N} 的子集,那么在上述方案中,我们需要给 A 、 B 各发送 O(N) 个 bit 的数据。在 N 非常大的情况下,这么做同样是不现实的。有趣的是,如果前台不止两个人,而是四个人的话,那么我们可以做得更好:我们可以给四个人都只发送 O(√N) 个 bit 的数据,并且同样保证每个人都不能从中推出任何信息来。

    为了便于说明,我们现在假设 S 是 {0, 1, 2, …, 99} 的一个子集。假设你想要知道, 67 是否在集合 S 里。于是,你首先随机生成一个 {0, 1, 2, …, 9} 的子集 T1 ,然后在里面加上数字 6 (如果 T1 里没有 6 的话)或者去掉数字 6 (如果 T1 里有 6 的话),得到 T2;再生成另一个 {0, 1, 2, …, 9} 的子集 T3 ,然后在里面加上数字 7 (如果 T3 里没有 7 的话)或者去掉数字 7 (如果 T3 里有 7 的话),得到子集 T4 。接下来,向 A 、 B 、 C 、 D 依次询问下面四个问题

      A :在所有十位数属于 T1 并且个位数属于 T3 的数当中,是否有偶数个数在集合 S 里。
      B :在所有十位数属于 T1 并且个位数属于 T4 的数当中,是否有偶数个数在集合 S 里。
      C :在所有十位数属于 T2 并且个位数属于 T3 的数当中,是否有偶数个数在集合 S 里。
      D :在所有十位数属于 T2 并且个位数属于 T4 的数当中,是否有偶数个数在集合 S 里。

    如果 T1 等于 {2, 4, 7, 8, 6} ,那么 T2 就应该等于 {2, 4, 7, 8} ;如果 T3 等于 {2, 3, 5} ,那么 T4 就应该等于 {2, 3, 5, 7} 。四次询问之后我们便可得知,在下图各种颜色的方框中,属于集合 S 的数有奇数个还是偶数个。结合 A 、 B 的回答(蓝色方框和黄色方框),我们就能推出,在集合 S 当中,十位数属于 T1 并且个位数恰好为 7 的数有奇数个还是偶数个;结合 C 、 D 的回答(红色方框和绿色方框),我们就能推出,在集合 S 当中,十位数属于 T2 并且个位数恰好为 7 的数有奇数个还是偶数个。于是,我们就可以知道,十位数恰好为 6 并且个位数恰好为 7 的数是否在集合 S 当中了。

      

    类似地,如果集合 S 是 {1, 2, …, N} 的子集,那么我们可以对这 N 个数进行重新编码,使得每个数都由高位和低位组成。那么,高位和低位的取值范围都是从 1 到 √N 。在整个协议中,我们需要给每个人发送两个 {1, 2, …, √N} 的子集,这相当于两个 √N 位的 01 串,因此其数据量为 2√N 个 bit ,也就是 O(√N) 个 bit 。

    不过,请注意,虽然与每个人交流的数据量少了,但这次却有四个人了,因而你需要发送四个这么大的数据。当 N 很小的时候, 4 · 2√N 很可能反而比 2 · N 更大。

    同样地,如果我们有 2d 个人,我们就可以把 1 到 N 里面的所有数都看作 d 位数,每一位的取值范围是从 1 到 N1/d 。为了完成一次查询,我们需要给每个人发送 d 个 {1, 2, …, N1/d} 的子集,因此总共需要发送 2d · d · N1/d 个 bit 。对于不同的 N ,我们可以选取最合适的 d ,使得 2d · d · N1/d 最小。例如,下图所示的就是 N = 1 000 000 时函数 f(d) = 2d · d · N1/d 的图像,可见 d = 4 时的通信成本是最低的。因此,如果查询点足够多的话,我们可以选择在 16 个不同的地方进行查询。

      

参考资料: B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, Private Information Retrieval, Journal of the ACM (JACM), 1998

14 条评论

  • mathfan

    久停之后必有长篇!相当精彩!ps:又一个沙发!

  • 沭 荔

    这是大学内容吗?表示看不懂,

  • 您的昵称(必填)

    记得有本介绍自然语言处理的书说过,有人建立的语料库,允许用户进行各种统计,但用户不能将数据库考走(数据库的拥有者不会允许,用户也没那么大硬盘)

  • dead suspect

    很有意思!最后一部分总bit数的变化很有启发性

  • 大河

    果然牛的一塌糊涂

  • None

    我问A,里面有没有n,n-1;问B,里面有没有n,n+1。也可以吧

  • 251

    真的看不懂。。

  • Sparktang

    回复 楼层: 地幔 | 2013-07-31 18:11 | None 的评论

    原题也说过:“事实上,你需要保证 A 和 B 两人都不能从你的问题中获取到任何信息,也就是说,对于 A 和 B 当中的任何一个人来说,各种问题出现的概率不会随着 n 值的改变而改变。”
    所以如果你去问“S里面有没有n,n-1”,另外问“S里面有没有n,n+1”是不合题意的,这么做等于每次查询操作都留下了一条再明显不过的查询记录,该记录泄漏出你关心的数字是n与n-1(或者n+1)二者之一。

  • 肥得

    考虑在使用前一种需要发送O(N)bit的方法时,说不定T1恰巧只有一个数,然后我按照规则生成T2,去问前台工作人员。这个时候前台工作人员被我弄昏头啦,因为我所有可能询问他的问题都是一样的概率(?这里是有疑问的,他哪里知道,他只知道我问了他一个问题而已),所以他不知道我真正想询问的n是哪个。
    再考虑我每次只随机生成一个数,作为T1,按同样规则生成T2,然后我去问前台工作人员同样的问题。这个前台工作人员知道的信息和上一个前台工作人员一样多,那么O(1)的方法不也蒙混过关不能让前台人员知道我想询问的n吗?

    所以是不是有这样的预设:我需要在这个前台工作人员那里问很多次问题?是不是这样的预设应该在问题里面写明白?

  • 如果 S 是 {1, 2, …, 99,100} 的一个子集, 而不是 {0, 1, 2, …, 99} 的一个子集,在4个人的情况下,十位数是不是应该在{0, 1, 2,….10}里面抽而个位数在{0, 1, 2….., 9}里面抽?

  • 熊熊熊

    如果现在S是{1,2,3…., 99,100}而我要查的数据正好是100,假设有4个工作人员,那么我T1,T2就需要在{1,2,…,9,10}里面随机产生,而T3,T4就需要在{0,1,….,8,9}里面随机产生。是这样的吗?

  • dpcer

    这是云计算中的Private Information Retrieval问题,已经有了很多种基于不同入手点的解决方法。

    随便说个简单的改进方案,需要使用可信硬件:

    前台工作人员换成一个可信硬件
    用户先验证和自己对话的前台的确是可信硬件,从而确认前台不会受到后台的秘密控制,是完全独立的
    用户对前台:我需要第3个数据单元的内容
    前台对后台:我需要所有数据单元的内容
    后台对前台:(a1,a2,a3……)
    前台对用户:a3

    考虑到用户对前台的通信是经过网络的,带宽较低,而前台对后台的通信是本地的,带宽较高,因此同样是“读取整个数据库”,但是这种做法就有了可行性

发表评论

  +  62  =  69