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


はじめに

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

https://jp.techcrunch.com/2019/01/28/eaglys/

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


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

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

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

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

https://www.slideshare.net/herumi/ss-59758244

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


準同型暗号

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

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

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

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

https://www.slideshare.net/herumi/x86-64study-shimov6


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: 法とする素数

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

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進数を量子計算で処理する

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

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格子暗号+量子計算でものすごい計算量を使ってですができました。。。僕は数学はあまり得意ではないので得意な人はやってみてください。