【安全多方计算之FSS】通俗易懂理解函数秘密分享——FSS（一）

通俗理解函数密码分享，形象生动地介绍了函数密码分享的前世今生，后续将陆续推出FSS的底层原理和深度哲学。

料理码王 · 2024-05-20 14:21:33 发布

0. 引言

在研读大量的文献、csdn和知乎之后，笔者发现大家都没有道清楚函数秘密分享——FSS的本质，都在把FSS的形式化语言抄来抄去，根本就没有能让普通人理解FSS的可能性。因此，笔者独家撰写了这个系列的技术文档，带大家通俗易懂地、形象生动地彻彻底底搞清楚FSS！

大部分人都想说PIR，即隐私信息检索，但是隐私信息检索的本质是什么？其实应该是安全多方计算，由多个人共同计算出一个输出 $f (x)$ ，同时不暴露函数 $f$ 的任何信息， $x$ 是大家都知道的。

大家先看秘密分享——SS方案的发展脉络（时间前后顺序）：
在这里插入图片描述
总结以上五种方案（时间前后顺序）：

方案名	中文名	描述	优势	劣势
FHE	全同态加密	加密输入，执行 $P$ 运算，获得输出，再解密	结果准确，易于设计方案	加解密耗时，运算也耗时
1/2 FHE	1/2 全同态加密	公钥加密输入，分片，执行运算结果，然后解密，就是输出	适用于多方安全计算	耗时，异步
两方 HSS（Bool）	两方布尔同态秘密分享	直接将 $x$ 随机分片，将分片的数据参与运算 $P$ ，输出结果，bool运算后输出结果	速度快	支持的操作有限
两方 HSS（算术）	两方算术秘密分享	直接将 $x$ 随机分片，将分片的数据参与运算 $P$ ，输出结果，算术运算后输出结果	速度快，支持算术运算	需要公开函数 $P$ ，无法支持非线性运算
FSS	函数秘密分享	函数分片，共同的输入，然后执行计算分片的结果，最后两个bool求和，输出最终结果	隐藏函数（功能）	函数分片方案较复杂，运算有限，暴露输入的 $x$

安全多方计算的初衷：隐藏各方的输入 $x$ ，共同参与一个已知的功能函数 $f$ 运算，并且最终各方将知晓最终的输出 $f (x)$ .
FSS之前的方案一直在想尽办法隐藏输入 $x$ ，并且不算优化运算和加密时间，起到了一定的效果；
由于之前隐藏输入 $x$ 的方案已经达到最佳，或者说已经没有了优化之处，于是诞生了FSS，对函数进行隐藏，同时共有输入 $x$ 。
此处先提一下FSS的具体应用（不理解没关系，后续会详解），会将输入 $x$ 给加入掩码，即隐藏了输入 $x$ 不被别人知道，但是代价是需要借助一个第三方服务器才能实现高效地计算。

回顾FSS的流程设计：
在这里插入图片描述
我们可以得出以下几点结论：

蓝色部分就是需要被设计的模块，其实就是两个模块，最后一个bool运算其实就是发送回数据拥有者，然后bool相加即可！
函数的分片可以预先进行且是一次性的！当函数的分片发送到多方中（分布式服务器）之后，使用共同的 $x$ （这是实时动态变化的且在线的）进行多方同时在分片中计算；
优化的重心在分片的构造上，这直接决定了Eval部分执行的效率。

因此，FSS所有的算法被顺其自然地设计为两个协议——KeyGen协议（用来隐藏函数且给函数分片）和Eval协议（执行高效计算）。

FSS的所有算法中，这部分的目的是为了给函数分片，这部分等价于生成（具体的生成原理和方法描述看后续）两个key，即 $k_0,k_1)$ ，这两个key是一个若干长度（后面会说具体的长度组成）的字符串发送给两方后，执行后续的Eval。

使用密钥key，即 $k_i,i \in \{0,1\}$ ，对公共输入 $x$ 逐个比特进行比较，然后将结果进行bool求和，此时就能得到最终的正确输出。

从协议的过程整体来看，对两方的服务器都隐藏了当前计算的函数（这得益于第三方服务器生成的随机数 $\alpha$ ，后续会知道这就是个函数偏移offset）；
各方原本持有的输入 $x$ 的分片也是会使用这个随机数 $\alpha$ 进行偏移，这样执行运算的时候获取到的输入值就是 $x+\alpha$ ，即真正的 $x$ 是被隐藏了的；
最后双方将运行的结果分片放到一起的时候，进行bool求和即可获得最终的运算结果；
后续的《【安全多方计算之FSS】通俗易懂理解函数秘密分享——FSS具体构造（二）》中将重点介绍FSS的协议细节，搞清楚FSS的具体原理，以及作者Boyle为什么使用校正词和一棵二叉树就可以实现函数分片，以至于将FSS的构想提升到哲学层面。