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

文章图片
显然这是一个安全多方计算的一个分支，也就是说它仍然是属于安全多方计算的领域。据我所知，目前传统的安全多方计算，所有商用的安全多方计算都是基于电路格式。 Sort格式什么意思？也就是说你只能顺序执行，你在安全多方计算里面是不可以支持RAM计算模型的。什么叫RAM计算？RAM就是RandomAccessMachine 。我们现在的常规电脑是冯诺依曼结构，在内存里可以随机访问或跳转RandomAccess 。比如说你做一个BinarySearch ，二分搜索，你不需要scan整个Memory ，你可以跳到你指定的位置去做读写、做比较，然后再做下一步操作。但是因为一些技术的限制，在安全多方计算里面我们现在不能做这种类似操作，我们现在只能顺序执行。而这种顺序执行会极大程度的限制我们安全多方计算可以使用的场景，比如说有一些我们需要跳转或者跳转比较多的算法就没办法高效的用安全多方计算来实现。
我们这次想要做的一个工作是在RAM模型下去实现一个PrivateFunctionEvaluation 。也就是说我们这个安全多方计算系统再也不用被编译成电路就能支持RAM的计算结构。如果你有一个死循环，你有一个WhileLoop ，甚至你的WhileLoop里面的Condition是一个不确定的Condition 。比如说一个死循环里面，你有一个基于私密数据的隐私保护数据的条件，那么我们这个模型也能够去支持，并且我们这个模型会保护你的算法。我们的做法大致讲来是把一些高级语言(比如C++语言或者Java等)用编译器(比如用LLVM的编译器)编译成TinyRAM的指令集，为什么是TinyRAM呢？因为我们需要一个精简指令集，如果指令集太复杂了我们整个系统的开销就会非常的大。所以我们就选了一个精简指令集， TinyRAM 。当然RISC-V也是可以的，我们对程序和输入都进行隐私保护。具体来说我们都进行秘密分享，我后面会一一和大家解释具体操作。
我们在程序秘密分享和数据秘密分享的前提下进行安全的执行，我们可以密态的执行。
MPC分布式ORAM先讲一下我们构建的一个前提工作，也就是我们要构建一个分布式的ORAM 。

文章图片
什么是分布式的ORAM呢？
传统的ORAM是讲你有一个服务器或者有多个服务器，然后有一个Client ，这个Client在服务器上面进行读写，它不能让服务器知道你读写的是哪一个位置。分布式ORAM指的是我已经不存在这样的一个Client ，我在安全多方计算时我要读写哪一格的位置，其实我要读写的这个数据也是隐私保护的，比如说它是以秘密分享的形式去保护的，然后在服务器上面进行读写，它也是一个分布式的结构。具体我们采用了4个服务器架构。如果你要只读的话，我们也可以做出3PC的格式。这个2PC的格式后面我们会讲，这是一个经典的PIR ，但它不是标准的ORAM ，它只是一个PrivateInformationRetrieval的实现形式，主要是基于DPF（DistributedPointFunction），也就是FSS（FunctioningSecretSharing）。
我们构建的这个分布式有几个特点：第一个特点，它可以进行任意次的读和写，而且读和写之间的转换是不需要Refresh、是不需要Eviction的。即我们看见的一些常见操作，可能它的读会很快，但是读转到写的过程中需要非常多的时间或者它的读写都比较快，但是它经过若干次的读写突然要进行一次Refresh或者进行一次Image ，这就极大程度的限制了这些ORAM在我们这个场景中的使用。具体来说，我们的O-READ ，它的通信量是12log2(n)bits ，这个N就是你这个Memory大概有多少Memory的size 。然后你在Memory里面取一个数，不让这个服务器知道你取哪一个数。我们需要的通信量是12倍的log2(n) ，然后你想oblivious去改写那个Memory ，就是你在一个N个size的Memory里面，你在某一条里面想去写入一个数。比如说在i条里面写入一个数，在我们这里AllRight的通信量是24倍的log2(n)加12tbits ， T其实就是你要写入的这个数据的长度，具体的操作它分Openδ、Cyclic-shift、Scale、Re-randomize ，稍后我会一一介绍。