加法準同型暗号を使って乗算する

加法準同型暗号とは

以下のように暗号化したまま加法が可能な暗号。

$$
E(a) + E(b) = E(a + b)
$$

ただし、$E(a)$は$a$の暗号文。
加法準同型暗号としてはPaillier暗号などが有名。

Paillier暗号

1999年にPaillierによって発明された公開鍵暗号。こちらが詳しかった。
加法に加えて減法、定数倍もできる。

$$
E(a) - E(b) = E(a - b) \
n * E(a) = E(na)
$$

Paillier暗号による乗算

Pailler暗号は加法準同型暗号なので通常は乗算を行うことはできないが、以下の等式を用いて秘密鍵をもつBobとデータをやり取りすることでAliceは乗算結果を得ることができる。

$$
ab = (a+r_a)(b+r_b) - ar_b - br_a - r_ar_b
$$

1. Aliceは乱数$r_a, r_b$を生成し、$E(a+r_a), E(b+r_b)$を計算してBob送信する.
2. Bobは$E(a+r_a), E(b+r_b)$を復号し、$(a+r_a)(b+r_b)$を暗号化してAliceへ送信する.
3. Aliceは受け取った$E((a+r_a)(b+r_b))$から$ar_b, br_a,r_ar_b$を引いて$E(ab)$を得る.

$$
\begin{array}{ccc}
Alice & & Bob \
E(a), E(b), pk & & sk \
& \xrightarrow{E(a + r_a), E(b + r_b)} & \
& \xleftarrow{E((a + r_a)(b + r_b))} & \
\end{array}
$$

一連の操作において、Bobに$a, b$を知られることなくAliceは$ab$を得ている。

実装

Paillier暗号はこちらの実装を参考に少々手を加えた。

import random
from paillier import *

# 準備
sk, pk = generate_keypair(32)

a, b = 3, 5
print(f'(a, b) = ({a}, {b})')

enc_a = encrypt(pk, a)
enc_b = encrypt(pk, b)

print('***** Aliceの処理ここから *****') 
# a, bに乱数を加えてBobへ送信
ra = random.randrange(0, pk.n)
rb = random.randrange(0, pk.n)
print(f'ra = {ra}')
print(f'rb = {rb}')

enc_a_plus_ra = e_add_const(pk, enc_a, ra)
enc_b_plus_rb = e_add_const(pk, enc_b, rb)

print('***** Bobの処理ここから *****') 
# 復号して乗算した結果を暗号化してAliceへ
a_plus_ra = decrypt(sk, pk, enc_a_plus_ra)
b_plus_rb = decrypt(sk, pk, enc_b_plus_rb)

prod = a_plus_ra * b_plus_rb
print(f'prod = {prod}')

enc_prod = encrypt(pk, prod)

print('***** 再度Aliceの処理ここから *****') 
# Bobから受信したデータからa*r_b, b*r_a, r_a*r_bを引く
enc_arb = e_mul_const(pk, enc_a, rb)
enc_bra = e_mul_const(pk, enc_b, ra)
enc_rarb = encrypt(pk, ra * rb)

enc_result = e_sub(pk, enc_prod, enc_arb)
enc_result = e_sub(pk, enc_result, enc_bra)
enc_result = e_sub(pk, enc_result, enc_rarb)

print(decrypt(sk, pk, enc_result))

(a, b) = (3, 5)

***** Aliceの処理ここから *****
ra = 940245986
rb = 1030728560

***** Bobの処理ここから *****
prod = 969138398988975785

***** 再度Aliceの処理ここから *****
15