準同型暗号

概要

準同型暗号 (homomorphic encryption; HE) は暗号化したデータを復号化せず演算することで、復号化により計算結果を得ることができる暗号スキーム。データの内容を秘匿したままクラウドのようなサードパーティの計算リソースを使用することができる。準同型暗号の概念は最初に [1] で紹介された。将来的にはデータを暗号化したまま解析や検索を行う技術への応用が期待されている。

Table of Contents

1. 概要
   1. 数学モデル
2. 完全準同型暗号
   1. LWE 格子暗号
   2. ブートストラッピング
   3. 利用可能な実装
3. TFHE
   1. ビルドとインストール
   2. 鍵生成
   3. 暗号化
   4. 暗号計算
   5. 復号化
4. Microsoft SEAL
   1. Linux / macOS
5. 参考文献

数学モデル

準同型暗号はある集合から別の集合へ代数構造を維持したまま変換する準同型写像に基づいている。写像 \(f\) を暗号化操作、\(x_1, x_2\) をそれぞれ平文の代数としたとき、ある演算 ⊛ に対して以下の関係が成り立つ。\[ f(x_1) ⊛ f(x_2) = f(x_1 ⊛ x_2) \] これは \(x_1,x_2\) を復号化しなくても \(x_1 ⊛ x_2\) の演算を行う事ができることを意味している。

1. 暗号化: \(x_1, x_2 \to f(x_1), f(x_2)\)
2. 演算: \(f(x_1) ⊛ f(x_2) = f(x_1 ⊛ x_2)\)
3. 復号化: \(f^{-1}(f(x_1 ⊛ x_2)) = x_1 ⊛ x_2\)

準同型暗号により可能な演算によって加法準同型暗号と乗法準同型暗号がある。

• 加法準同型暗号: \(f(x_1) + f(x_2) = f(x_1 + x_2)\)
• 乗法準同型暗号: \(f(x_1) \times f(x_2) = f(x_1 \times x_2)\)

加法と乗法の両方が可能な準同型暗号を完全準同型暗号 (FHE; fully homomorphic encryption) と呼ぶ。片方だけであれば離散対数に基づく ElGamal や素因数分解に基づく RSA といったよく知られた非対称鍵暗号を応用して行うことができる。

完全準同型暗号

LWE 格子暗号

完全準同型暗号は LWE 問題に基づく格子暗号を使ったスキームが存在する。LWE 問題に基づく格子暗号では、線形方程式が秘匿されたノイズ (誤差) を含むことでその計算複雑性が NP 困難となることを利用している。例えば加法準同型暗号 (\(\ref{lwe_add}\)) では、\(\vector{e}_1\), \(\vector{e}_2\) は暗号者自身が設置したものであるから \(\vector{e}_1+\vector{e}_2\) を除去し一般的な多元1次方程式の解法で \(\vector{s}_1+\vector{s}_2\) を算出することができる。\[ \begin{equation} \vector{x}_1 + \vector{x}_2 = (\vector{A} \cdot \vector{s}_1 + \vector{e}_1) + (\vector{A} \cdot \vector{s}_2 + \vector{e}_2) = \vector{A} \cdot (\vector{s}_1 + \vector{s}_2) + (\vector{e}_1 + \vector{e}_2) \label{lwe_add} \end{equation} \] 一方、乗法準同型暗号 (\(\ref{lwe_mul}\)) では \(\vector{s}_1, \vector{s}_2\) に対して \(\vector{e}_1,\vector{e}_2\) を十分小さくすればノイズ \(\vector{e}'\) が格子の "粗さ" による丸めで無視できることを利用する。\[ \begin{eqnarray} \vector{x}_1 \times \vector{x}_2 & = & (\vector{A} \cdot \vector{s}_1 + \vector{e}_1) \times (\vector{A} \cdot \vector{s}_2 + \vector{e}_2) = \vector{A} \cdot \vector{s}_1 \times \vector{A} \cdot \vector{s}_2 + \vector{e}' \label{lwe_mul} \\ \vector{e}' & = & (\vector{A} \cdot \vector{s}_1 \cdot \vector{e}_2 + \vector{A} \cdot \vector{s}_2 \cdot \vector{e}_1 + \vector{e}_1 \cdot \vector{e}_2) \nonumber \end{eqnarray} \]

ブートストラッピング

ノイズの大きさは暗号化直後に最小で、加法・乗法準同型暗号演算を繰り返すたびに累積する。最終的にこのノイズの増加がある閾値を超えると復号化時に正しい演算結果を得られなくなる。回避策として、ノイズの取りうる範囲から演算可能な回数を制限することができる。このように計算回数の制限を持つ完全準同型暗号を SFHE (somewhat fully homomorphic encryption) と呼ぶ。

ブートストラッピング (bootstrapping) [8] は準同型暗号の演算で暗号文に蓄積するノイズを削減し、任意の回数の計算を可能にする操作である。ただし計算量が極めて膨大であり、当初のアルゴリズムでは 1 回のブートストラッピングに数分から数秒、より改良された現在のアルゴリズムでも数百ミリ秒程度を必要とする。計算過程の中でどのタイミングでブートストラッピングを行うかで計算回数を減らすことができる。

利用可能な実装

現実的に実装可能な準同型暗号スキームには以下のものがある。

TFHE

[6] 論理回路を構成する。トーラス構造の格子を使用する FHE でブートストラップも高速。

BGV (Brakerski-Gentry-Vaikuntanathan)

[2] CKKS, BVF より複雑だが計算効率は良い。1つの整数か2つの小さな整数の演算が可能。

BFV (Brakerski / Fan-Vercauteren)

[3,4] CKKS と同等の計算効率。1つの整数か2つの小さな整数の演算が可能。

CKKS (Cheon-Kim-Kim-Song)

[5] BFV と同等の計算効率。精度は限られるが固定小数点演算と複素数の演算が可能。

上記は全て格子暗号による完全準同型暗号である。

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

TFHE

TFHE [6] (a fast fully homomorphic encryption scheme over the torus) は 10 個のバイナリゲート (AND, OR, XOR, NAND, NOR, etc.) と高速なブートストラップを実装する完全準同型暗号ライブラリ。

ビルドとインストール

TFHE ライブラリのビルドには cmake と g++ ≧ 5.2 または clang ≧ 3.8 の C++ コンパイラが必要。

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

鍵生成

以降はTFHE のチュートリアルに従って操作を行う。各ソースは以下のようにコンパイルすることができる (警告が気になる場合は -w オプションで抑制しても良い）。

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

まず暗号化/復号化のための秘密鍵と、暗号演算を行うための鍵を生成する。以下のコードの実行によってそれぞれ secret.key と cloud.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 Encryption over the Torus. In Journal of Cryptology, volume 33, pages 34–91 (2020).
7. David Wu, Dan Boneh. Somewhat (Practical) Homomorphic Encryption
8. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC ’09, pp. 169–178. ACM, 2009.