@yuichirominato 2019.01.29更新 508views

【新暗号】LWE格子暗号をつかってデータを暗号化したまま量子コンピュータで計算してみる


はじめに

現在は21世紀なので何が起きても不思議じゃありません。また最近はものすごい優秀な人たちが多いです。昨日面白い記事を見つけました、

データを暗号化したまま解析する「秘密計算」技術を研究開発するEAGLYSは1月28日、SBIインベストメントとユーザーローカルから資金調達を実施したと発表した。調達金額は非公開だが、1億円前後の金額だと見られる。

データを暗号化したままビッグデータ解析!

データを暗号化したまま解析!ということで、個人情報保護や大事なデータを守りつつビッグデータを処理したい!という需要は現在確実にあります。暗号化したままニューラルネットワークで深層学習したいとか、機械学習したいとかいう要望があります。暗号化してあれば元データはわかりませんので、統計が今よりも簡単に扱えます。

将来的により大きなデータを処理したいということで、暗号化したまま統計データが取れるのは大変大きな需要がありそうでビジネスチャンスの香りがします。

ということで、見つけました。暗号文のまま計算しよう。

準同型暗号というのを使うと計算ができてしまうようです。

準同型暗号

準同型暗号をwikipediaで探しました。

準同型暗号(じゅんどうけいあんごう)は、準同型性を有するような暗号方式である。RSA暗号ElGamal暗号など整数論をベースとした多くの公開鍵暗号は、この特徴を有しており、電子投票電子マネーなどの暗号プロトコルにおいて利用される。

https://ja.wikipedia.org/wiki/%E6%BA%96%E5%90%8C%E5%9E%8B%E6%9A%97%E5%8F%B7

こういうスライドも見つけました。

Ring-LWE格子暗号がでてきました。ということはLWE格子暗号で計算できるんでしょうか?

LWE格子暗号

パッケージでいい高度な暗号がたくさん出てますが、先日ブログで参考サイトから試して計算をしてみましたので、それを使って本当に足し算ができるかやってみたいと思います。

https://blog.mdrft.com/post/1271

参考にしましたのはこちらです。

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: 法とする素数
    • α: 誤差の大きさに関連するパラメータ
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)

今回はこれをそのまま拡張してみます。どうやら計算に使用するのは、暗号化した後のC1とC2を使うことで計算できそうです。C2同士を足して、C1で復号します。

普通に足し算をやってみる

