【耐量子コンピュータ暗号】LWE格子暗号を実装してみる


はじめに

最近汎用型の量子コンピュータがIBMから商用化が発表されましたがきになるのが暗号の行方という方も多いのではないでしょうか。

汎用型量子コンピュータにはshorのアルゴリズムと呼ばれる、位相推定アルゴリズムを活用して暗号の周期性を推定するアルゴリズムがあり、原理的に現在のRSAや離散対数問題が現実的な時間で解けてしまうことがわかっています。そのため、マシンの開発も急ピッチで各国争うように進んでいますが、それに対する対応策も徐々に出始めています。NHKでもわかりやすく紹介されています。

https://www.nhk-ondemand.jp/goods/G2018087537SA000/


格子暗号

今回はその中でも格子暗号に着目してみたいと思います。こちらのNICT NEWSにも特集されています。

https://www.nict.go.jp/publication/NICT-News/1303/02.html

詳しい内容は上記を参照していただくとして、基本的には直交しない基底ベクトルからある点に最も近い格子点を求めることが計算量的に困難であるということを元に暗号が作られています。

今回は日本銀行金融研究所の下記の資料に基づいて格子暗号の実装について考えてみたいと思います。きちんと対策をとれば大丈夫なはずなので。

量子コンピュータの解読に耐えうる暗号アルゴリズム

「格子暗号」の最新動向

https://www.imes.boj.or.jp/research/papers/japanese/15-J-09.pdf

対応しなくてはいけないのは主に公開鍵暗号方式で、RSAにしても、ECDSAにしても将来的には対策が必要で、すでに世界中で新暗号策定が始まっています。暗号の移行にはとても時間がかかるので、今の実機の量子ビットがいくつだからまだ大丈夫という話ではなくて、原理的に解けることがわかっていて実機の開発が進んでいるという事実から新暗号は世界の中で必須のものとなっています。

今回は格子暗号の中でもLWE(Learning with error)暗号と呼ばれるタイプに注目してみたいと思います。

実際Google社も2016年にGoogle Chromeに対して、NewHopeとよばれる格子ベースの暗号の実装実験を行なっています。

Google、ポスト量子コンピューティング時代の新暗号化アルゴリズムをChrome Canary版で実験開始

LWEは機械学習でも解決が難しいと言われているらしいです。

https://en.wikipedia.org/wiki/Learning_with_errors


参考

こちらのサイトがすごいです。ほぼこの通りですがやってみたいと思います。

LWE格子暗号による暗号化をやってみる

http://inaz2.hatenablog.com/entry/2017/05/27/003343


早速実装します

実装は解くべき式をみてみます。上記のサイトがとてもわかりやすく引用します。実際に解くべき問題は、下記のようになります。

A * s + e = T

A: 格子の基底行列(n x n)

秘密鍵

s: 係数(n x 1)

e: 誤差(n x 1)

公開鍵

T: 格子点に誤差を加えた点(n x 1)

引用:http://inaz2.hatenablog.com/entry/2017/05/27/003343

これに加えて下記のようなパラメータを考えます。

パラメータ

n: 格子の次元

q: 法とする素数

α: 誤差の大きさに関連するパラメータ

実装

解くべき式がわかったので、実装をみてみます。1ビット平文の暗号化・復号をしてみます。

import numpy as np

# parameters
n = 230 #次元数
q = 2053 #法とする素数
A = np.random.randint(q, size=(n, n)) #nとqから生成される格子の基底
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('n = ',n,', q = ',q,', alpha = ',alpha,'\nA = ',A,'\n\n')

# keys
s = np.random.randint(q, size=n)
e = randint_from_gaussian(size=n)
T = (A.dot(s) % q + e) % q

print('[+] secret key') #秘密鍵の出力
print('s =\n', s)
print('e =\n', e)
print('[+] public key') #公開鍵の出力
print('T =\n', T)

# encryption
plain_bit = 1

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)

結果は、

n =  230 , q =  2053 , alpha =  8.0 

A = [[ 401 792 1729 ... 1240 630 1217]
[ 885 138 1159 ... 678 877 1539]
[ 200 865 849 ... 1752 1768 1123]
...
[1846 1804 1659 ... 1674 372 525]
[1720 2020 168 ... 227 1203 1769]
[1167 1528 1732 ... 963 419 564]]

