@yuichirominato 2019.01.14更新 623views

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

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とよばれる格子ベースの暗号の実装実験を行なっています。

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

利用用途

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

以前の記事で検討した結果、

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

1、たびたび登場するhash計算の高速化
2、PoWのプルーフの高速化に重ね合わせが利用できるかどうか

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

Recommended


Wikiへ移動