晴耕雨読

working in the fields on fine days and reading books on rainy days

LWE格子暗号による加法準同型性

LWEによる暗号化では加法準同型性があります。 ここでは平文空間が での暗号化・加法準同型性について、Pythonで実装して検証していきます。

まず、前の記事 では平文空間が のときの暗号化をしましたが、加法準同型性の検証をするには面白くないので、平文空間が での暗号化を考えます。 定義は Fully Homomorphic Encryption – CSE 206A: Lattice Algorithms and Applications, Fall 2017 を参考にしました。

  • LWE暗号化処理

    • 秘密鍵 $\vec{s} \in \Z_q^n$ をランダムに選ぶ。
    • 暗号化 : 秘密鍵 $\vec{s}$, 平文 , ランダムに選んだ値 $\vec{a} \leftarrow \Z_q^n$, 誤差 $e \leftarrow \chi$ を入力し、暗号文を出力する。

    • 復号 : 秘密鍵 $\vec{s}$ と暗号文 $\vec{c}^T = [\vec{a}^T, b]$ を入力し、$\vec{c}^T \bar{s} = \vec{c}^T (-s, 1)$ を一番近い $q/8$ の倍数に丸め込み、その倍数を出力する。

復号について、平文空間のサイズが $2$ で、平文空間が のときは、復号の処理で次の条件を満たすときは平文が「1」としていました。

一般に、平文空間のサイズが $n$ となると、$j$ 番目の平文が「$i$」 である条件は次のようになります(マイナスになる部分は $\mathrm{mod}\,q$ でプラス側に繋がっています)。

注意点として、演算を繰り返すと誤差が大きくなります。そして誤差が $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)$ が確認できました。

一応、前の記事 で示した式を使って、加法準同型性を式で確認すると、次のようになります。

ただし、式変形の途中で誤差 $e$ が小さいもので無視できるとします。

以上です。

参考文献