【浙江大学张秉晟分享】RAM模型下的多方隐私函数评估( 六 )

文章图片
整个ObliviousCycle如上图中的左图所示，你可以想象成它其实就是TinyRAM的一个机器。这个机器的所有状态全部都是以秘密分享密态的形式存储的,它有PrivatePC（ProgramCounter）。你每次来一个指令的时候，指令是从哪里读的呢？指令我们专门有内存的Memory ，我们这个结构、内存的Memory是可以不区分指令区和数据区的。也就是说如果你的代码的写作方式是在你代码的运行期间动态产生代码、新的代码，我们是可以支持这种形式的。即你不需要把代码定制在这个Memory里面，代码的那部分Memory只读，数据的Memory可以读写，我们不需要这样。代码和数据是可以混在一起的，而且你可以动态的去修改你的代码。有一些病毒就很喜欢并且能做到把自己数据区域的数据变成代码再去运行。
我现在不是以程序安全的角度去讲这件事情，是以功能性的角度去讲这件事情。我们其实可以满足这样的功能需求。我们这个程序会从这个Memory里面、隐私保护里面取一条指令进行解析，解析完毕后，这条指令它会有操作数还有它自己做的是什么操作、要用到什么寄存器。比如说我们会用到什么寄存器，寄存器寻址或者立即数寻址。我们再到内存里去取相关的数，取了相关的数以后我们做操作，做完操作以后再进行选择，就是你实际上的结果。我们再把这个结果存回去，然后根据你的Flag ，我们会去update这个ProgramCounter ，就是我们下一条要运行哪条指令。我们基本上是根据这个ProgramCounter到这个Memory里面再去取下一条指令。

文章图片
具体来说，其实我们的ObliviousCycle最大的开销就是我们要支持二十多条的TinyRAM的指令集。我们要做到所有指令集都在同一个步骤里面完成。大致的思路就是如何防止你知道我做的是哪一条指令，我们就把所有的指令都做了，当然不是把每一条指令单独做一遍。观察上图的左边部分你会发现，我们对所有的指令集有机进行组合。
也有前人在工作中把若干的指令集用姚式混淆电路编出来。姚式混淆电路会比较大，我们这里是用ABY的结构，有一些用姚式混淆电路做，有一些用布尔电路做，有一些是用代数电路做，所以我们这个非常高效。对于所有的指令集，我们可以在三轮内完成，包括Compare、一些比较、一些跳转，各种指令在三轮内完成。我们有一些指令做的会比较快，有一些指令做的会比较慢，有一些指令之间是共享一些中间结果的，所以我们是有机的去组合起来。

文章图片
我们整体的MPC的PrivateFunctionEvaluation的大概运行结构如上图所示：第一轮要Fetch ，就读一条指令。第二轮Decode这个指令，顺便去读取相关的操作数。第三轮是Execute ，因为我们需要涵盖指令集里面所有的指令，所以Execute其实需要三轮。第四轮是写，因为写和Fetch可以同时执行，所以它们在同一个pipeline里面可以重叠。基本上我们这个程序就是这样循环。

文章图片
我们为了展示这个程序的效率做了一些相关的RAM结构下比较常见的函数的Evaluation 。比如说BinarySearch ，比如说SetIntersection ，比如说QuickSort 。具体我们把Offline、Fetch、Decode、Evaluation、Write的时间都分开测了，也包括Totaltime 。注意，因为我们是保护函数的，所以相比于不保护函数的一些安全多方计算，时间确实慢一点。