【浙江大学张秉晟分享】RAM模型下的多方隐私函数评估( 四 ) IEEExATECIEEExATEC科技思享会是由

文章图片
我先简单介绍一下DPF 。 DPF是DistributedPointFunction ，它最经典的构造是两方的DPF ，就是有个Generate ，它会Generate出两个K ，这个K一方给左边，一方给右边，两个服务器S1和S2 。这两个服务器分别针对这个K做Evaluate ，把做出来的最后一行的从β0到β3两个东西全加起来，它其实是一个Unitvector 。什么叫Unitvector？它只有一位是non-zero ， none-zero位通常在这个应用场景里面会把它取为1 ，其他每一位都是0 ，也就是说这其实是一个Compression的过程，把一个Unitvector给compress成一个log2(n)Size的T 。因时间问题，具体的做法我在此就不一一讲了，这是一个比较经典的技术，它是用一个Tree的Structure ，在每一层会有一个Correction 。也就是说它一共有log2(n)层，所以它的KSize会有log2(n) 。这个在数据量比较大的时候，这个Tree的Expansion耗时会比较长；但是在数据量比较小的时候，它的操作会非常的快。

文章图片
2PC会有一些缺点， 2PC的这个FSS ，传统的FSS-basedPIR：
第一,它不能直接用在我们这里，原因是它需要两个Server两个服务器，看见相同的铭文，它其实是一个多Server的PIR 。服务器上面的两个服务器要有一模一样的数据，然后你选取这个数据里面一模一样的PIR的位置，再到自己本地进行合成。
第二是这个Client知道自己要取哪一个数。那我们要做这个分布式的RAM ，首先服务器不能知道这个数据的铭文是什么。其次，服务器在我们这个应用场景里面甚至也不可以知道它要取哪一个数。也就是说这两个都必须得秘密分享、必须得保护。

文章图片
所以我们才会有一个4Server的结构。大概的思路是一个DPF需要两个服务器，有相同的值。在双服务器的情况下，这两个服务器必须存明文。但我们如果有4服务器，我们其实可以把这个数据秘密分享成两份。举个例子，这两份分别由S3和S4去拿同一份秘密分享的Share ， S1和S2拿同一份秘密分享的Share ，也就是ReplicatedShare 。这两个拿同一份、那两个拿同一份，这样我们可以让S1去生成一个DPF的K分给S3和S4 。 S3和S4针对他们共有的Share可以做刚才的PIR的Evaluation 。同理，这个S1和S2也可以对他们共有的Share去做PIR的Evaluation 。

文章图片
这里还会有一个问题，就是我们要取的这个点也不能透露给别人。要取的这个点不透露给别人，我们的做法就是在offline阶段，可以做一个DPF针对一个随机的点。比如说i是0到N减一里面任意的一个数，等到你实际上你要存取的那个值出来的时候，你把实际要存取的值减掉我们之前prepare的时候随机选的那个值，出来的那个数它其实就是一个offset ，就是一个纠正量。我们让所有的服务器对自己的数据shift这个Cyclic的shift ，就是去循环的移动偏移量，使得我们做的这个DPF它就相当于是针对一个未知的秘密分享的目标索引做的DPF 。具体我在此就不细讲了。

文章图片
做完了以后， 4方各自会做一个linearfunction ，也就是说他们不需要通信就可以以秘密分享的形式去得到要取的数，就比如说你要取第i个数，那么这个数就叫Xi 。根据上图的公式，你其实就可以算出这个Xi是什么，即Xi也是一个秘密分享的形式存在的。