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

はじめに

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

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

実装例

初期設定

from phe import paillier

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

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

暗号化

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...

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

加算

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

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

掛算

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個ランダムの数字の加算と掛算です。

検証ロジック

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

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