NFGen | 自动化非线性函数评估代码生成器

本文针对MPC下开销巨大的非线性函数计算，提出了NFGen工具包。NFGen利用离散分段多项式，自动化综合考虑后端MPC协议的开销、近似精度等指标，生成最优的近似多项式，并利用后端的MPC协议库进行计算（例如PrivPy，MP-SPDZ等）。相比于之前手动在MPC源码下直接编写近似多项式，NFGen在精度、性能等方面都有长足提升。

• 正确性与精度：为了效率考虑，目前大多数MPC协议还是需要将浮点数（FLP）转化为定点数（FXP）进行计算。该转化不仅会引起精度的损失，在一些极端的情况下会带来溢出等错误；
• 性能：更重要的，MPC协议的计算性能比对应的明文计算低好几个数量级，尤其是针对复杂的非线性函数；
• 泛化性：即便我们可以用MPC协议内置支持的一些基本操作实现很多非线性函数，但是有些复杂的函数比如等还是很难去实现；
• 可移植性：MPC协议底层技术多样，针对不同的场景硬件环境等各种权衡复杂。如何设计面向多样化场景的最优方案是个难题。

1. FXP下近似多项式的挑战：1）首先多项式需要满足FXP的值域和放缩限制，保证计算中间结果不溢出（上溢出、下溢出）；2）其次，FXP实际上是整数，寻找一个最优的多项式是一个NP-完全的整数规划问题。因此，本文需要寻找一个合理的近似。
2. 和的权衡：越大，则分段越多，因此需要的比较也越多；越大，则需要的乘法也越多。
   
   

1. 给定函数和系统配置文件NFD，NFGen首先在明文下计算函数得到候选定点数函数簇；
2. 进一步，根据MPC性能文件PPD从选取性能最优的函数；
3. 最后，利用生成代码模板OPPE，并生成后端MPC协议对应的代码。

;

2. 下溢出的情况则复杂一些：如果，那么存在。此时，令  ；否则当时，需要满足

。

最后具体算法如下：

1. 不能太大，以免上溢出，即；

 2.    是一个合法的FXP且。具体算法如下:

实验评估

往期推荐