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

文章图片
写怎么写呢？写会比读麻烦一点，因为如果只读的话3方也够，我们这个算法有3方的版本。如果你要写的话必须得4方。写，我们其实是有一个限制的。我们的写法大概的原理是你需要知道原始的数据是什么，你需要知道你写进去的这个数据是什么，然后你把写进去的这个数据减掉原始的数据，你就会有一个delta ，即有个修改量、偏移量。你需要把原始的数据增加多少量才会变成你现在想要它变成的这个数据。
因为在我们的应用场景里面，你在写之前必定是读过那个格子的值的，所以我们这边并不会增加任何额外的开销。即我们这个假设你需要知道原始的数据是什么？现在修改的数据是什么？在我们这个应用场景里面是默认的假设。你会利用DPF针对你内存里面的每一个值都进行增加一个偏移量，就是刚才你算出来的最新的值和以前的值之间的差。

文章图片
当然这个增加的时候你会需要乘以一个PointFunction ，也就是说绝大部分除了一个位置之外，其他所有位置你增加的偏移量都是0 。然后到那个位置，你增加的偏移量是Δv ，在其他部分都是0 。增加完、更新完以后，你的输出结果还是秘密分享，所以可以继续往下走不需要做读和写的转换。
文章图片
这个是我们具体的一个Benchmark的一个result 。我们针对一些常见的或者现在state-of-the-artDistributedORAM进行比较。比如我分别用红色、黄色和绿色来表示FLORAMORAM、SQRTORAM、CIRCUITORAM ，我用蓝色来表示我们自己的。因为我们自己可以做offline和online的分离，所以在图中我会画两条线，一条线就是直接online的运行时间，一条线是把online和offline合在一起的运行时间。那么我们的初始化时间是显著优于任何其他工作，可以说我们几乎不要初始化。在读的做法里面，我们在绝大多数情况下优于任何其他的工作，只有当这个数据量比较小的时候，比如说数据量在2的20次以下的时候，那么SQRTORAM会比我们的快一点点。这只是在某一些场景下面，比如说在WAN的场景下面。在写的方面，我们整体的效率和FLORAMORAM差不了多少。但是因为我们是可以把online和offline分开的，如果你只看online效率，当数据库比较大的时候、超过2的20次的时候，我们的效率明显高于所有已知的DistributedORAM 。
MPC模拟CPU
有了这个非常高效的DistributedORAM ，我们就可以开始模拟这个RAM结构的CPU了。我们模拟的思路是以RAM的形式去管理存储结构,包括所有的存储结构（我们用的是冯诺依曼结构）、包括整体CPU运行时候的你的指针PC值和一些Flag值、一些寄存器值、一些内存的值、一些指令，所有东西都由RAM形式接管。具体来说，我们把普通的代码，也就是任何一些C语言、高级语言的代码，用常规的编译器编译成TinyRAM的指令集。我们会对TinyRAM指令集里面的指令进行解析。解析完以后，我们会进行隐私保护的执行。我们后面会讲具体是怎么执行的。它是密态执行然后密态选择、茫然更新，整体、所有的过程都是Oblivious ，都是内存保护的。

文章图片
具体的指令集大概有25个左右，前半部分是boolean的指令集，也就是说位操作，比如说AND、OR、XOR、NOT、Shift等等。中间是一些加减乘除的常规操作，后面第三类是一些各种各样的比较，它的Flag会不一样，然后会有一些mov的操作、存取的操作和跳转的指令。