LWEによる暗号化では加法準同型性があります。 ここでは平文空間が \(\{0,...,7\}\) での暗号化・加法準同型性について、Pythonで実装して検証していきます。 \(\gdef\Z{\mathbb{Z}} \gdef\vec#1{\textbf{#1}}\)
まず、前の記事 では平文空間が \(\{0,1\}\) のときの暗号化をしましたが、加法準同型性の検証をするには面白くないので、平文空間が \(\{0,1,...,7\}\) での暗号化を考えます。 定義は Fully Homomorphic Encryption – CSE 206A: Lattice Algorithms and Applications, Fall 2017 を参考にしました。
-
LWE暗号化処理
- 秘密鍵 $\vec{s} \in \Z_q^n$ をランダムに選ぶ。
-
暗号化 : 秘密鍵 $\vec{s}$, 平文 \(m \in \{0,1,...,7\}\), ランダムに選んだ値 $\vec{a} \leftarrow \Z_q^n$, 誤差 $e \leftarrow \chi$ を入力し、暗号文を出力する。
\[\mathrm{LWE}_s(m) = [\vec{a}^T\!,\, \vec{a}^T \vec{s} + e + m(q/8)]\] -
復号 : 秘密鍵 $\vec{s}$ と暗号文 $\vec{c}^T = [\vec{a}^T, b]$ を入力し、$\vec{c}^T \bar{s} = \vec{c}^T (-s, 1)$ を一番近い $q/8$ の倍数に丸め込み、その倍数を出力する。
\[\mathrm{LWE}_s^{-1}(\vec{c}^T) = \lfloor (8/q)((q/16) + \vec{c}^T \bar{s}) \rfloor\]
復号について、平文空間のサイズが $2$ で、平文空間が \(\{0,1\}\) のときは、復号の処理で次の条件を満たすときは平文が「1」としていました。
\[\left\lfloor\frac{q}{4}\right\rfloor < p < 3\left\lfloor\frac{q}{4}\right\rfloor\]一般に、平文空間のサイズが $n$ となると、$j$ 番目の平文が「$i$」\((i \in \{0,...,n-1\})\) である条件は次のようになります（マイナスになる部分は $\mathrm{mod}\,q$ でプラス側に繋がっています）。
\[(2i-1)\left\lfloor\frac{q}{2n}\right\rfloor < p_j < (2i+1)\left\lfloor\frac{q}{2n}\right\rfloor\]注意点として、演算を繰り返すと誤差が大きくなります。そして誤差が $q/n$ を超えると、正しく復号できなくなります。
平文空間のサイズが $8$ のときをPythonでプログラムにすると次のようになります。
import numpy as np
n = 128 # 格子の次元
q = 4049 # 法とする素数
A = np.random.randint(q, size=(n, n))
alpha = 6.0 # 誤差分布のパラメータ
MESSAGE_SPACE_SIZE = 8
def randint_from_gaussian(size):
sigma = alpha / np.sqrt(2 * np.pi)
x = np.random.normal(0, sigma, size)
return np.rint(x)
def encrypt(plaintext, T):
r = randint_from_gaussian(size=n)
C1 = r.dot(A) % q
M = (q+1)/MESSAGE_SPACE_SIZE * plaintext
C2 = (r.dot(T) - M) % q
return C1, C2
def decrypt(ciphertext, s):
C1, C2 = ciphertext
p = (C1.dot(s) - C2) % q
div = MESSAGE_SPACE_SIZE * 2
for i in range(1, MESSAGE_SPACE_SIZE):
before = i * 2 - 1
after = i * 2 + 1
if before*(q+1)/div < p < after*(q+1)/div:
return i
return 0
print('lattice basis: A = \n', A)
print()
# 秘密鍵と公開鍵の設定
s = np.random.randint(q, size=n)
G = A.dot(s) % q
e = randint_from_gaussian(size=n)
T = (G + e) % q
print('[+] secret key')
print('s =\n', s)
print('e =\n', e)
print('[+] public key')
print('T =\n', T)
print()
# 暗号化
plainA_bit = 2 # 平文A
plainB_bit = 3 # 平文B
print('[+] plainA_bit = %d' % plainA_bit)
print('[+] plainB_bit = %d' % plainB_bit)
print()
A_C1, A_C2 = encrypt(plainA_bit, T)
B_C1, B_C2 = encrypt(plainB_bit, T)
print('[+] ciphertext')
print('A_C1 =\n', A_C1)
print('A_C2 =\n', A_C2)
print('B_C1 =\n', B_C1)
print('B_C2 =\n', B_C2)
print()
# 暗号文同士の加算
C_C1 = A_C1 + B_C1
C_C2 = A_C2 + B_C2
# 復号
decrypted_bit = decrypt((C_C1, C_C2), s)
print('[+] decrypted_bit = %d' % decrypted_bit)
# => 5
平文Aが「2」、平文Bが「3」のとき、それぞれの暗号文を足し合わせたものを復号した平文Cの結果は「5」になることが実行してみると確認できます。
lattice basis: A =
[[1179 3714 3642 ... 629 2380 2135]
[ 206 1563 959 ... 3872 2899 1674]
[2303 2765 670 ... 1915 259 2800]
...
[1940 642 1267 ... 3543 2495 3563]
[2480 120 3711 ... 1410 2429 1722]
[1031 3367 3479 ... 2510 1607 1877]]
[+] secret key
s =
[2028 2149 566 3628 334 3785 174 2683 3355 1715 2865 3344 356 1353
1980 292 1123 1997 138 1688 3956 1478 3914 1441 3082 1333 1462 1491
2861 2171 1348 2030 1142 603 3667 1364 2800 3539 3476 1686 3562 1239
1889 3305 3452 1696 888 1497 1963 1137 3811 513 624 1882 2418 1263
2256 2417 201 2313 3208 2676 3342 1849 3177 2843 901 2145 1720 1378
3827 118 2882 3254 291 3071 338 3991 797 805 2806 74 181 1937
3914 890 1254 3664 3410 3922 1699 1238 2857 35 3956 3223 3560 4014
2478 774 913 760 2492 3191 119 3287 2733 237 3757 2007 890 1721
2684 2364 3012 3941 2927 815 2264 957 1340 2027 1370 61 1366 1633
2396 3127]
e =
[-1. -2. -0. 3. 3. -1. -2. 2. 0. 1. -3. -3. -1. 1. 1. 1. 1. 1.
-3. -4. -2. -1. -2. -3. -7. -1. -2. 4. 0. 3. -2. -2. -2. -2. 1. -0.
-3. -2. 3. 1. -0. 1. 4. 1. -2. -4. 3. 2. -0. 2. 0. -1. -2. 1.
-1. 0. 1. -0. -5. 4. 1. -1. -1. -2. 5. -1. 3. 6. 0. -3. 1. -2.
2. -4. 2. 4. 0. -1. 4. -1. -2. 1. 3. -4. 2. -0. 2. 1. 3. -2.
-1. 2. -2. 3. -2. -1. 1. -2. -0. -2. 0. -3. -4. 2. 3. 3. 2. 1.
1. -1. -3. 0. 0. 1. 0. -4. -5. 1. -5. -2. 1. -1. -1. 0. -0. -2.
-2. -0.]
[+] public key
T =
[3659. 1650. 1725. 3791. 2317. 3105. 1693. 2514. 1602. 3349. 2958. 3579.
1637. 3940. 369. 2902. 1076. 1666. 3692. 1876. 3153. 3473. 1687. 2892.
2293. 2185. 781. 3821. 1777. 3832. 1220. 1968. 27. 3214. 3984. 810.
1852. 1354. 1064. 3583. 2470. 1414. 1167. 1000. 336. 2208. 909. 2237.
1808. 2769. 2563. 3471. 1368. 2233. 3997. 1395. 785. 3669. 2526. 647.
2780. 3939. 3575. 2155. 1035. 504. 1186. 2450. 838. 3632. 3605. 340.
1042. 1629. 3362. 3062. 325. 2468. 349. 1215. 3611. 2105. 787. 2535.
1023. 2780. 2300. 2917. 717. 2245. 183. 2028. 288. 1868. 545. 3463.
1098. 1697. 972. 1797. 3465. 1145. 309. 1428. 2236. 3006. 2472. 3072.
2906. 791. 1088. 304. 3555. 657. 3226. 761. 298. 1173. 1263. 386.
2220. 1839. 745. 1051. 2473. 2129. 3167. 944.]
[+] plainA_bit = 2
[+] plainB_bit = 3
[+] ciphertext
A_C1 =
[1174. 2919. 3147. 1462. 1038. 2666. 1009. 1194. 1577. 1757. 1478. 2351.
1877. 3164. 3306. 3383. 1660. 3487. 1005. 3745. 207. 216. 3163. 560.
3966. 233. 2446. 3940. 2528. 346. 3382. 1478. 2093. 2624. 731. 680.
388. 1841. 1731. 2829. 2882. 2943. 808. 3080. 330. 3695. 2467. 2242.
2441. 3276. 2299. 2631. 1078. 2180. 2342. 3625. 899. 1310. 2286. 1239.
2997. 1682. 1533. 2195. 2061. 732. 1480. 94. 1133. 445. 3441. 2128.
3669. 3175. 237. 2456. 2714. 2607. 1953. 3022. 575. 573. 2504. 3033.
239. 1652. 1495. 2795. 2650. 480. 852. 910. 2328. 3545. 665. 2743.
2963. 2924. 2549. 2029. 556. 681. 3299. 3987. 3520. 1208. 1615. 1567.
3071. 294. 3788. 3760. 3572. 433. 2747. 3230. 3516. 32. 3281. 399.
1075. 93. 1158. 782. 458. 2541. 731. 2326.]
A_C2 =
3688.5
B_C1 =
[ 650. 3282. 1224. 3598. 1246. 3950. 3182. 1205. 2883. 2907. 1001. 1081.
507. 1831. 3301. 2916. 3280. 818. 2676. 1050. 665. 3409. 2140. 3237.
1571. 107. 1555. 1496. 83. 2152. 1774. 1905. 282. 491. 267. 635.
3181. 12. 138. 774. 2303. 3849. 125. 623. 2887. 1893. 3444. 3840.
3640. 1600. 312. 4017. 3784. 3842. 375. 2040. 1916. 3153. 2810. 154.
2761. 2813. 2309. 486. 2894. 2548. 3146. 861. 2181. 2561. 2296. 1414.
2363. 1130. 2177. 3851. 2099. 3531. 105. 2405. 3487. 616. 2164. 3520.
2808. 3261. 1135. 332. 2905. 3951. 1683. 2612. 1567. 1260. 3677. 3473.
3357. 3044. 2901. 2328. 3723. 3454. 3193. 1969. 707. 1506. 1380. 2432.
2898. 3639. 3984. 3803. 3727. 1982. 3596. 2583. 1026. 2602. 360. 3147.
1950. 1627. 960. 884. 3742. 3617. 1447. 2665.]
B_C2 =
1124.25
[+] decrypted_bit = 5
LWE暗号化において、$\mathrm{Enc}(2) + \mathrm{Enc}(3) = \mathrm{Enc}(5)$ が確認できました。
一応、前の記事 で示した式を使って、加法準同型性を式で確認すると、次のようになります。
\[\begin{aligned} \vec{C}_1 &= \vec{r} \cdot{} \vec{A} \\[3pt] C_2 &= \vec{r} \cdot{} \vec{T} - M \\ &= \vec{r} \cdot{} (\vec{G} + \vec{e}) - M \\ &= \vec{r} \cdot{} (\vec{A} \cdot{} \vec{s} + \vec{e}) - M \\[9pt] \mathrm{Dec}(\vec{C}_1, C_2) &= \vec{C}_1 \cdot{} \vec{s} - C_2 \mod q \\ &= \vec{r} \cdot{} \vec{A} \cdot{} s - (\vec{r} \cdot{} (\vec{A} \cdot{} \vec{s} + \vec{e}) - M) \mod q \\ &= \vec{r} \cdot{} \vec{A} \cdot{} s - (\vec{r} \cdot{} \vec{A} \cdot{} \vec{s} + \vec{r} \cdot{} \vec{e} - M) \mod q \\ &= - \vec{r} \cdot{} \vec{e} + M \mod q \\ &= M \\[9pt] \mathrm{Dec}(\vec{C}_{1_A}, C_{2_A}) + \mathrm{Dec}(\vec{C}_{1_B}, C_{2_B}) &= (\vec{C}_{1_A} \cdot{} \vec{s} - C_{2_A}) + (\vec{C}_{1_B} \cdot{} \vec{s} - C_{2_B}) \mod q \\ &= \vec{r}_A \cdot{} \vec{A} \cdot{} s - (\vec{r}_A \cdot{} (\vec{A} \cdot{} \vec{s} + \vec{e}) - M_A) + {} \\ &\phantom{=} \vec{r}_B \cdot{} \vec{A} \cdot{} s - (\vec{r}_B \cdot{} (\vec{A} \cdot{} \vec{s} + \vec{e}) - M_B) \mod q \\ &= -(\vec{r}_A \cdot{} \vec{e} + \vec{r}_B \cdot{} \vec{e}) + M_A + M_B \mod q \\ &= M_A + M_B \mod q \end{aligned}\]ただし、式変形の途中で誤差 $e$ が小さいもので無視できるとします。
以上です。