SEAL全同态加密开源库(七) rns剩余数系统-源码解析

2021SC@SDUSC

2021-11-14

前言

这是SEAL开源库代码分析报告第六篇，本篇将分析util文件夹中的rns.h和rns.cpp，也即剩余数系统。

理论知识补充

推荐一篇很好的初学者入门博客，陈志罡教授写的：科学网—整数上全同态加密方案分析（1）–献给全同态加密的初学者 - 陈智罡的博文 (sciencenet.cn)

本期的理论知识补充，我们介绍RNS，剩余数系统。

剩余数表示系统（RNS，residue number system）是一种用较少的数表示较多的数的表示系统。RNS可显著提高信号处理应用中某些算法密集型场景的算法速度。此外，RNS也是研究快速算法极限理论的一个工具。

可能上面的看起来有些困难，这里举个例子，帮助理解。

1500年前的一位古代中国学者写下了这样一个问题：“已知三个数分别除以7、5、2得到的余数是2、3、2，试问这三个数分别是多少？”这可能是历史上第一个使用多剩余数表示的数字。这个问题的本质上是要将 模 (7|5|3) 的剩余数系统 上表示的数 (2|3|2) 转换为其对应的标准十进制形式。用RNS表示，x=(2|3|2)RNS(7|5|2).

对于我们的全同态加密而言，不难看出，其可以应用于用来进行大整数表示以及运算。

rns.h源码解析

首先是RNSBase类。

构造器如下：

RNSBase(const std::vector<Modulus> &rnsbase, MemoryPoolHandle pool);

            RNSBase(RNSBase &&source) = default;

            RNSBase(const RNSBase &copy, MemoryPoolHandle pool);

            RNSBase(const RNSBase &copy) : RNSBase(copy, copy.pool_)
            {}

&operator=和&operator[]重构了运算符=和[]，比较简单。

剩下的大多为布尔函数，结合rns.cpp分析即可。

然后是BaseConverter类，实现基于base基数的转换。

构造器如下：除了常规的线程池，传入了两个前面提到的RNSBase类的引用，在其中实现了rns.cpp的初始化操作。

BaseConverter(const RNSBase &ibase, const RNSBase &obase, MemoryPoolHandle pool)
                : pool_(std::move(pool)), ibase_(ibase, pool_), obase_(obase, pool_)
            {
                if (!pool_)
                {
                    throw std::invalid_argument("pool is uninitialized");
                }

                initialize();
            }

然后是一堆返回size和引用的函数，没有分析的必要。

最后是RNSTool类。

divide_and_round_q_last_ntt_inplace函数借助了前文提到的NTT算法，其中提到扩展的基数必须支持NTT算法，否则报错。

最实用的部分在下面，实现各种求余数的操作。其具体的形式都在注释中给出了。

// Base converter: q --> B_sk
            Pointer<BaseConverter> base_q_to_Bsk_conv_;

            // Base converter: q --> {m_tilde}
            Pointer<BaseConverter> base_q_to_m_tilde_conv_;

            // Base converter: B --> q
            Pointer<BaseConverter> base_B_to_q_conv_;

            // Base converter: B --> {m_sk}
            Pointer<BaseConverter> base_B_to_m_sk_conv_;

            // Base converter: q --> {t, gamma}
            Pointer<BaseConverter> base_q_to_t_gamma_conv_;

            // prod(q)^(-1) mod Bsk
            Pointer<MultiplyUIntModOperand> inv_prod_q_mod_Bsk_;

            // prod(q)^(-1) mod m_tilde
            MultiplyUIntModOperand neg_inv_prod_q_mod_m_tilde_;

            // prod(B)^(-1) mod m_sk
            MultiplyUIntModOperand inv_prod_B_mod_m_sk_;

            // gamma^(-1) mod t
            MultiplyUIntModOperand inv_gamma_mod_t_;

            // prod(B) mod q
            Pointer<std::uint64_t> prod_B_mod_q_;

            // m_tilde^(-1) mod Bsk
            Pointer<MultiplyUIntModOperand> inv_m_tilde_mod_Bsk_;

            // prod(q) mod Bsk
            Pointer<std::uint64_t> prod_q_mod_Bsk_;

            // -prod(q)^(-1) mod {t, gamma}
            Pointer<MultiplyUIntModOperand> neg_inv_q_mod_t_gamma_;

            // prod({t, gamma}) mod q
            Pointer<MultiplyUIntModOperand> prod_t_gamma_mod_q_;