\( \def\vector#1{\boldsymbol{#1}} \)

準同型暗号

Takami Torao #準同型暗号 #HE #FHE
  • このエントリーをはてなブックマークに追加

概要

準同型暗号 (homomorphic encryption; HE) は暗号化されたデータの演算によって復号化されたデータの演算を代用ができる暗号スキーム。演算結果は秘密鍵によって解読することができるが、演算を行うために秘密鍵による復号化を必要としない。準同型暗号を使用することにより、データの内容を秘匿したままクラウドのようなサードパーティの計算リソースを安全に利用することができる。

準同型暗号は一般向けの暗号技術ではなく、データサイズは何倍も大きくなり、また大きなオーバーヘッドを伴うため、暗号化されていない状態で非常に計算コストのかかる計算を準同型暗号で代用することは現実的ではない。

準同型写像

ある群 \(A\) から別の群 \(B\) に演算の関係を維持したまま準同型写像という。

実装スキーム

準同型暗号の概念は最初に [1] で紹介された。現実的に実装可能な準同型暗号スキームには以下のものがある。

BGV スキーム (Brakerski-Gentry-Vaikuntanathan)
[2] 他の二つより複雑だが計算効率は良い。整数のみの演算。
BFV スキーム (Brakerski / Fan-Vercauteren)
[3,4] CKKS と同等の計算効率。整数のみの演算。
CKKS スキーム (Cheon-Kim-Kim-Song)
[5] BFV と同等の計算効率。精度は限られるが複素数の演算が可能。

上記は全て完全準同型暗号 (つまり加算と乗算が可能) である。また格子ベースの暗号スキームであり量子耐性暗号と言われている。

TFHE

TFHE [6] (a fast fully homomorphic encryption scheme over the torus)

ビルドとインストール

cmake と g++ ≧ 5.2 または clang ≧ 3.8 の C++ コンパイラが必要。

$ git clone https://github.com/tfhe/tfhe.git
$ cd tfhe
$ make
$ make install

鍵生成

チュートリアルに従う。コンパイルは以下のように行う。

g++ [filename].cpp -o [output] -ltfhe-spqlios-fma -w

secret.keycloud.key (ともに 113,672,736B) が生成される。

#include <tfhe/tfhe.h>
#include <tfhe/tfhe_io.h>
#include <stdio.h>

// 秘密鍵と暗号演算用の鍵を作成
int main() {
    const int minimum_lambda = 110;
    TFheGateBootstrappingParameterSet* params = new_default_gate_bootstrapping_parameters(minimum_lambda);

    // 秘密鍵の作成
    uint32_t seed[] = { 314, 1592, 657 };
    tfhe_random_generator_setSeed(seed, 3);
    TFheGateBootstrappingSecretKeySet* secret_key = new_random_gate_bootstrapping_secret_keyset(params);

    // 後で使用するために秘密鍵をファイルに保存
    FILE* secret_key_file = fopen("secret.key", "wb");
    export_tfheGateBootstrappingSecretKeySet_toFile(secret_key_file, secret_key);
    fclose(secret_key_file);

    // 暗号演算用の鍵をファイルに保存 (暗号演算を行うクラウドベンダーに渡す想定)
    FILE* cloud_key = fopen("cloud.key", "wb");
    export_tfheGateBootstrappingCloudKeySet_toFile(cloud_key, &secret_key->cloud);
    fclose(cloud_key);

    delete_gate_bootstrapping_secret_keyset(secret_key);
    delete_gate_bootstrapping_parameters(params);
    return EXIT_SUCCESS;
}

暗号化

cloud.data (81,152B) が生成される。

#include <tfhe/tfhe.h>
#include <tfhe/tfhe_io.h>
#include <stdio.h>

int main() {
    // ファイルから秘密鍵を読み込み
    FILE* secret_key_file = fopen("secret.key", "r");
    TFheGateBootstrappingSecretKeySet* secret_key = new_tfheGateBootstrappingSecretKeySet_fromFile(secret_key_file);
    fclose(secret_key_file);

    // 必要であれば秘密鍵の持つパラメータを参照
    const TFheGateBootstrappingParameterSet* params = secret_key->params;

    // 2017 の 16 個の ciphertext を生成
    int16_t plaintext1 = 2017;
    LweSample* ciphertext1 = new_gate_bootstrapping_ciphertext_array(16, params);
    for (int i=0; i<16; i++) {
        bootsSymEncrypt(&ciphertext1[i], (plaintext1>>i)&1, secret_key);
    }

    // 42 の 16 個の ciphertext を生成
    int16_t plaintext2 = 42;
    LweSample* ciphertext2 = new_gate_bootstrapping_ciphertext_array(16, params);
    for (int i=0; i<16; i++) {
        bootsSymEncrypt(&ciphertext2[i], (plaintext2>>i)&1, secret_key);
    }

    printf("Hi there! Today, I will ask the cloud what is the minimum between %d and %d\n", plaintext1, plaintext2);

    // 2×16 個の ciphertext をファイルに保存 (暗号演算を行うクラウドに渡す)
    FILE* cloud_data = fopen("cloud.data", "wb");
    for (int i=0; i<16; i++){
        export_gate_bootstrapping_ciphertext_toFile(cloud_data, &ciphertext1[i], params);
    }
    for (int i=0; i<16; i++){
        export_gate_bootstrapping_ciphertext_toFile(cloud_data, &ciphertext2[i], params);
    }
    fclose(cloud_data);

    delete_gate_bootstrapping_ciphertext_array(16, ciphertext2);
    delete_gate_bootstrapping_ciphertext_array(16, ciphertext1);
    delete_gate_bootstrapping_secret_keyset(secret_key);
    return EXIT_SUCCESS;
}

暗号計算

処理時間 1.294 秒で answer.data (40,576B) が生成される。

#include <tfhe/tfhe.h>
#include <tfhe/tfhe_io.h>
#include <time.h>
#include <stdio.h>

static void compare_bit(LweSample* result, const LweSample* a, const LweSample* b, const LweSample* lsb_carry, LweSample* tmp, const TFheGateBootstrappingCloudKeySet* cloud_key);
static void minimum(LweSample* result, const LweSample* a, const LweSample* b, const int nb_bits, const TFheGateBootstrappingCloudKeySet* cloud_key);

int main() {
    // 暗号演算用の鍵を読み込み
    FILE* cloud_key_file = fopen("cloud.key", "rb");
    TFheGateBootstrappingCloudKeySet* cloud_key = new_tfheGateBootstrappingCloudKeySet_fromFile(cloud_key_file);
    fclose(cloud_key_file);

    // 必要であれば秘密鍵の持つパラメータを参照
    const TFheGateBootstrappingParameterSet* params = cloud_key->params;

    // ファイルから 2×16 個の ciphertext を読み込み
    LweSample* ciphertext1 = new_gate_bootstrapping_ciphertext_array(16, params);
    LweSample* ciphertext2 = new_gate_bootstrapping_ciphertext_array(16, params);
    FILE* cloud_data = fopen("cloud.data","rb");
    for (int i=0; i<16; i++){
        import_gate_bootstrapping_ciphertext_fromFile(cloud_data, &ciphertext1[i], params);
    }
    for (int i=0; i<16; i++){
        import_gate_bootstrapping_ciphertext_fromFile(cloud_data, &ciphertext2[i], params);
    }
    fclose(cloud_data);

    // いくつかの処理を行う: ここでは 2 つの値の最小値を計算する
    LweSample* result = new_gate_bootstrapping_ciphertext_array(16, params);
    clock_t begin = clock();
    minimum(result, ciphertext1, ciphertext2, 16, cloud_key);
    clock_t end = clock();
    printf("%f seconds\n", (double)(end - begin) / CLOCKS_PER_SEC);

    // 32 個の ciphertext をファイルに保存する
    FILE* answer_data = fopen("answer.data", "wb");
    for (int i=0; i<16; i++){
        export_gate_bootstrapping_ciphertext_toFile(answer_data, &result[i], params);
    }
    fclose(answer_data);

    delete_gate_bootstrapping_ciphertext_array(16, result);
    delete_gate_bootstrapping_ciphertext_array(16, ciphertext2);
    delete_gate_bootstrapping_ciphertext_array(16, ciphertext1);
    delete_gate_bootstrapping_cloud_keyset(cloud_key);
    return EXIT_SUCCESS;
}

// i 番目のビットを比較するために使用される elementary full comparator gate:
//   input: ai and bi the i-th bit of a and b
//          lsb_carry: the result of the comparison on the lowest bits
//   algo: if (a==b) return lsb_carry else return b
static void compare_bit(
    LweSample* result, const LweSample* a, const LweSample* b, const LweSample* lsb_carry, LweSample* tmp,
    const TFheGateBootstrappingCloudKeySet* cloud_key
) {
    bootsXNOR(tmp, a, b, cloud_key);
    bootsMUX(result, tmp, lsb_carry, a, cloud_key);
}

// 2 つの 16bit 値を比較し小さい方を result に設定する
static void minimum(
    LweSample* result, const LweSample* a, const LweSample* b, const int nb_bits,
    const TFheGateBootstrappingCloudKeySet* cloud_key
) {
    LweSample* tmps = new_gate_bootstrapping_ciphertext_array(2, cloud_key->params);

    // キャリーを 0 に初期化
    bootsCONSTANT(&tmps[0], 0, cloud_key);
    // elementary comparator gate を n 回実行
    for (int i=0; i<nb_bits; i++) {
        compare_bit(&tmps[0], &a[i], &b[i], &tmps[0], &tmps[1], cloud_key);
    }
    // tmps[0] が比較の結果: a が大きい場合 0、b が大きい場合 1
    // 小さい方を選択して result にコピーする
    for (int i=0; i<nb_bits; i++) {
        bootsMUX(&result[i], &tmps[0], &b[i], &a[i], cloud_key);
    }

    delete_gate_bootstrapping_ciphertext_array(2, tmps);
}

復号化

#include <tfhe/tfhe.h>
#include <tfhe/tfhe_io.h>
#include <stdio.h>

int main() {
    // ファイルから秘密鍵をロード
    FILE* secret_key = fopen("secret.key", "rb");
    TFheGateBootstrappingSecretKeySet* key = new_tfheGateBootstrappingSecretKeySet_fromFile(secret_key);
    fclose(secret_key);

    // 必要であれば秘密鍵の持つパラメータを参照
    const TFheGateBootstrappingParameterSet* params = key->params;

    // 結果から 16 個の chiphertext を読み出す準備
    LweSample* answer = new_gate_bootstrapping_ciphertext_array(16, params);

    // answer ファイルから 32 個の ciphertext を読み出し
    FILE* answer_data = fopen("answer.data", "rb");
    for (int i=0; i<16; i++){
        import_gate_bootstrapping_ciphertext_fromFile(answer_data, &answer[i], params);
    }
    fclose(answer_data);

    // 復号化し 16-bit プレーンテキストの答えを構築
    int16_t int_answer = 0;
    for (int i=0; i<16; i++) {
        int ai = bootsSymDecrypt(&answer[i], key);
        int_answer |= (ai<<i);
    }

    printf("And the result is: %d\n", int_answer);
    printf("I hope you remember what was the question!\n");

    delete_gate_bootstrapping_ciphertext_array(16, answer);
    delete_gate_bootstrapping_secret_keyset(key);
    return EXIT_SUCCESS;
}
And the result is: 42
I hope you remember what was the question!

Microsoft SEAL

Microsoft SEAL は C++ で実装されている準同型暗号のライブラリ。github.com/Microsoft/SEAL で OSS として公開されており MIT ライセンスで利用できる。

Linux / macOS

libseal のビルドには cmake 1.13 以上を使用する。Ubuntu 18.04 の apt-get install でインストールされた cmake はバージョンは 3.11.0 であるため cmake.org/download から最新版をインストールする必要がある。

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 18.04.4 LTS
Release:        18.04
Codename:       bionic

$ cmake --version
cmake version 3.16.5

SEAL の github リポジトリをクローンして cmake . && make を行うことで native/lib/libseal-3.4.a がビルドされる。

$ git clone https://github.com/microsoft/SEAL.git
Cloning into 'SEAL'...
remote: Enumerating objects: 7761, done.
...

$ cd SEAL/native/src
$ cmake .
-- The CXX compiler identification is GNU 7.5.0
-- The C compiler identification is GNU 7.5.0
...

$ make
Scanning dependencies of target seal
[  2%] Building CXX object CMakeFiles/seal.dir/seal/batchencoder.cpp.o
...
[100%] Linking CXX static library ".../git/SEAL/native/lib/libseal-3.4.a"
[100%] Built target seal

また native/example に用意されているサンプルも同様に cmake . && make でビルドすることができる。

$ bin/sealexamples
Microsoft SEAL version: 3.4.5
+---------------------------------------------------------+
| The following examples should be executed while reading |
| comments in associated files in native/examples/.       |
+---------------------------------------------------------+
| Examples                   | Source Files               |
+----------------------------+----------------------------+
| 1. BFV Basics              | 1_bfv_basics.cpp           |
| 2. Encoders                | 2_encoders.cpp             |
| 3. Levels                  | 3_levels.cpp               |
| 4. CKKS Basics             | 4_ckks_basics.cpp          |
| 5. Rotation                | 5_rotation.cpp             |
| 6. Performance Test        | 6_performance.cpp          |
+----------------------------+----------------------------+
[      0 MB] Total allocation from the memory pool

> Run example (1 ~ 6) or exit (0):

参考文献

  1. Ronald L. Rivest, R. L., Adleman, L., and Michael L. Dertouzos. ON DATA BANKS AND PRIVACY HOMOMORPHISMS, Foundations of Secure Computation, 169-180, 1978 Academic Press
  2. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping, ACM Transactions on Computation Theory 6.3, July 2014 Article No.13
  3. Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, In Advances in cryptology–crypto 2012 (pp. 868–886). Springer, Berlin, Heidelberg.
  4. Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption, IACR Cryptology ePrint Archive, 2012, 144.
  5. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pp.409–437. Springer 2017, Cham.
  6. I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully Homomorphic Encryptionover the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020).