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程度にでき、また、複数ビットの平文を対応する多項式の係数で表すことにより暗号文の長さを格段に小さくできる。

昨年GoogleNew Hopeと呼ばれる耐量子鍵交換方式の実験を行ったが、この鍵交換方式もRing-LWE問題をベースとしたものになっている。

関連リンク