普通にやってみます。

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('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@s % q + e) % q

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

# encryption
plain_bit1 = 1
plain_bit2 = 0

r1 = randint_from_gaussian(size=n)
r2 = randint_from_gaussian(size=n)
C1 = r1@A % q
C2 = r2@A % q

C21 = (r1@T - (q+1)/2*plain_bit1) % q
C22 = (r2@T - (q+1)/2*plain_bit2) % q
C23 = C21 + C22
C24 = C21 + C21
C25 = C22 + C22

print('[+] ciphertext')
print('C1 =\n', C1)
print('C2 =\n', C2)
print("")
print('C21 =\n', C21)
print('C22 =\n', C22)
print('C23 =\n', C23)
print('C24 =\n', C24)
print('C25 =\n', C25)
print("")

# decryption
p1 = (C1@s - C21) % q
p2 = (C2@s - C22) % q
p3 = ((C1+C2)@s - C23) % q
p4 = ((C1+C1)@s - C24) % q
p5 = ((C2+C2)@s - C25) % q
decrypted_bit1 = int((q+1)/4 < p1 < 3*(q+1)/4)
decrypted_bit2 = int((q+1)/4 < p2 < 3*(q+1)/4)
decrypted_bit3 = int((q+1)/4 < p3 < 3*(q+1)/4)
decrypted_bit4 = int((q+1)/4 < p4 < 3*(q+1)/4)
decrypted_bit5 = int((q+1)/4 < p5 < 3*(q+1)/4)

print("[+] decrypted_bit1 = %d" % decrypted_bit1)
print("[+] decrypted_bit2 = %d" % decrypted_bit2)
print("[+] decrypted_bit3 = %d" % decrypted_bit3) 
print("[+] decrypted_bit4 = %d" % decrypted_bit4) 
print("[+] decrypted_bit5 = %d" % decrypted_bit5)

こういうのを用意しました。実行してみます。僕は暗号はあまり詳しくないので、暗号化するのを0と1を準備します。0+0と1+0と1+1をしてみます。

計算結果は、何度かやってみて、

n =  230 , q =  2053 , alpha =  8.0 
A =  [[ 216 1225 1194 ...  967 1452  991]
 [ 525 1619 1648 ...  196 1518 1659]
 [ 394 1249 1749 ... 1808 1500 1585]
 ...
 [1500  689   17 ...  642  575  124]
 [ 217 1241 1326 ... 1595 1356 1409]
 [1345  724 1272 ...  175 1305   60]] 


[+] secret key
s =
 [1775 1887 1900  476 1448 1947  607 1285 1921 1660 1752  409 1926 1354
  296  569 1990 1846 1618 1115  469 1190  464  230   90  469 1652  682
 1846  599  735  178  623  551  742 1428  300 1418 1785 1987 1617  674
 1179  429   10 1068 1119  732 1522 1108  188  531 1874  292  753   44
  336  238  861  581 1114 1839  837  560  720 1694  860  810  710  645
  630 1360 1403 1420  746  505   38 1012  757  273   50 1306 1630 1639
  497 1414 1669 2004  174  548 1245  906   83  864  757  737   51 1916
 1415  500  953 1358  759 1255 1862  922 1730 1286 1426 1601   47 1291
 1863 1251   51 1881  894 2043 1387 1710 1819 1933 1239 1787  221  700
  369  301 1650 1259  563 1072 1999  917 2008  323 1945 1921  373 1742
  589  609 2030 1247  328 1205  760 1253 1920  288   19  261   20  774
    7 1726  436  139  560  710  446  347 1599 1151 1882 1111  191  786
  748  735  776 1182 1931 1635 1575 1242 1738 1101  141 1162 1201  310
  815   20 1801  792 1068 1231 1477  169  863 1649  319  165  645 1926
   53 1019 1585  969  798 1356  989  446  645  348 1282  390 1877 1984
   70  823 1947  543 1470  918  422  753  149 1649  327  481 1260  771
 1822 1589  275 1682 1274 1720]
e =
 [  4.  -2.   2.   4.   5.   2.  -5.  -4.   1.   1.   2.  -1.   0.   3.
  -0.  -0.  -3.   1.   1.  -1.   3.  -2.   5.   3.   2.   1.   1.  -1.
  -2.  -3.   0.   2.   1.  -4.  -0.   3.  -1.  -1.   0.  -6.   1.  -1.
  -1.   2.   1.   1.  -5.  -0.   6.  -4.   3.  -2.  -3.   7.   6.   5.
  -6.  -1.  -2.   4.   2.   5.  -2.   3.  -1.  -0.  -3.   2.   5.  -0.
   0.   5.   2.  -0.  -1.  -3.   2.   6.  -3.  -2.  -1.  -0.  -3.  -4.
   2.  -2.   1.   1.  -5.   1.   1.   2.   3.   1.   4.  -0.  -2.   1.
  -2.  -1.  -3.   1.   2.   3.  -3.  -3.   3.  -3.  -4.   1.  -2.   5.
   8.  -1.  -1.   3.   1.  -7.   1.   1.   5.  -5.  -5.  -5.   4.  -1.
   5.  -1.   1.   3.  -1.   5.  -2.   3.   2.  -1.  -0.   3.   7.  -0.
   0.   1.   7.   0.   1.   2.   0.  -2.   0.   7.   1.  -2.   1.   2.
  -0.   2.  -1.   1.  -3.  -4.   0.  -3.   1.   1.   4. -10.  -5.   2.
  -8.  -7.  -1.   2.  -1.   4.   3.  -5.   0.  -0.   2.   2.   3.  -2.
   6.  -4.   3.   4.   5.   1.   2.   3.  -0.  -3.   6.  -1.   1.  -2.
  -1.   7.   4.   1.   4.  -0.  -4.  -4.   1.  -0.   2.   5.  -1.   4.
   1.  -4.   0.   3.   6.   2.  -3.   2.   7.  -1.  -0.  -2.  -1.  -7.
  -3.   1.   2.   1.  -3.  -8.]
[+] public key
T =
 [ 873. 1161.  538. 1801. 1512.   26. 1073. 1969.  193. 1585.   53. 1570.
 1162. 2010.  562.  245. 1451.  906.  181.   66.  186.  930.  528. 1078.
  393.  516. 1262. 1425. 1123.   73. 1493. 1214. 1749. 1789.  214. 1411.
 1337. 1326. 1364. 1842.  109. 1201.  284. 1791.  755.  559. 1331. 1374.
 1661.  824. 1849.  679. 1411. 1962. 1285. 1455.   36.  315.  885. 2034.
  438. 1849.  627. 1026. 1735. 1877. 1086. 1138.    5.  684.  858.  603.
 1380.  896. 1875.  718. 2048. 1999.  369.   95.  198. 1819.  414.  332.
  426.  733.  127.  851. 1883. 1409. 1475.  136.   12.  160. 1937.  497.
 1046. 1595.  830.  726.  579. 1096. 1812. 1754. 1433.   55. 1173.  339.
  627. 1856. 1180. 1851.  656.  784.  926.  276. 1520. 1878. 1874. 1900.
   32.  586. 1982.  897. 1451.  440.  783.  767.  635. 1708.  277. 1627.
 1624.  157. 1328.  921. 1544. 1590. 1341.  949.   37.   99.  896.   76.
 1871. 1478.  501. 1041. 1721.  810. 1291. 1149. 2018.  309. 1532. 1799.
  858.  286.  540. 1059.  613.  580. 2000.  287. 1433.  689.  773. 1539.
  252. 1538. 1415. 1822.  152.  900. 1491.  653.  499. 1333. 1628. 1571.
  759. 1851. 1498.  748. 1489. 1471.  372. 1947. 1364. 1275. 1115. 1851.
 1443. 1041. 1285. 1192. 1303.   33.  690. 2029.  433.  572. 1566. 1872.
  260.  666. 1714. 1664. 1046.  698. 1220.  578.  262.  102.  549. 1927.
 1545.  202.  657. 1064.  932.  923. 1442.  970.  688.  479. 1593.  125.
 1366. 1024.]
[+] ciphertext
C1 =
 [ 233. 1605. 1110.  689.  804.  375.  196. 1966. 1476.  188. 1504.  309.
  824.  291. 1572. 1924. 1075. 1666.   53. 1705. 1883. 1525.  599. 1085.
   58. 2036.  806. 1676.  556.  778. 1372. 1147.  191. 1513. 1218.  282.
  685.  594.  533. 1892.   98.   99.  108. 1340. 1654. 1763.  869. 1681.
  724.  953. 1993. 1450.  252. 1141. 1351.  930. 1429.  181. 1004.  610.
 1927.  776.  349. 1851. 1946. 1002. 1499. 1631.  260.  353. 1379. 1312.
  732.   27. 2022.  289. 1852.  319.  834.  780.  886.  653.  562.  793.
 1219.  720.  561.  283.   78. 1711.  669.  916. 1444.  413. 1278. 1385.
 1484. 1756. 2017.  598. 1633. 1133. 1056.  927. 1404. 1178.  445. 1340.
 1033.  284.  946. 1331.  395. 1440. 1527. 1454. 1578.  412. 1660. 1592.
 1892. 1505.  546. 1399. 1707. 1841.  335. 1633.  506. 1093.  528. 1330.
   49. 1104. 1308.  930. 1158.  574.  363. 2038. 1086.  120.  821. 1729.
 1211.  123. 1507. 1360.  359. 1970.  593. 1324. 1973. 1660.  983. 1722.
  969. 1187. 2031. 1651.  175. 1932. 1379. 1411. 1744. 1601.  460.  807.
 1787.  767.  818.  179.  262.   21. 1151.  674.  905. 1874. 1478.  387.
  986.  548.  161.   27.  752. 1968.  220.  916.  593.  821. 1061.  850.
  930.  164.  690.  511. 1727.  180. 1819. 1411.  614. 1202. 1089.  143.
 1522.  187.  905. 1796. 1226. 1048. 1101. 1682.  721. 1233.  695. 1070.
  799.  115.  248.  385. 1139.  195.  235.   29.  151.  632. 1994. 1850.
  113.  680.]
C2 =
 [4.510e+02 1.284e+03 1.770e+03 9.110e+02 7.100e+01 6.250e+02 1.402e+03
 3.920e+02 1.991e+03 1.100e+02 1.309e+03 1.370e+03 3.050e+02 8.700e+02
 1.919e+03 1.632e+03 1.974e+03 8.200e+01 1.297e+03 1.817e+03 3.160e+02
 7.290e+02 1.516e+03 1.675e+03 1.813e+03 7.580e+02 1.509e+03 2.710e+02
 4.180e+02 1.883e+03 6.260e+02 1.102e+03 9.850e+02 4.700e+02 1.729e+03
 4.250e+02 7.210e+02 3.120e+02 5.530e+02 9.320e+02 2.530e+02 1.531e+03
 2.790e+02 3.170e+02 1.200e+02 4.420e+02 1.040e+02 1.869e+03 1.866e+03
 5.300e+02 1.815e+03 1.638e+03 9.370e+02 1.096e+03 1.410e+03 1.995e+03
 9.920e+02 1.653e+03 1.264e+03 2.400e+02 1.804e+03 1.507e+03 9.050e+02
 6.280e+02 1.403e+03 8.410e+02 1.304e+03 1.032e+03 1.350e+03 1.170e+03
 6.960e+02 1.809e+03 6.930e+02 7.040e+02 1.338e+03 5.400e+02 2.032e+03
 1.730e+02 3.720e+02 1.209e+03 5.300e+01 2.006e+03 1.387e+03 1.242e+03
 1.659e+03 8.640e+02 4.280e+02 1.158e+03 8.290e+02 5.980e+02 1.707e+03
 4.590e+02 1.241e+03 1.099e+03 3.830e+02 1.068e+03 4.500e+01 9.030e+02
 3.550e+02 1.952e+03 1.860e+02 1.634e+03 4.230e+02 1.871e+03 1.499e+03
 1.034e+03 5.470e+02 1.803e+03 3.320e+02 1.000e+00 1.540e+03 3.940e+02
 4.840e+02 6.290e+02 8.950e+02 1.748e+03 1.123e+03 1.497e+03 9.680e+02
 7.640e+02 1.534e+03 1.861e+03 2.048e+03 5.790e+02 1.490e+03 1.390e+03
 1.462e+03 4.550e+02 8.600e+01 9.520e+02 1.165e+03 8.590e+02 4.440e+02
 2.210e+02 7.810e+02 1.888e+03 4.680e+02 7.440e+02 6.260e+02 4.200e+01
 7.540e+02 1.718e+03 8.680e+02 1.004e+03 3.520e+02 4.550e+02 1.768e+03
 1.309e+03 1.866e+03 1.659e+03 2.350e+02 8.300e+01 1.662e+03 1.563e+03
 1.347e+03 6.300e+01 1.064e+03 1.394e+03 3.520e+02 2.540e+02 1.589e+03
 6.130e+02 4.620e+02 1.618e+03 4.990e+02 1.731e+03 8.300e+02 9.050e+02
 1.849e+03 1.240e+02 1.435e+03 9.810e+02 1.310e+03 7.370e+02 1.000e+03
 7.220e+02 1.320e+03 1.899e+03 7.000e+01 1.159e+03 1.424e+03 5.970e+02
 3.220e+02 5.200e+02 1.495e+03 1.948e+03 1.384e+03 1.312e+03 2.950e+02
 1.894e+03 8.000e+00 1.547e+03 1.050e+03 1.222e+03 1.287e+03 1.320e+02
 1.897e+03 1.634e+03 1.649e+03 1.176e+03 1.980e+03 5.530e+02 1.416e+03
 7.710e+02 1.039e+03 1.306e+03 3.350e+02 6.900e+02 3.080e+02 1.938e+03
 8.800e+02 1.656e+03 2.350e+02 4.660e+02 1.106e+03 8.460e+02 1.938e+03
 1.080e+02 7.020e+02 1.486e+03 1.984e+03 8.460e+02 1.458e+03 7.170e+02
 1.576e+03 9.330e+02 7.440e+02 1.135e+03 1.554e+03 3.550e+02]

C21 =
 1475.0
C22 =
 38.0
C23 =
 1513.0
C24 =
 2950.0
C25 =
 76.0

[+] decrypted_bit1 = 1
[+] decrypted_bit2 = 0
[+] decrypted_bit3 = 1
[+] decrypted_bit4 = 0
[+] decrypted_bit5 = 0
[+] decrypted_bit1 = 1
[+] decrypted_bit2 = 0
[+] decrypted_bit3 = 1
[+] decrypted_bit4 = 0
[+] decrypted_bit5 = 0
[+] decrypted_bit1 = 1
[+] decrypted_bit2 = 0
[+] decrypted_bit3 = 1
[+] decrypted_bit4 = 0
[+] decrypted_bit5 = 0
[+] decrypted_bit1 = 1
[+] decrypted_bit2 = 0
[+] decrypted_bit3 = 1
[+] decrypted_bit4 = 0
[+] decrypted_bit5 = 0

何回かやりましたが、1,0,1,0,0の答えが出ました。暗号化から少しずつみてみたいと思います。

# 暗号化する2つのビット
plain_bit1 = 1
plain_bit2 = 0

#ガウス分布を暗号化するビットごとに用意
r1 = randint_from_gaussian(size=n)
r2 = randint_from_gaussian(size=n)

#それぞれ暗号化
C1 = r1@A % q
C2 = r2@A % q

#それぞれ暗号化
C21 = (r1@T - (q+1)/2*plain_bit1) % q
C22 = (r2@T - (q+1)/2*plain_bit2) % q

#暗号化したものを足し算する
C23 = C21 + C22 #1+0に対応
C24 = C21 + C21 #1+1に対応
C25 = C22 + C22 #0+0に対応

それぞれ暗号化したビットを足し合わせてみました。

復号してみる

次に上記計算したものを復号してみます。暗号化されたC1やC2を使いながら復号をします。

# 復号
p1 = (C1@s - C21) % q
p2 = (C2@s - C22) % q

#足し算したやつは対応したC1やC2をつかって復号
p3 = ((C1+C2)@s - C23) % q
p4 = ((C1+C1)@s - C24) % q
p5 = ((C2+C2)@s - C25) % q

decrypted_bit1 = int((q+1)/4 < p1 < 3*(q+1)/4)
decrypted_bit2 = int((q+1)/4 < p2 < 3*(q+1)/4)
decrypted_bit3 = int((q+1)/4 < p3 < 3*(q+1)/4)
decrypted_bit4 = int((q+1)/4 < p4 < 3*(q+1)/4)
decrypted_bit5 = int((q+1)/4 < p5 < 3*(q+1)/4)

#表示
print("[+] decrypted_bit1 = %d" % decrypted_bit1)
print("[+] decrypted_bit2 = %d" % decrypted_bit2)
print("[+] decrypted_bit3 = %d" % decrypted_bit3) 
print("[+] decrypted_bit4 = %d" % decrypted_bit4) 
print("[+] decrypted_bit5 = %d" % decrypted_bit5)

を実行するとこうなりました。 

[+] decrypted_bit1 = 1 #1に対応
[+] decrypted_bit2 = 0 #0に対応
[+] decrypted_bit3 = 1 #1+0に対応
[+] decrypted_bit4 = 0 #1+1に対応
[+] decrypted_bit5 = 0 #0+0に対応

上記を見ると何回か計算してみましたが、1,0の暗号化復号はもちろんOKで、1+0や0+0のような桁上がりがないものは大丈夫でした。

量子計算への応用

僕は暗号に詳しくないですが、桁上がりがなければ計算できそうです。量子計算でもやってみます。暗号化されたものを見てみると、、、

C21 =
 1475.0
C22 =
 38.0
C23 =
 1513.0
C24 =
 2950.0
C25 =
 76.0

これを足し算するのは今の量子ビットでは大変そうです。。。ちょっと式を見てみると、復号に使うC1やC2は大丈夫そうですが、実際に足し算をする方は気をつけてやってみたいです。

C21 = (r1@T - (q+1)/2*plain_bit1) % q
C22 = (r2@T - (q+1)/2*plain_bit2) % q

なんかうまく暗号化されれてC21やC22の値が小さければ計算できそうです。。。探してみます。下記は成立していました。

[+] ciphertext
C1 =
 [  70. 1475. 2010.   60.  695.  364. 1704.   94.  558.  998.  149. 1350.
 1444. 1783.  595. 1490. 1602. 1926.  537.  671.  479.  791. 1289.  791.
 1212. 1224.  749. 1641.  662. 1119. 1223. 1412. 1397. 1683. 1731.  656.
 1657.   62. 1962. 1534. 1054.  100. 1342. 1538.  306. 1415. 1219. 1345.
 1807. 1883.  761. 1110.  601.  114.  316. 1292. 1106. 1428.  150. 1393.
 1317. 1786.  891. 1516.  895.  951. 1283.  600.  817. 1831. 1364.   33.
 1993.  316. 1774. 1662. 1446.  147.  965.  312.  426.  576. 2038. 1116.
  419. 2034.   86.  960.   56. 1842. 1834.  788. 1090.  930.  879. 1064.
  330. 1331.   49.  414.  282. 1430.   33. 1385.  405. 1471. 1136.  390.
  357.  801.  963.  211. 1404. 1307. 1538.  280.  952.  130.  965. 1788.
 1598. 1036. 1123. 1090. 1770. 1488. 1169.  133.  310.  770.  961.  199.
 1574.  671.  620. 1646. 1390. 2036. 1413.   87. 1565.   76. 1631.  341.
  479. 1309. 1320.  747.   52. 1863.  481.  571.  386. 1377. 1632. 1875.
 1815. 1653.  319. 1612.  121. 1299. 2020. 1369. 1762.  494.  266. 1510.
 1579.  992. 1364.  769. 1813. 1983.  516. 1635.   18. 1181. 1912.  166.
 1092. 1353. 1440. 1523.  257. 1083. 1990.  977. 1159.   52. 1754.  677.
  305.   46. 1162.  867. 1149. 1490.  745.  389.   14.  704. 1989. 1687.
 1700. 1585.  186.  902. 1792. 2035.  287. 1216. 1817.  583. 1866.  843.
  388.  348.  505. 1008. 1304. 1690. 1673. 1701. 1306.   43. 1453.  653.
 1440. 1578.]
C2 =
 [8.290e+02 1.161e+03 1.194e+03 4.950e+02 9.480e+02 2.044e+03 8.320e+02
 1.909e+03 3.120e+02 1.102e+03 1.245e+03 1.383e+03 1.300e+01 1.630e+03
 8.430e+02 1.000e+00 7.460e+02 4.790e+02 1.967e+03 4.800e+02 3.490e+02
 1.512e+03 1.050e+03 1.134e+03 7.570e+02 3.810e+02 9.390e+02 6.690e+02
 1.278e+03 1.779e+03 1.994e+03 1.923e+03 1.041e+03 2.600e+02 7.250e+02
 4.180e+02 2.740e+02 8.000e+00 1.013e+03 1.430e+02 1.169e+03 1.580e+02
 4.360e+02 1.628e+03 1.770e+02 1.720e+02 2.002e+03 7.930e+02 1.983e+03
 8.590e+02 8.070e+02 8.700e+01 1.882e+03 3.590e+02 1.884e+03 1.470e+03
 7.870e+02 1.960e+02 1.165e+03 4.120e+02 8.100e+02 1.760e+03 8.000e+00
 8.870e+02 7.370e+02 2.770e+02 7.090e+02 1.760e+02 9.600e+01 1.530e+02
 4.010e+02 2.600e+02 1.418e+03 1.278e+03 1.140e+03 1.486e+03 5.460e+02
 8.430e+02 1.118e+03 1.370e+02 9.430e+02 2.000e+01 3.420e+02 1.751e+03
 8.920e+02 4.800e+01 4.300e+01 1.281e+03 2.510e+02 9.780e+02 1.792e+03
 1.177e+03 1.956e+03 1.801e+03 1.232e+03 1.654e+03 1.878e+03 4.340e+02
 1.215e+03 1.700e+01 1.492e+03 8.800e+01 6.250e+02 9.000e+02 1.281e+03
 1.879e+03 4.360e+02 5.130e+02 1.670e+03 1.622e+03 9.380e+02 6.270e+02
 2.012e+03 1.219e+03 1.725e+03 9.580e+02 1.750e+03 1.495e+03 1.822e+03
 1.317e+03 1.041e+03 2.950e+02 7.570e+02 1.701e+03 1.592e+03 1.920e+02
 1.722e+03 1.397e+03 1.755e+03 4.600e+02 1.409e+03 1.738e+03 7.520e+02
 1.547e+03 1.045e+03 1.892e+03 6.130e+02 7.740e+02 1.339e+03 1.149e+03
 8.590e+02 1.513e+03 1.623e+03 1.540e+02 8.820e+02 1.766e+03 1.821e+03
 2.032e+03 1.846e+03 5.120e+02 2.820e+02 1.886e+03 4.780e+02 1.190e+03
 1.370e+03 4.430e+02 1.542e+03 6.840e+02 9.260e+02 5.930e+02 2.190e+02
 1.376e+03 7.810e+02 1.215e+03 7.220e+02 1.130e+03 2.970e+02 2.043e+03
 1.850e+03 1.804e+03 1.364e+03 1.186e+03 1.131e+03 1.121e+03 1.985e+03
 2.450e+02 1.642e+03 1.723e+03 7.600e+01 4.440e+02 2.590e+02 4.080e+02
 1.723e+03 2.130e+02 6.600e+02 9.300e+01 6.000e+01 1.539e+03 3.700e+01
 1.586e+03 1.093e+03 5.380e+02 1.949e+03 5.980e+02 1.510e+03 8.490e+02
 1.825e+03 4.660e+02 6.720e+02 4.380e+02 9.220e+02 6.220e+02 1.557e+03
 9.370e+02 3.800e+02 1.020e+02 1.708e+03 1.150e+03 1.251e+03 5.240e+02
 1.131e+03 1.764e+03 1.358e+03 1.442e+03 1.596e+03 1.959e+03 1.223e+03
 1.880e+02 6.980e+02 1.381e+03 1.803e+03 4.810e+02 1.662e+03 1.520e+02
 8.430e+02 7.030e+02 8.450e+02 1.659e+03 1.264e+03 1.960e+02]

C21 =
 167.0
C22 =
 98.0
C23 =
 265.0
C24 =
 334.0
C25 =
 196.0

10進数を量子計算で処理する

これを使ってやってみます。汎用回路なんであんまり量子関係ないですが、まぁ回路を変えていけば将来的には同じことになる気がします。とりあえず今できることをやってみます。

https://blog.mdrft.com/post/2141

10進数の計算はこちらの回路です。格子暗号と組み合わせてみました。現実的な値に暗号化されたらそれを使って0+1を足し算してみます。

from blueqat import Circuit

#ビットのキャリー回路
def carry(a):
    return Circuit().ccx[a+1,a+2,a+3].cx[a+1,a+2].ccx[a,a+2,a+3]

#ビットのキャリー回路の逆
def carry_reverse(a):
    return Circuit().ccx[a,a+2,a+3].cx[a+1,a+2].ccx[a+1,a+2,a+3]

#ビットの合計
def sum(a):
    return Circuit().cx[a+1,a+2].cx[a,a+2] 

#10進数を2進数に
def tobinary(A):
    return bin(A)[2:] 

#2つの10進数を2進数に直して、桁を揃えて加算回路の順にビットを並べ替える
def digits(a,b): 
     aa = tobinary(a)  
     bb = tobinary(b)  
     alen = len(aa)  
     blen = len(bb)  
     maxlen = max(alen,blen) 
     if alen>blen: 
         bb = bb.zfill(alen) 
     elif blen>alen: 
         aa = aa.zfill(blen) 
  
     str = '' 
     for i in range(maxlen): 
         str += '0' + aa[maxlen-i-1] + bb[maxlen-i-1] 
     str += '0' 
     return str

#ビット文字列をXゲートを使ったデータ入力回路に変換
def tox(a): 
     cir = Circuit(len(a)) 
     for i in range(len(a)): 
         if a[i] == "1": 
             cir += Circuit().x[i] 
     return cir

#2進数を10進数に
def todecimal(A):
    return int(str(A),2) 

#加算回路から加算の結果のビット列だけを抜き出して結合
def getb(result): 
     str = result[-1] 
     digi = int((len(result)-1)/3) 
     for i in range(digi): 
         str += result[-2-i*3] 
     return todecimal(str)

#全てを組み合わせて加算回路に
def plus(a,b): 
     qubits = len(digits(a,b)) 
     cir1 = tox(digits(a,b)) 
     digi = int((len(digits(a,b))-1)/3) 

     cir2 = Circuit(qubits)     
     for i in range(digi): 
         cir2 += carry(i*3) 

     cir3 = Circuit(qubits).cx[-3,-2] + sum((digi-1)*3) 
  
     cir4 = Circuit(qubits) 
     for i in range(digi-1): 
         cir4 += carry_reverse((digi-i-2)*3) 
         cir4 += sum((digi-i-2)*3)
  
     result = (cir1 + cir2 + cir3 + cir4).m[:].run(shots=1) 
     return getb(result.most_common()[0][0])

量子計算を間に挟んでみました。

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('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@s % q + e) % q

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

# encryption
plain_bit1 = 1
plain_bit2 = 0

r1 = randint_from_gaussian(size=n)
r2 = randint_from_gaussian(size=n)
C1 = r1@A % q
C2 = r2@A % q

C21 = (r1@T - (q+1)/2*plain_bit1) % q
C22 = (r2@T - (q+1)/2*plain_bit2) % q

if C21 < 256 and C22 < 256:
    C23 = plus(int(C21),int(C22)) #ここが量子計算回路

print('[+] ciphertext')
print('C1 =\n', C1)
print('C2 =\n', C2)
print("")
print('C21 =\n', C21)
print('C22 =\n', C22)
print('C23 =\n', C23)
print("")

# decryption
p1 = (C1@s - C21) % q
p2 = (C2@s - C22) % q
p3 = ((C1+C2)@s - C23) % q
decrypted_bit1 = int((q+1)/4 < p1 < 3*(q+1)/4)
decrypted_bit2 = int((q+1)/4 < p2 < 3*(q+1)/4)
decrypted_bit3 = int((q+1)/4 < p3 < 3*(q+1)/4)

print("[+] decrypted_bit1 = %d" % decrypted_bit1)
print("[+] decrypted_bit2 = %d" % decrypted_bit2)
print("[+] decrypted_bit3 = %d" % decrypted_bit3)

しかもC1とC2がたまたま256より小さくできたときだけ計算してみます。

、、、僕のPCだとめちゃくちゃ時間かかります。しかしできた気がします。

n =  230 , q =  2053 , alpha =  8.0 
A =  [[ 481 1779 1174 ... 1603 1754 1911]
 [1287 1733   85 ...  710 1278 1909]
 [ 187 1482  168 ...  357  500 1978]
 ...
 [ 717  388  351 ... 1555 1658  898]
 [1947 1030 1638 ...  217 1418 1081]
 [ 390 1123 1511 ... 1118 1963 1514]] 


[+] secret key
s =
 [ 653  375  290   60  909   11 1605 1101 1615 1127 1659  205  645 1732
  888  592 1768  449  446  644 1409 1803   89  545   21  547  906  976
  674 1677 1950  401 1752 1497 1804  365 1195 2012 1696  394  845  893
   29 1760  547  531  934  470  866 1230  693  393 1234  144  995  777
 1374  208  567 1508 1160  483 1657 1776 1961  824 1411 1139 1299  863
 2049  572  666  436  490 1939  895  247 1019 1509   17   44  227 1262
 1574 1819 1139  821 1764  364 1372  361 1872  331 1976  805  629 1654
  528 1893 1009 1884  925 1426  541  218  585 1928 1523 1594 1408 1562
  219 1983 1803  229  729 1649   89 1534 1238  316 1030   96  938 1062
 1600 1106  219 1048 1411 1928 1457  659  687 1908 2009   27 1466 1472
 1270  146 1162  194  423 1634   25  753  672  413  846 1695 1008  771
 1078 1057  380  838  662  864  278  453 1252  213 2049  478 1850   78
 1533  530  718  382 2042  688 2050 1117 1538 1990  153 2051  874  396
 1125  822 1849  714 1856   23 1968 1558 1648 1715   51 1976 1663 1408
 1818  352 1305  684  998  475 1718  916  967  274 1014  904 1822  716
 1863  993 1697 1969 1614  432 1537  872 1545 1633 1364 1946  949 1489
  650 1739 1953  269 1113  649]
e =
 [  0.   1.  -6.  -1.  -3.  -1.  -2.  -4.  -0.   1.  -3.   2.   5.   1.
  -2.  -1.   8.   4.  -0.   2.  -2.  -4.   1.   1.   8.   5.  -2.  -0.
  -0.  -5.   2.   1.  -1.  -3.   1.  -3.  -1.  -0.  -2.  -4.  -4.   3.
  -1.  -2.  -6.  -1.  -5.   2.  -2.  -0.  -1.  -0.  -2.   1.  -4.  -1.
   6.  -2.  -2.   2.  -5.  -3.  -3.  -0.   5.   1.  -0.  -1.   3.   0.
   3.  -2. -10.  -2.   1.  -1.   1.   4.   6.   1.  -4.   1.  -2.   4.
  -5.   3.   3.  -1.  11.  -0.   3.   3.   2.  -0.   3.  -1.  -1.   3.
   3.  -3.  -2.  -3.  -1.   1.  -0.  -2.  -3.   2.   3.   3.   5.  -5.
   6.  -5.   0.  -3.   4.  -3.   4.  -2.  -1.  -2.   6.  -2.  -1.   2.
   0.   3.  -2.   1.  -1.  -0.   7.  -3.   3.  -2.  -1.  -3.   2.  -2.
   3.  -1.   2.   1.  -2.  -2.   2.   1.   3.   1.  -1.  -1.   1.  -4.
  -2.  -5.   1.  -1.  -0.  -2.   4.   1.   5.  10.  -4.  -4.  -4.  -1.
  -1.  -2.  -0.   1.   3.   0.   1.   1.  -5.   9.   1.  -0.  -2.  -4.
  -2.   2.   0.  -6.  -4.  -1.   0.   1.  -4.   1.  -1.  -0.   0.   1.
  -3.  -1.   4.   5.   3.  -5.  -0.  -3.   2.  -4.   3.   2.  -8.   1.
   5.  -2.  -3.   5. -10.   7.  -2.  -2.   1.   0.   0.   1.   1.  -0.
  -2.  -0.   3.   2.  -3.   4.]
[+] public key
T =
 [1.347e+03 1.000e+00 5.060e+02 8.590e+02 4.330e+02 4.610e+02 1.250e+02
 3.030e+02 1.965e+03 1.690e+03 1.979e+03 9.110e+02 1.495e+03 1.113e+03
 1.240e+03 1.130e+02 1.023e+03 1.963e+03 7.800e+01 1.635e+03 1.970e+03
 4.340e+02 3.920e+02 1.855e+03 9.500e+01 1.789e+03 1.350e+03 9.790e+02
 1.779e+03 1.184e+03 7.850e+02 9.450e+02 1.668e+03 4.800e+01 8.390e+02
 1.900e+01 1.587e+03 1.328e+03 1.728e+03 1.122e+03 1.480e+02 2.080e+02
 1.517e+03 1.356e+03 1.981e+03 9.350e+02 9.510e+02 2.980e+02 1.035e+03
 5.110e+02 7.350e+02 2.033e+03 1.131e+03 9.370e+02 1.505e+03 9.300e+01
 1.575e+03 1.740e+03 6.300e+01 7.380e+02 5.220e+02 4.810e+02 9.800e+01
 9.210e+02 1.902e+03 1.193e+03 1.958e+03 1.002e+03 1.935e+03 8.410e+02
 5.410e+02 9.100e+01 1.126e+03 1.014e+03 1.177e+03 2.420e+02 2.140e+02
 4.120e+02 1.358e+03 1.132e+03 5.890e+02 1.274e+03 8.670e+02 1.811e+03
 3.270e+02 1.648e+03 1.968e+03 5.370e+02 1.679e+03 1.304e+03 1.222e+03
 1.415e+03 1.340e+02 7.500e+01 1.603e+03 1.912e+03 7.800e+01 7.000e+02
 1.146e+03 5.120e+02 2.500e+01 1.495e+03 4.040e+02 1.494e+03 4.690e+02
 7.090e+02 1.893e+03 3.920e+02 1.580e+02 6.390e+02 1.967e+03 5.580e+02
 6.920e+02 1.571e+03 4.090e+02 2.980e+02 1.607e+03 6.950e+02 1.551e+03
 6.730e+02 1.128e+03 7.160e+02 1.772e+03 1.198e+03 9.580e+02 5.500e+01
 1.310e+03 1.925e+03 1.269e+03 1.786e+03 1.505e+03 3.560e+02 1.785e+03
 5.760e+02 1.670e+03 6.240e+02 6.670e+02 1.577e+03 1.795e+03 1.518e+03
 8.140e+02 5.940e+02 1.533e+03 1.975e+03 1.324e+03 2.250e+02 5.310e+02
 7.080e+02 1.584e+03 1.830e+02 6.710e+02 1.380e+02 1.733e+03 3.860e+02
 1.274e+03 4.440e+02 1.124e+03 1.380e+02 1.070e+03 2.031e+03 1.003e+03
 2.750e+02 1.421e+03 2.000e+01 1.434e+03 1.204e+03 7.740e+02 7.300e+02
 1.142e+03 1.529e+03 6.580e+02 1.979e+03 8.060e+02 2.120e+02 9.700e+01
 1.219e+03 6.000e+02 5.110e+02 1.880e+02 8.020e+02 1.526e+03 1.287e+03
 8.250e+02 8.520e+02 3.380e+02 1.136e+03 1.403e+03 1.680e+03 1.758e+03
 1.707e+03 8.530e+02 1.070e+03 1.320e+03 1.242e+03 2.043e+03 1.080e+02
 5.800e+01 8.960e+02 3.180e+02 1.930e+02 9.030e+02 1.890e+02 1.028e+03
 0.000e+00 3.070e+02 1.259e+03 1.531e+03 1.877e+03 5.870e+02 1.220e+03
 1.504e+03 5.900e+02 6.050e+02 2.230e+02 9.450e+02 5.000e+00 1.859e+03
 1.696e+03 8.080e+02 8.640e+02 1.983e+03 7.280e+02 1.099e+03 6.380e+02
 5.670e+02 1.839e+03 1.950e+03 1.473e+03 1.272e+03 1.289e+03]
^[[A[+] ciphertext
C1 =
 [1455. 2015.  625. 1443.  609. 1870.  299. 1864.  717.  990.  174. 1614.
 1767. 1617.  204.  499. 1947. 1457. 1101.  739.  419.  269. 1747.  741.
 1280. 1803. 1271.  513.  543.  425.  563. 1732.  837. 1332.  730.  722.
 2039.  249. 1367.  812.  866. 1529.   19.  908. 1163. 1123.  599. 2043.
  237.  927.  583. 1011.  293. 1616. 1572.  273. 1609.  594. 1352. 1820.
 1480.  141.  348.  182. 1047.  835. 1919.  663.  826. 1245.  729. 1123.
 1971. 1711. 1832. 1149. 1045. 1069.  466. 1422. 1889.  932. 2043.  906.
 1201.  503.  736. 1528.  383.  775. 1183. 1212.  595.  503.  296. 1875.
 1276. 1763.  773. 1364. 1306.  530.  176. 1416. 1802.  422. 1620.  395.
  794. 1991. 1866.  601. 1877. 1336. 1419.  469. 1469. 1058.  376.  104.
 1545.   31. 1285.  243. 1610.   89. 1382. 1286.   77. 1138.  563.  382.
  364.   41.  334. 1646.  500.  512. 1861.  744.  264. 1192. 1069.  273.
 1984. 1035.  393.  676.  347. 1168. 1898.  657.   58.  712. 1861. 1967.
  248.  523.  714.  685. 1091. 1134. 1451.  727.  997.  311. 1337.  470.
  623.  312.  538. 1988. 1705. 1962. 1667. 1124.  635.  846.  676. 1565.
 1605.  581.  929. 1604. 1973.  908.  643.  870.  962.  722. 1655. 1390.
  215. 1819. 1243. 1496.  597. 1583. 1555. 1962.  624.  183. 1701.  920.
 1802. 1311. 1661. 1158. 1295. 1666.  217.  339. 1559.   99. 1604.  802.
 1470.  899.  344. 1868. 1406.  332. 1482. 1785.  491. 1815. 1421.  507.
 1509. 1593.]
C2 =
 [1777.  142. 2051.  498.  990. 1562. 1178.  761. 1293.  907. 1153. 1840.
 2016.  851.  341. 1786.  782. 1379.  373. 1091. 1342.  189. 1836. 1179.
  770. 1811. 1130.  755.  262. 1697.  545. 1831.  488. 1417.  579.  589.
 1525.  531.  920. 1227. 1603.  999. 1510. 1300. 1472.  708.  254. 1281.
  109.  883. 1924.  335.  419.  133. 1033. 2041.   19.  243. 1356.  259.
  903. 1613.  474.  914. 1955. 1745.  835.  897.  842.  134.   58. 1917.
 1355.  632. 1196.  618. 1030. 1175. 1310.  177.  879.   33.  438. 1120.
 1083. 1536. 1206.  640. 1620. 1976.  834. 1765. 1320.  877. 1317.  222.
 1709. 1543. 1298.   49. 2009.  238.   96. 1637.  676. 1395. 1594. 1528.
 1169. 1271. 1777. 1042. 1999. 1247.  873.  130.  330.  458.  906. 1780.
 1480. 1292.  766.  544.  599. 1282.  450. 1960. 1147.  157. 1849. 1407.
  205. 1842. 1364. 1734. 1123.  480.  906. 1882. 1911. 1064. 1239. 1646.
 1616.  686.  523. 1116. 1185.  575.  475. 2012.  655.  998. 1386. 1735.
  673.  879.  108. 1371.   39.  758. 1007. 1369.   55.  793.  363. 1330.
  759.  218. 1460.  906. 1962. 1705. 1829. 1335. 1890. 1887.  490.  984.
  551.  971. 1679.  732.  441. 1362. 1859. 1868. 1452.  156.  308. 1296.
  325.  899.  633.  633. 1275. 2022. 1092. 1091.   70.  787.  503. 1087.
  202. 1783. 1654.  446. 1625.  126.  837.  111.  243. 1218. 1503. 1524.
  758. 1333. 1257.  351. 2007.  370. 1457.  450.  733.  912.  534.  630.
 1751.  860.]

C21 =
 136.0
C22 =
 83.0
C23 =
 219

[+] decrypted_bit1 = 1
[+] decrypted_bit2 = 0
[+] decrypted_bit3 = 1

1+0=1をLWE格子暗号+量子計算でものすごい計算量を使ってですができました。。。僕は数学はあまり得意ではないので得意な人はやってみてください。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方