OpenFHE チュートリアル：　CKKS形式で演算＋近似演算＋ブートストラップの組み合わせにチャレンジしてみたかった。

**@kenmaro**です。
普段は主に**秘密計算、準同型暗号などの記事について投稿しています**。
秘密計算に関連するまとめの記事に関しては以下をご覧ください。

> - [秘密計算エンジニアを始めて２年半が経った。](https://qiita.com/kenmaro/items/48059dd60f79e80f5ef8)
> - [秘密計算エンジニアを始めて3年が経った。](https://qiita.com/kenmaro/items/a1d90a074d552b7bf886)


## 概要

以前の記事

https://qiita.com/kenmaro/items/de53308b2c964f7469b0

でご紹介した、格子暗号ベースの準同型暗号のこれからのデファクトスタンダードになりそうな
ライブラリ、OpenFHE

https://www.openfhe.org/

について、チュートリアルを触ってみました。

今までわたしはMicrosoft SEALライブラリを使って、CKKS形式の暗号を使って秘密計算の実装を行うことが多かったのですが、

OpenFHEに搭載されている魅力的な機能や使用感について、

- CKKS形式のブートストラップ手法がどれくらいの速度で実行できるのか
- 精度はどのくらいなのか
- ライブラリとしての使いやすさはどんな感じなのか
- CKKS形式のThreshold 暗号はどのように使うのか
- CKKS形式のPRE（プロキシ再暗号化）はどのように使用するのか
- ブートストラップ手法を用いて簡単なアプリケーションを作ってみる


について実際に自分でチュートリアルを作り、実行してみることにしました。
内容としては結構大きくなりそうだったので、今回はまず

- CKKS形式のブートストラップ手法がどれくらいの速度で実行できるのか
- 精度はどのくらいなのか

この二つについて、準同型演算とブートストラップを混ぜて回路を構成する形で、
自分でチュートリアルコード＋アルファの形でいろいろ実行してみましたので、
その結果やチュートリアルコードを公開しようと思います。


また、今回のコードは全てCKKS形式のみを試していますので、他の形式についてはまだ試していません。

## ブートストラップを複数回実行した時の演算時間と精度について

暗号自身に対して、１０回ブートストラップをかけた時の実行時間と精度について検証しました。

### 検証プログラム

```mytest_eval_many_bs.cpp
#define PROFILE
#include "openfhe.h"
#include "stdio.h"

using namespace lbcrypto;
using namespace std;

using namespace std::chrono;
inline double get_time_msec(void) {
    return static_cast<double>(duration_cast<nanoseconds>(steady_clock::now().time_since_epoch()).count()) / 1000000;
}

void SimpleBootstrapExample();

int main(int argc, char* argv[]) {
    SimpleBootstrapExample();
}

void SimpleBootstrapExample() {
    CCParams<CryptoContextCKKSRNS> parameters;
    SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 12);

#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDAUTO;
    usint dcrtBits               = 78;
    usint firstMod               = 89;
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60;
#endif

    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetFirstModSize(firstMod);

    std::vector<uint32_t> levelBudget = {4, 4};
    uint32_t approxBootstrapDepth     = 8;

    uint32_t levelsUsedBeforeBootstrap = 12;
    usint depth =
        levelsUsedBeforeBootstrap + FHECKKSRNS::GetBootstrapDepth(approxBootstrapDepth, levelBudget, secretKeyDist);
    parameters.SetMultiplicativeDepth(depth);

    printf("this is my depth %d\n", depth);

    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

    cryptoContext->Enable(PKE);
    cryptoContext->Enable(KEYSWITCH);
    cryptoContext->Enable(LEVELEDSHE);
    cryptoContext->Enable(ADVANCEDSHE);
    cryptoContext->Enable(FHE);

    usint ringDim = cryptoContext->GetRingDimension();
    // This is the maximum number of slots that can be used for full packing.
    usint numSlots = ringDim / 2;
    std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl << std::endl;

    cryptoContext->EvalBootstrapSetup(levelBudget);

    auto keyPair = cryptoContext->KeyGen();
    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
    cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);

    // Making plaintext vector
    std::vector<double> x;
    for (int i = 0; i < 10; i++) {
        x.push_back(i - 5);
    }
    size_t encodedLength = x.size();

    Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, 0);

    ptxt->SetLength(encodedLength);
    std::cout << "Input: " << ptxt << std::endl;

    // Encryption
    Ciphertext<DCRTPoly> c = cryptoContext->Encrypt(keyPair.publicKey, ptxt);

    double start = get_time_msec();

    for (int i = 0; i < 10; i++) {
        // Bootstrapping
        c = cryptoContext->EvalBootstrap(c);
        // Decryption
        Plaintext res_c;
        cryptoContext->Decrypt(keyPair.secretKey, c, &res_c);
        res_c->SetLength(encodedLength);
        std::cout << "res_c\n\t" << res_c << std::endl;
    }

    double end = get_time_msec();

    printf("total_time: %f\n", end-start);
}

```

### 実行結果

```bash
Input: (-5, -4, -3, -2, -1, 0, 1, 2, 3, 4,  ... ); Estimated precision: 59 bits

res_c
	(-5, -4, -3, -1.99999, -1.00001, -2.80521e-06, 1, 2, 3, 4,  ... ); Estimated precision: 18 bits

res_c
	(-5, -4, -3, -1.99999, -1.00001, -4.60478e-06, 1.00001, 2, 3, 4,  ... ); Estimated precision: 17 bits

res_c
	(-4.99999, -4.00001, -3, -1.99999, -0.999993, 2.26885e-06, 1.00001, 2, 3.00001, 3.99999,  ... ); Estimated precision: 17 bits

res_c
	(-4.99999, -4.00001, -3, -2, -1, 2.47069e-06, 1.00001, 2, 3, 4,  ... ); Estimated precision: 17 bits

res_c
	(-4.99999, -4.00001, -3, -2, -0.999993, -1.41384e-05, 0.999996, 1.99999, 3.00001, 3.99999,  ... ); Estimated precision: 17 bits

res_c
	(-4.99999, -4.00001, -3, -1.99999, -0.999995, -6.49506e-06, 0.999999, 2, 3, 4,  ... ); Estimated precision: 17 bits

res_c
	(-4.99997, -4.00001, -2.99999, -1.99999, -0.999988, -4.03381e-06, 0.999996, 1.99998, 3, 3.99998,  ... ); Estimated precision: 17 bits

res_c
	(-4.99998, -4.00002, -3, -1.99998, -1.00001, -8.26868e-06, 1, 1.99999, 3.00001, 4,  ... ); Estimated precision: 16 bits

res_c
	(-4.99999, -4.00001, -3.00001, -2, -0.999975, 1.9953e-06, 0.999987, 1.99998, 3, 3.99999,  ... ); Estimated precision: 16 bits

res_c
	(-4.99999, -4.00001, -3.00001, -1.99999, -0.999984, -3.20151e-06, 1, 2, 3, 4,  ... ); Estimated precision: 16 bits

total_time: 18109.998497
```

結果は、約１６ビット程度の精度は保ちつつ、ブートストラップを実行できている。
ブートストラップ１回の実行速度は（検証パラメータの下で）約1.8秒で実行できている。

TFHEをずっと最近触っていたのと比べると、圧倒的に精度がよく、
想像していたよりもかなり早いという結果になりました、、！


## 準同型演算とブートストラップを組み合わせてみる

次は、準同型演算（加算、乗算）とブートストラップを組み合わせて演算できるか、
簡単に検証してみます。

### 検証プログラム

```mytest_eval_then_bs.cpp
#define PROFILE

#include "openfhe.h"

#include "stdio.h"

using namespace lbcrypto;
using namespace std;

void SimpleBootstrapExample();

int main(int argc, char* argv[]) {
    SimpleBootstrapExample();
}

void SimpleBootstrapExample() {
    CCParams<CryptoContextCKKSRNS> parameters;
    SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 12);
#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDAUTO;
    usint dcrtBits               = 78;
    usint firstMod               = 89;
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60;
#endif

    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetFirstModSize(firstMod);

    std::vector<uint32_t> levelBudget = {4, 4};
    uint32_t approxBootstrapDepth     = 8;

    uint32_t levelsUsedBeforeBootstrap = 12;
    usint depth =
        levelsUsedBeforeBootstrap + FHECKKSRNS::GetBootstrapDepth(approxBootstrapDepth, levelBudget, secretKeyDist);
    parameters.SetMultiplicativeDepth(depth);

    printf("this is my depth %d\n", depth);

    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

    cryptoContext->Enable(PKE);
    cryptoContext->Enable(KEYSWITCH);
    cryptoContext->Enable(LEVELEDSHE);
    cryptoContext->Enable(ADVANCEDSHE);
    cryptoContext->Enable(FHE);

    usint ringDim = cryptoContext->GetRingDimension();
    // This is the maximum number of slots that can be used for full packing.
    usint numSlots = ringDim / 2;
    std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl << std::endl;

    cryptoContext->EvalBootstrapSetup(levelBudget);

    auto keyPair = cryptoContext->KeyGen();
    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
    cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);

    // Making plaintext vector
    std::vector<double> x;
    for (int i = 0; i < 10; i++) {
        x.push_back(i);
    }
    size_t encodedLength = x.size();

    Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, 0);

    ptxt->SetLength(encodedLength);
    std::cout << "Input: " << ptxt << std::endl;

    // Encryption
    Ciphertext<DCRTPoly> c = cryptoContext->Encrypt(keyPair.publicKey, ptxt);

    // Evaluation
    Ciphertext<DCRTPoly> c_add = cryptoContext->EvalAdd(c, c);
    Ciphertext<DCRTPoly> c_mul = cryptoContext->EvalMultAndRelinearize(c, c);

    // Bootstrapping
    auto pbs_c     = cryptoContext->EvalBootstrap(c);
    auto pbs_c_add = cryptoContext->EvalBootstrap(c_add);
    auto pbs_c_mul = cryptoContext->EvalBootstrap(c_mul);

    std::cout << "level remaind pbs_c: " << depth - pbs_c->GetLevel() << std::endl << std::endl;
    std::cout << "level remaind pbs_c_add: " << depth - pbs_c_add->GetLevel() << std::endl << std::endl;
    std::cout << "level remaind pbs_c_mul: " << depth - pbs_c_mul->GetLevel() << std::endl << std::endl;

    // Decryption
    Plaintext res_pbs_c;
    cryptoContext->Decrypt(keyPair.secretKey, pbs_c, &res_pbs_c);
    res_pbs_c->SetLength(encodedLength);
    std::cout << "res_pbs_c\n\t" << res_pbs_c << std::endl;

    Plaintext res_pbs_c_add;
    cryptoContext->Decrypt(keyPair.secretKey, pbs_c_add, &res_pbs_c_add);
    res_pbs_c_add->SetLength(encodedLength);
    std::cout << "res_pbs_c_add\n\t" << res_pbs_c_add << std::endl;

    Plaintext res_pbs_c_mul;
    cryptoContext->Decrypt(keyPair.secretKey, pbs_c_mul, &res_pbs_c_mul);
    res_pbs_c_mul->SetLength(encodedLength);
    std::cout << "res_pbs_c_mul\n\t" << res_pbs_c_mul << std::endl;
}

```

### 実行結果

```bash
Input: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9,  ... ); Estimated precision: 59 bits

level remaind pbs_c: 12

level remaind pbs_c_add: 12

level remaind pbs_c_mul: 12

res_pbs_c
	(-6.51086e-06, 1, 2.00001, 3, 3.99999, 5, 6, 7, 7.99999, 8.99999,  ... ); Estimated precision: 18 bits

res_pbs_c_add
	(4.6128e-06, 2, 3.99999, 6, 8, 10, 12, 14, 16, 18,  ... ); Estimated precision: 18 bits

res_pbs_c_mul
	(-2.40522e-06, 0.999998, 4, 9, 16, 25, 36, 49, 64, 81,  ... ); Estimated precision: 18 bits
```

問題なく実行できており、精度もCKKSの普通の演算と大差なく実行できています、
素晴らしいです。

## 近似形式の非線形演算とブートストラップを組み合わせてみる

最後に、近似式（チェビシェフ近似）に基づいた関数を実行し、その演算とブートストラップを組み合わせてみます。
今回は近似の対象として、ReLU関数を定義域にしたがって近似しています。
この近似対象は自分で関数をカスタマイズできるので、どんな関数でも大丈夫です。
TFHEのPBS経由のLUTとある意味同じ使用感で実装できます。

また、近似関数実行にかかる時間も計測してみます。


### 検証プログラム

```mytest_eval_approx_then_ps.cpp
#define PROFILE

#include "openfhe.h"

#include "stdio.h"

using namespace lbcrypto;
using namespace std;

using namespace std::chrono;
inline double get_time_msec(void) {
    return static_cast<double>(duration_cast<nanoseconds>(steady_clock::now().time_since_epoch()).count()) / 1000000;
}

void SimpleBootstrapExample();

double relu(double x) {
    if (x >= 0) {
        return x;
    }
    else {
        return 0;
    }
}

int main(int argc, char* argv[]) {
    SimpleBootstrapExample();
}

void SimpleBootstrapExample() {
    CCParams<CryptoContextCKKSRNS> parameters;
    SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
    parameters.SetSecretKeyDist(secretKeyDist);
    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 12);

#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDAUTO;
    usint dcrtBits               = 78;
    usint firstMod               = 89;
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60;
#endif

    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetFirstModSize(firstMod);

    std::vector<uint32_t> levelBudget = {4, 4};
    uint32_t approxBootstrapDepth     = 8;

    uint32_t levelsUsedBeforeBootstrap = 12;
    usint depth =
        levelsUsedBeforeBootstrap + FHECKKSRNS::GetBootstrapDepth(approxBootstrapDepth, levelBudget, secretKeyDist);
    parameters.SetMultiplicativeDepth(depth);

    printf("this is my depth %d\n", depth);

    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

    cryptoContext->Enable(PKE);
    cryptoContext->Enable(KEYSWITCH);
    cryptoContext->Enable(LEVELEDSHE);
    cryptoContext->Enable(ADVANCEDSHE);
    cryptoContext->Enable(FHE);

    usint ringDim = cryptoContext->GetRingDimension();
    // This is the maximum number of slots that can be used for full packing.
    usint numSlots = ringDim / 2;
    std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl << std::endl;

    cryptoContext->EvalBootstrapSetup(levelBudget);

    auto keyPair = cryptoContext->KeyGen();
    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
    cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);

    // Making plaintext vector
    std::vector<double> x;
    for (int i = 0; i < 10; i++) {
        x.push_back(i - 5);
    }
    size_t encodedLength = x.size();

    Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, 0);

    ptxt->SetLength(encodedLength);
    std::cout << "Input: " << ptxt << std::endl;

    // Encryption
    Ciphertext<DCRTPoly> c = cryptoContext->Encrypt(keyPair.publicKey, ptxt);

    // relu
    double start = get_time_msec();
    auto c_relu  = cryptoContext->EvalChebyshevFunction(relu, c, -10, 10, 50);
    double end   = get_time_msec();

    // Bootstrapping
    auto pbs_c = cryptoContext->EvalBootstrap(c);

    auto pbs_c_relu = cryptoContext->EvalBootstrap(c_relu);

    std::cout << "level remaind pbs_c: " << depth - pbs_c->GetLevel() << std::endl << std::endl;
    std::cout << "level remaind pbs_c_relu: " << depth - pbs_c_relu->GetLevel() << std::endl << std::endl;

    // Decryption
    Plaintext res_pbs_c;
    cryptoContext->Decrypt(keyPair.secretKey, pbs_c, &res_pbs_c);
    res_pbs_c->SetLength(encodedLength);
    std::cout << "res_pbs_c\n\t" << res_pbs_c << std::endl;

    Plaintext res_pbs_c_relu;
    cryptoContext->Decrypt(keyPair.secretKey, pbs_c_relu, &res_pbs_c_relu);
    res_pbs_c_relu->SetLength(encodedLength);
    std::cout << "res_pbs_c_relu\n\t" << res_pbs_c_relu << std::endl;

    printf("approx_time: %f\n", end - start);
}

```

### 実行結果

```bash
res_pbs_c
	(-5, -4, -3.00001, -2, -1, -1.703e-07, 1, 2, 3, 4,  ... ); Estimated precision: 18 bits

res_pbs_c_relu
	(0.000196051, -9.39667e-05, -0.00093034, -0.00178729, 0.00212488, 0.100044, 1.00212, 1.99821, 2.99906, 3.99991,  ... ); Estimated precision: 18 bits

approx_time: 652.076170
```

結論としては、ReLU関数が結構いい精度で近似できているということ、
実行時間も１回の近似演算で0.6秒くらいというかなり凄い結果になりました。

私がSEALライブラリを使ってCKKS形式でテイラーやチェビシェフ近似を実装した時よりかなり高速な結果となったので、
どこに違いがあるのか、パラメータはこれで大丈夫なのか、という疑問が少しありますが、精査してみようと思います。
結果だけみると、かなり使えるな、という結果になりました！


## まとめ

今回は、以前の記事で言及したOpenFHEというライブラリについて、
CKKS形式の枠組みの中でいくつか試してみたかったことを、
チュートリアルコードの拡張という形で試してみました。

私個人の意見として、精度、速度ともに、これは使えるぞ、、？
という結果になりました。

暗号パラメータに関してはこのパラメータで本システムにおける実装ができるかどうかという精査は必要ですが、パラメータについてもセキュリティビットを指定するような実装が可能になっているので、
そこの検証もかなり楽にできるようになっています。


次回以降で、今回は言及できなかった

- CKKS形式のThreshold 暗号はどのように使うのか
- CKKS形式のPRE（プロキシ再暗号化）はどのように使用するのか
- ブートストラップ手法を用いて簡単なアプリケーションを作ってみる

の３つについてやってみようと思います。

準同型暗号界隈、面白くなってきました。



今回はこの辺で。


@kenmaro