準同型暗号PaillierをPythonで実装と処理速度検証

# はじめに

プライバシー保護のための準同型暗号技術について、一番有名なPaillier暗号をPythonでの実装例と、暗号化キーの長さによって処理速度がどう変更するのかの検証を行いたいです。

準同型暗号に関する説明は今回割愛します。

# 実装例

## 初期設定

```python
from phe import paillier

# キーペア作成
public_key, private_key = paillier.generate_paillier_keypair()

# コンスタント2つ作成
num1 = 15
num2 = 20
```

## 暗号化

```python
encrypted_num1 = public_key.encrypt(num1)
encrypted_num2 = public_key.encrypt(num2)

print(f"暗号化した num1: {encrypted_num1.ciphertext()}")
# 140362034439846807867856938689313166233670963779...

print(f"暗号化した num2: {encrypted_num2.ciphertext()}")
# 150286860806309438164949437987344826383124111270...
```

暗号化した数字列は長過ぎるので、一部だけ記載します。

## 加算

```python
encrypted_sum = encrypted_num1 + encrypted_num2
decrypted_sum = private_key.decrypt(encrypted_sum)

print(f"暗号化した sum: {encrypted_sum.ciphertext()}")
# 10325979146656833486860853394641346236573093185...

print(f"復号化した sum: {decrypted_sum}")
# 35
```

これで加算の整合性が確認できました。

## 掛算

```python
scalar = 3

encrypted_product = encrypted_num1 * scalar
decrypted_product = private_key.decrypt(encrypted_product)

print(f"暗号化した product: {encrypted_product.ciphertext()}")
# 13926595952070523528972674386197829544024007504...

print(f"復号化した product: {decrypted_product}")
# 45
```

これで掛算の整合性が確認できました。

# 処理速度

準同型暗号に関する一番気になるのはやはり処理のスピードなので、今回はColab環境で暗号化キーの長さによって処理速度の変動を検証します。

検証するのは、1,000個ランダムの数字の加算と掛算です。

## 検証ロジック

```python
import random
import time
import phe.paillier as paillier


def bench_encrypt(pubkey, nums):
    for num in nums:
        pubkey.encrypt(num)


def bench_decrypt(prikey, nums):
    for num in nums:
        prikey.decrypt(num)


def bench_add(nums1, nums2):
    for num1, num2 in zip(nums1, nums2):
        num1 + num2


def bench_mul(nums1, nums2):
    for num1, num2 in zip(nums1, nums2):
        num1 * num2


def time_method(method, *args):
    start = time.time()
    method(*args)
    return time.time() - start


def bench_time(test_size, key_size=128):
    pubkey, prikey = paillier.generate_paillier_keypair(n_length=key_size)
    nums1 = [random.random() for _ in range(test_size)]
    nums2 = [random.random() for _ in range(test_size)]
    nums1_enc = [pubkey.encrypt(n) for n in nums1]
    nums2_enc = [pubkey.encrypt(n) for n in nums2]
    ones = [1.0 for _ in range(test_size)]

    times = [
        time_method(bench_encrypt, pubkey, nums1),
        time_method(bench_decrypt, prikey, nums1_enc),
        time_method(bench_add, nums1_enc, nums2_enc),
        time_method(bench_mul, nums1_enc, nums2)
    ]
    times = [t / test_size for t in times]
    ops = [int(1.0 / t) for t in times]
    return

key_sizes = [128, 256, 512, 1024, 2048]
for key_size in key_sizes:
    bench_time(1000, key_size)
```

## 検証結果

|  | 128 bits | 256 bits | 512 bits | 1024 bits | 2048 bits |
|-----------|----------|-----------|-----------|------------|------------|
| 暗号化 (s) | 0.000701 | 0.000761 | 0.003652 | 0.018408 | 0.121616 |
| 暗号化 (ops/s) | 1427 | 1314 | 273 | 54 | 8 |
| 復号化 (s) | 0.000322 | 0.000399 | 0.001486 | 0.005362 | 0.034731 |
| 復号化 (ops/s) | 3108 | 2509 | 672 | 186 | 28 |
| 加算 (s) | 0.000022 | 0.000013 | 0.000021 | 0.000029 | 0.000080 |
| 加算 (ops/s) | 44776 | 74856 | 47155 | 34813 | 12430 |
| 掛算 (s) | 0.000116 | 0.000191 | 0.000525 | 0.001092 | 0.003807 |
| 掛算 (ops/s) | 8635 | 5245 | 1905 | 915 | 262 |

特に掛算の場合は、暗号化キーの長さによって、処理速度がかなり落ちることが確認できました。