网页美工实训心得_photoshop抠图_资源最全的网盘搜索引擎_saascrm国内免费pdf

摘要

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 timechrono::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 stepscc->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。