LWE格子暗号による暗号化をやってみる
近年、量子コンピュータ研究の進展により、量子コンピュータでも解くのが難しい暗号（Post-quantum cryptography; 耐量子計算機暗号）への注目が高まっている。 ここでは、耐量子計算機暗号のひとつであるLWE格子暗号の原理を説明し、単純化したアルゴリズムで暗号化を行うプログラムコードを書いてみる。
格子とLearning with Errors問題
LWE格子暗号は、Learning with Errorsと呼ばれる問題をもとにした公開鍵暗号方式である。
格子とは、基底ベクトルの整数係数線形結合で表される点（格子点）からなる集合である。 格子については、直交しない基底ベクトルからある点Pに最も近い格子点を求めることが計算量的に困難であるといわれている。 これは、最近ベクトル問題（Closest Vector Problem; CVP）と呼ばれる。
Learning with Errors問題は、この点Pを基底ベクトルの整数係数線形結合と誤差の和として表したとき、点Pから係数と誤差を求める問題である。 これは言い換えれば、次のような誤差付きの線形方程式を解く問題であるといえる。
A * s + e = t
誤差がない場合の線型方程式はガウスの消去法などを用いて容易に解けるが、誤差が加わった線形方程式を効率的に解くアルゴリズムは現時点で見つかっていない。
LWE格子暗号では、素数qを法とする有限体上での演算のもとでの格子を考える。 また、LWE格子暗号には暗号文のまま演算ができるという性質がある。 このような性質を持つ暗号は準同型暗号と呼ばれる。
単純化したLWE格子暗号で暗号化してみる
次の資料では、単純化したLWE格子暗号による1ビット平文の暗号化・復号アルゴリズムが説明されている。
このアルゴリズムは本来のLWE格子暗号のアルゴリズムとは異なるが、説明を簡単にするため、ここではこのアルゴリズムをもとにした計算をやってみる。 パラメータ、秘密鍵、公開鍵は次のようになる。
- パラメータ
- n: 格子の次元
- q: 法とする素数
- A: 格子の基底行列（n x n）
- α: 誤差の大きさに関連するパラメータ
- 秘密鍵
- s: 係数（n x 1）
- e: 誤差（n x 1）
- 公開鍵
- T: 格子点に誤差を加えた点（n x 1）
numpyを用いて計算を行うプログラムコードを書くと次のようになる。
import numpy as np
# parameters
n = 230
q = 2053
A = np.random.randint(q, size=(n, n))
alpha = 8.0
def randint_from_gaussian(size):
sigma = alpha/np.sqrt(2*np.pi)
x = np.random.normal(0, sigma, size)
return np.rint(x)
print '[+] parameters'
print "lattice dimension: n = %d" % n
print "prime modulus: q = %d" % q
print 'lattice basis: A = \n', A
print "error distribution parameter: alpha = %f" % alpha
print
# keys
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
# encryption
plain_bit = 1
print "[+] plain_bit = %d" % plain_bit
print
r = randint_from_gaussian(size=n)
C1 = r.dot(A) % q
M = (q+1)/2 * plain_bit
C2 = (r.dot(T) - M) % q
print '[+] ciphertext'
print 'C1 =\n', C1
print 'C2 =\n', C2
print
# decryption
p = (C1.dot(s) - C2) % q
decrypted_bit = int((q+1)/4 < p < 3*(q+1)/4)
print "[+] decrypted_bit = %d" % decrypted_bit
上のコードでは、誤差を正規分布に従って生成し、1ビットの平文を暗号化した後復号している。
復号時は秘密鍵である係数sを用いて -r*e + M を計算し、-r*e として期待される値かどうかで確率的に平文のビットを判定する。
実際に実行してみると、次のようになる。
$ python lwe.py
[+] parameters
lattice dimension: n = 230
prime modulus: q = 2053
lattice basis: A =
[[1543 329 1153 ..., 1259 18 1144]
[ 686 1250 850 ..., 640 1822 502]
[1817 901 1649 ..., 1272 900 145]
...,
[ 207 1325 1223 ..., 1783 1011 1331]
[ 225 1380 1143 ..., 468 1403 50]
[ 937 1758 92 ..., 1938 1435 902]]
error distribution parameter: alpha = 8.000000
[+] secret key
s =
[ 977 2046 1632 1459 1308 729 574 1506 1244 1405 1546 1482 800 213 1551
1122 1691 1910 1302 917 1495 465 681 1442 1953 432 997 2052 1002 105
371 1161 1215 1015 626 1925 1318 1886 1850 1689 320 949 944 153 1536
1112 405 1274 709 928 1049 522 639 1180 1644 1474 1667 2047 313 1693
947 1655 383 703 570 112 737 870 1492 1489 409 348 1744 1759 1075
596 883 1414 404 2004 1553 1624 896 1285 1469 611 1649 717 400 786
963 1561 1142 1301 1457 829 354 291 715 332 1230 1954 1146 1083 761
1233 1455 908 1165 666 542 883 1628 911 189 1058 864 442 1084 22
293 655 1120 1187 190 574 164 1253 1718 676 311 116 1334 1184 1504
1354 1448 1471 1066 1941 147 990 1082 5 25 1190 1692 557 1642 988
1455 527 823 1620 620 1044 133 370 1281 1306 1793 85 1613 1594 380
1430 466 1827 1517 421 1781 471 948 1281 87 568 1717 731 1439 1338
1781 1273 764 580 398 816 1691 1657 1767 471 630 495 824 756 541
644 1746 1991 1597 1223 234 1673 1280 1339 1472 1634 1118 1781 1050 1429
289 1874 846 1510 250 532 662 1407 432 597 205 1442 92 943 403
260 1973 1883 520 736]
e =
[ -3. 6. 1. -2. -6. 2. -4. 1. 4. 2. 1. 1. 2. -2. 3.
-1. 3. 2. 6. -2. -3. -6. 1. -3. 3. -1. -3. 3. -3. -1.
-5. -3. 1. -4. -2. -0. 2. 3. -3. -2. -4. -3. -0. -6. 1.
-0. -4. 1. -2. 1. 0. -1. 0. -0. 1. 1. -3. -1. 0. 2.
1. 2. -4. -3. 2. -1. -4. -2. -2. -3. 3. 0. -2. 0. 0.
-1. 2. 7. 3. 1. -2. -1. -1. -1. 0. 3. 5. 8. 4. -1.
-0. 1. 5. -3. 2. 2. -3. -6. 0. 6. 4. -1. -1. -2. 4.
-2. -6. -2. 2. 4. 5. -2. -1. -0. -2. 4. 7. -2. -1. 1.
-2. 2. -2. -7. 0. 3. 3. 3. 1. -4. 1. 3. 8. 2. 2.
-1. -1. -4. -0. 1. -3. -1. 1. -2. -3. -1. 2. 4. -0. 0.
3. -2. -5. 1. -0. 1. 4. -3. -5. -4. 2. -0. -1. -1. 1.
-4. 6. 0. -0. -2. 0. -6. 0. -1. -1. -2. 2. 4. -3. -0.
-2. 3. 3. -0. 5. 1. 5. -0. 5. -1. 6. -0. -11. 1. -2.
2. 2. 0. -0. 0. -1. -2. 1. -1. 4. 2. -0. -0. 4. 5.
-1. -3. 1. -3. 0. -4. 2. 3. -2. 3. -0. -2. -5. 1. -4.
-0. -3. -4. 4. -3.]
[+] public key
T =
[ 492. 1328. 983. 1435. 1316. 833. 1076. 444. 13. 1561.
1409. 782. 1126. 408. 600. 1127. 1547. 95. 991. 458.
1536. 814. 1926. 527. 1220. 650. 2030. 834. 613. 1191.
1534. 790. 888. 765. 911. 56. 1935. 1782. 6. 491.
1833. 1104. 579. 0. 1211. 1204. 674. 1553. 196. 1480.
1001. 1707. 102. 1000. 331. 858. 1608. 27. 727. 1542.
2050. 640. 1780. 1156. 390. 494. 1532. 874. 797. 993.
859. 1448. 1634. 2029. 743. 1397. 1803. 595. 89. 1085.
1955. 140. 272. 1866. 1113. 2052. 1581. 1103. 1611. 308.
593. 1850. 557. 838. 595. 1999. 1924. 447. 1554. 1548.
2013. 2030. 203. 1858. 1944. 1099. 446. 1872. 1042. 1009.
15. 1215. 412. 1269. 863. 1235. 671. 1124. 28. 383.
146. 58. 338. 1228. 1565. 303. 495. 519. 29. 380.
1974. 1694. 1594. 1308. 1363. 690. 1291. 1096. 745. 642.
309. 1579. 1701. 485. 1798. 1667. 1800. 769. 1095. 1388.
720. 636. 2014. 391. 1238. 1984. 1272. 1810. 1604. 2028.
829. 291. 92. 1187. 1477. 824. 1635. 1620. 187. 1105.
632. 1215. 937. 1591. 1762. 1291. 656. 1128. 1957. 496.
559. 882. 1718. 1746. 1281. 1932. 251. 814. 364. 196.
558. 1910. 257. 11. 1831. 580. 301. 1330. 1405. 546.
267. 690. 1040. 150. 1110. 1007. 874. 473. 1164. 327.
1237. 963. 336. 602. 1421. 1488. 1367. 1440. 1631. 1425.
96. 1250. 477. 1813. 1660. 605. 971. 117. 352. 1064.]
[+] plain_bit = 1
[+] ciphertext
C1 =
[ 1935. 1715. 1768. 9. 1957. 220. 1702. 150. 312. 94.
1007. 1237. 260. 691. 1147. 1194. 1745. 1914. 1822. 825.
1449. 278. 1890. 541. 1568. 50. 459. 29. 1318. 800.
1515. 1593. 907. 596. 299. 302. 1799. 688. 376. 1963.
524. 564. 104. 1975. 1734. 1068. 964. 1368. 748. 1473.
163. 1796. 1579. 1536. 1963. 138. 39. 140. 1982. 382.
676. 704. 83. 1448. 1836. 1888. 255. 1332. 1921. 111.
928. 1942. 350. 2044. 1737. 459. 1646. 779. 1251. 1660.
1209. 991. 1493. 8. 952. 1647. 885. 823. 41. 50.
980. 1087. 1231. 1809. 79. 1054. 1140. 271. 1074. 54.
261. 1063. 1109. 1253. 1019. 1673. 876. 1456. 1255. 1455.
881. 1209. 1594. 1401. 1910. 898. 363. 64. 1485. 437.
553. 1252. 245. 1691. 1897. 48. 624. 520. 258. 138.
692. 1494. 1905. 767. 691. 2039. 1918. 547. 137. 1801.
886. 606. 1480. 767. 924. 198. 1233. 1135. 837. 306.
1465. 1926. 99. 1047. 1725. 2034. 1622. 853. 1992. 1870.
1157. 1364. 1040. 720. 1385. 1013. 342. 2031. 1445. 1552.
1119. 1876. 1053. 406. 1750. 955. 1688. 582. 1201. 900.
2029. 491. 1475. 597. 1764. 1205. 349. 1231. 1852. 1426.
1672. 1310. 354. 434. 225. 1161. 771. 1154. 722. 159.
1986. 1354. 1096. 102. 592. 362. 1397. 1319. 14. 1735.
69. 187. 494. 1413. 1786. 1331. 538. 2036. 1389. 1290.
1587. 622. 260. 782. 1657. 1065. 1345. 1498. 877. 743.]
C2 =
1427.0
[+] decrypted_bit = 1
plain_bitを変えながら複数回実行すると、ほとんどの場合において平文のビットを正しく判定できていることが確認できる。
Ring-LWE格子暗号
上のコードは単純化したものの実装であるが、本来のLWE格子暗号は格子の次元をnとしたとき公開鍵の鍵長がO(n2)となる。 また、上の結果からもわかるように、暗号文の長さは平文のn倍になる。
これらの点を改良したものとして、有限体の代わりに円分体の整数環上での演算を用いたRing-LWE（RLWE）格子暗号がある。 Ring-LWE格子暗号では、公開鍵の鍵長を数千bit程度にでき、また、複数ビットの平文を対応する多項式の係数で表すことにより暗号文の長さを格段に小さくできる。
昨年GoogleがNew Hopeと呼ばれる耐量子鍵交換方式の実験を行ったが、この鍵交換方式もRing-LWE問題をベースとしたものになっている。
