同态加密Hoisting Rotation介绍和OpenFHE示例

摘要

Hoisting在一个密文需要旋转多次的时候，可以预先计算公共的部分，从而加速整个旋转操作。
本文简要介绍RLWE同态加密的旋转（Rotation）操作和Hoisting的优化原理，然后给出如何在OpenFHE同态加密库中使用Hoisting Rotation。

密文旋转

RLWE同态密文旋转主要有下面三步：

1. 自同态：通过自同态将密文槽旋转，即计算$\varphi (ct)$；
2. 数值分解（break into digits）：将密文的系数用$\delta$进制表示$\varphi (ct)=\sum q_i{\delta }^i$。其中$\delta$是一个小的整数，$q_i$的系数小于$\delta$；
3. 密钥交换：将旋转后的密文的解密密钥$\varphi (sk)$，通过密钥交换，变为原来的密钥$sk$。

密文旋转的本质就是一个自同态映射$\varphi$。我们使用$ct$表示密文，那么旋转后的密文$c{t}_1=\varphi (ct)$. 这时的密文中的明文已经移到对应的位置了，但是解密密钥却变为了$\varphi (sk)$.

因此，第2、3步是为了将解密密钥重新切换为$sk$.

第2步的目的是降低密钥交换的噪声。

Hoisting Rotation

Hoisting Rotation 可以翻译成提升旋转，或者快速旋转。通过将多个旋转的公共部分计算，提到前面计算，降低整体的开销。为此，我们需要对上面的密文旋转步骤做调整。我们先计算第2步，然后再计算第1步，最后计算第3步：

1. 数值分解：首先对原来的密文分解$ct=\sum q_i^{\prime }{\delta }^i$；
2. 自同态：对分解后的密文进行自同态计算$\varphi (q_i^{\prime })$；
3. 密钥交换：使用$\varphi (q_i^{\prime })$进行密钥交换。

这里的正确性由下面两点保证：

• 自同态对加法和乘法具有分配律，即$\varphi ({\lambda }_{1}a+{\lambda }_{2}b)={\lambda }_1\varphi (a)+{\lambda }_2\varphi (b)$，其中${\lambda }_1,{\lambda }_2$是常数；
• 自同态不会明显增加环上多项式的范数，也就是，如果$q<\delta$，那么$\varphi (q)<\lambda \delta$，其中$\lambda$是一个与环相关的常数。

所以，我们有：
$\varphi (ct)=\varphi (\sum q_i^{\prime }{\delta }^i)=\sum \varphi (q_i^{\prime }){\delta }^i$.

并且，$\varphi (q_i^{\prime })$是的系数是小整数。

这样第一步对于所有的旋转步数来说，都是一样的，可以提到前面进行计算。

但是这里存在一个问题，就是原来的旋转的自同态只需要执行一次，而交换顺序后，自同态需要作用到每一个$q_i^{\prime }$。

所幸的是，多项式在大多数的密码学库都是采用的DCRT的形式表示（系数使用整数中国剩余定理分解，多项式使用多项式的中国剩余定理分解）。在这种表示下，自同态是非常快的。而数值分解需要进行多项式表示的转换，耗费的时间比较多。

因此，Hoisting Rotation可以加快整体的旋转。

OpenFHE代码示例

// OpenFHE example by zyf
#include<iostream>
#include<time.h>
#include <chrono>
#include "openfhe.h"

using namespace std;
using namespace lbcrypto;

// This example shows that how to rotation in CKKS,
// and how to use hoisting rot
int main(){
    // var for computation time
    chrono::high_resolution_clock::time_point time_start, time_end;
    chrono::microseconds time_diff;
    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetMultiplicativeDepth(2);
    parameters.SetScalingModSize(40);

    CryptoContext<DCRTPoly> cc=GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);

    usint cycOrder=cc->GetCyclotomicOrder();

    cout<<"The order of ring is "<<cycOrder<<endl;

    KeyPair<DCRTPoly> kp=cc->KeyGen();
    //just rot 1,2,3,4,5,6,7,8 steps
    cc->EvalRotateKeyGen(kp.secretKey,{1,2,3,4,5,6,7,8});

    size_t num=8;

    vector<double> vec_double={1,2,3,4,5,6,7,8};
    Plaintext p1=cc->MakeCKKSPackedPlaintext(vec_double);

    auto c0=cc->Encrypt(kp.publicKey,p1);
    vector<Ciphertext<DCRTPoly>> rotated_c(num);
    vector<Ciphertext<DCRTPoly>> hoist_rotated_c(num);
    cout<<"Rotation"<<endl;
    time_start=chrono::high_resolution_clock::now();
    for(size_t i=0;i<num;i++){
        rotated_c[i]=cc->EvalRotate(c0,i+1);
    }
    time_end=chrono::high_resolution_clock::now();
    time_diff = chrono::duration_cast<chrono::microseconds>(time_end - time_start);
    cout << "The time is [" << time_diff.count() << " microseconds]" << endl;

    Plaintext result;
    for(size_t i=0;i<num;i++){
        cc->Decrypt(kp.secretKey,rotated_c[i],&result);
        result->SetLength(num);
        cout<<result<<endl;
    }

    cout<<"Hoisting Rotation"<<endl;
    time_start=chrono::high_resolution_clock::now();
    auto pre_c=cc->EvalFastRotationPrecompute(c0);
    for(size_t i=0;i<num;i++){
        hoist_rotated_c[i]=cc->EvalFastRotation(c0,i+1,cycOrder,pre_c);
    }
    time_end=chrono::high_resolution_clock::now();
    time_diff = chrono::duration_cast<chrono::microseconds>(time_end - time_start);
    cout << "The time is [" << time_diff.count() << " microseconds]" << endl;

    for(size_t i=0;i<num;i++){
        cc->Decrypt(kp.secretKey,rotated_c[i],&result);
        result->SetLength(num);
        cout<<result<<endl;
    }

}

在我的机器上，普通的旋转8次，需要93613 microseconds，而Hoisting Rotation需要60798 microseconds。

原文地址：https://blog.csdn.net/watqw/article/details/142413056

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！