[+] secret key
s =
[1250 801 793 813 397 12 1895 772 1786 1674 331 458 23 1392
2013 637 1367 186 508 1314 1215 125 1785 861 2023 856 119 1137
1435 85 792 1104 1916 548 824 1969 1115 1253 134 1355 246 1512
623 590 771 1424 477 1952 1504 741 212 1564 1762 1431 31 1716
1044 185 1136 1451 958 1578 190 285 1021 1229 1820 1679 677 882
340 1239 1215 486 760 1995 585 121 1256 1995 647 375 1188 1266
1633 537 651 1905 179 857 1890 1245 1737 1842 1601 326 1881 926
1561 1914 857 1171 940 227 99 1690 1213 1632 226 571 1591 1545
491 145 211 434 184 1646 1064 2043 1547 1159 683 8 404 528
1849 406 1844 1833 561 79 138 1202 1807 1894 538 878 54 1778
422 154 499 128 1537 325 48 2011 1646 218 1705 1329 633 253
1809 1823 229 217 662 1117 636 1774 101 1761 211 1465 741 1906
670 822 825 622 1286 1151 1841 1149 1169 1431 592 1212 1055 156
1419 1046 1329 1139 1553 1828 766 1390 1943 559 370 1525 1171 106
937 395 391 1779 1461 1968 996 821 1832 454 1403 1663 1100 944
1174 1475 1119 1550 1208 964 719 413 14 843 2050 1923 752 1976
12 1323 1000 1679 29 1753]
e =
[ 2. 1. 3. 2. 4. 1. -2. -2. 1. -1. -0. -2. -2. 0.
-3. 3. -3. 2. 4. -2. -1. -1. -3. -3. 0. 1. 5. -1.
-0. 4. 1. 2. -0. 0. -3. 0. -5. -3. -0. -0. -1. 4.
-2. 3. -4. 0. -1. -1. -2. 1. 1. 7. -4. -3. -0. -10.
5. 2. 0. -3. 3. -0. 1. 0. -1. -0. -1. 1. 4. -3.
-2. 1. -1. 4. -0. -2. -5. -0. 2. -3. 2. 3. -1. 3.
3. 4. 0. -1. 0. -4. -3. -3. -1. 0. 0. -3. -1. -3.
-1. 2. 1. 2. -4. -2. -0. 0. 2. -3. 6. -5. -2. -0.
-2. -1. -1. -2. 3. -1. 4. -5. -2. 1. 2. 1. -1. -0.
-2. -0. 2. -6. 3. 1. -1. 1. -3. 4. -5. -2. -2. -4.
1. -5. 2. 2. -0. -3. -3. -6. 9. -3. 1. 0. 1. 1.
1. 1. 6. -3. -1. 12. 0. 4. -0. 3. -2. -1. -1. 1.
-1. 2. -4. -7. 2. -2. 3. 2. -3. -5. -4. 2. -2. -1.
1. 8. 9. 0. 1. -4. 5. -1. -2. -4. -1. -2. -1. -2.
1. -0. 2. 2. -6. 1. -2. 2. -3. 2. -1. 3. 5. -1.
2. -1. -3. -3. 0. -1. -5. 4. -2. -4. 3. 5. -1. -1.
1. 2. 5. 2. 0. 6.]
[+] public key
T =
[ 998. 1230. 834. 920. 828. 1519. 484. 1292. 1294. 374. 1757. 1321.
507. 1269. 1644. 248. 114. 9. 1684. 1714. 1990. 1439. 676. 1586.
1063. 1241. 246. 859. 933. 297. 404. 642. 1183. 1408. 115. 597.
1756. 280. 2002. 1565. 1170. 1011. 1041. 1015. 908. 1702. 1180. 1208.
1365. 230. 1555. 1651. 1187. 466. 1523. 1868. 463. 1863. 2025. 433.
1161. 447. 241. 944. 766. 131. 1833. 1881. 1989. 943. 1362. 372.
464. 1428. 1697. 1561. 851. 1059. 2040. 1514. 1973. 240. 1192. 60.
1030. 1550. 1724. 1980. 152. 28. 810. 1550. 877. 1235. 1174. 57.
1330. 1143. 671. 1148. 295. 778. 1497. 193. 99. 1418. 430. 658.
1224. 464. 1299. 96. 335. 1240. 1794. 715. 1140. 1223. 222. 1025.
808. 685. 1913. 979. 976. 1728. 1568. 140. 1765. 1677. 711. 1977.
1812. 1250. 1089. 200. 630. 1992. 162. 963. 295. 318. 1166. 1004.
1415. 540. 2052. 1302. 583. 221. 1205. 506. 186. 1698. 1327. 352.
1690. 1225. 1095. 1178. 1021. 1790. 77. 291. 1303. 501. 608. 371.
148. 1304. 374. 359. 589. 1829. 272. 119. 1071. 682. 740. 1668.
244. 670. 553. 1344. 350. 1886. 59. 24. 1333. 857. 98. 93.
257. 1690. 1335. 1775. 1123. 1777. 1668. 751. 1059. 1682. 1310. 822.
457. 687. 135. 58. 1323. 129. 617. 397. 396. 88. 1940. 594.
834. 1331. 344. 138. 924. 436. 1812. 1025. 1430. 1869. 939. 150.
719. 39.]
[+] ciphertext
C1 =
[1352. 289. 835. 411. 1400. 781. 933. 68. 1479. 1124. 1286. 950.
1434. 1565. 788. 220. 1943. 747. 571. 661. 601. 1451. 239. 1980.
1184. 2047. 596. 1484. 2046. 1951. 618. 728. 820. 1212. 1269. 1354.
579. 947. 165. 205. 296. 825. 1665. 112. 1659. 109. 579. 1761.
1845. 899. 845. 1307. 731. 1923. 320. 603. 189. 788. 854. 1587.
1480. 1615. 1514. 1266. 1086. 1370. 299. 1971. 1072. 1988. 945. 168.
575. 1791. 1686. 1599. 798. 1890. 1981. 2022. 1272. 987. 894. 745.
1116. 1984. 1240. 1731. 1378. 452. 1377. 1088. 563. 538. 1716. 1410.
1668. 1788. 1609. 958. 1926. 960. 267. 1507. 846. 1588. 149. 1580.
1665. 1229. 87. 688. 670. 750. 1389. 1141. 1092. 2018. 1196. 150.
1019. 144. 447. 802. 1851. 904. 1485. 1335. 716. 1503. 1133. 452.
1796. 1178. 731. 5. 1925. 17. 1861. 1617. 1460. 206. 192. 1336.
678. 29. 269. 1536. 1329. 1669. 250. 241. 1985. 1403. 1062. 901.
1541. 911. 353. 1797. 2040. 702. 748. 1538. 921. 877. 66. 502.
1242. 636. 894. 1514. 424. 174. 1432. 766. 1354. 985. 551. 1104.
800. 1769. 654. 470. 1487. 199. 1905. 972. 858. 939. 700. 147.
1193. 1733. 1432. 57. 340. 1770. 1668. 260. 774. 682. 1548. 184.
1131. 1033. 1236. 1474. 1632. 1826. 1264. 417. 1168. 1617. 1921. 438.
475. 349. 1651. 1954. 208. 1061. 289. 1953. 1378. 796. 316. 1390.
1860. 1079.]
C2 =
1866.0

[+] decrypted_bit = 1

引用:http://inaz2.hatenablog.com/entry/2017/05/27/003343

誤差を正規分布に従って生成し、1ビットの平文を暗号化した後、秘密鍵であるsを用いて-r*e+Mを計算して復号している。 -r*eとして期待される値かどうかで確率的に平文のビットを判定する。


Ring-LWE格子暗号

このままではAのサイズがO(n2)となってしまうので、これを改良しAを軽量化するためのRing-LWE格子暗号が開発されており、それにより暗号長が数千bit程度になるという。Googleの利用していたNewHopeもRLWEを利用して実験を行なっていたという。今後はRLWEにより注目してソリューションを目指していきたい。


利用用途

公開鍵暗号に対してRLWEが開発されるということで、オンラインの取引や仮想通貨のトランザクションの保護などが考えられます。

ブロックチェーン自体の性能に量子コンピュータが大きく貢献できるかどうかは、

1、たびたび登場するhash計算の高速化

2、PoWのプルーフの高速化に重ね合わせが利用できるかどうか

あたりが妥当ですが、トランザクションの署名に暗号化が利用されるとすると、その辺りにRLWEを利用することで量子コンピュータの耐性を高めることはできると思います。