论文→[ 科技论文 ]

古典用户端相容之量子抵抗与零知识设计

阅读量:02021-09-11作者:林德垣来源:资讯工程学研究所
首页 - 科技论文 - 本页网址:https://www.woailunwen.com/keji/72767/

研究生: 林德垣
研究生(外文): Te-Yuan Lin
论文名称: 古典用户端相容之量子抵抗与零知识设计
论文名称(外文): Quantum-Resistant and Zero-Knowledge Scheme for Classical-Client Compatibility
指导教授: 傅楸善傅楸善引用关係
指导教授(外文): Chiou-Shann Fuh
学位类别: 博士
校院名称: 国立台湾大学
系所名称: 资讯工程学研究所
学门: 工程学门
学类: 电资工程学类
论文种类: 学术论文
论文出版年: 2021
毕业学年度: 109
语文别: 英文
论文页数: 71
中文关键词: 同态加密、后量子密码、量子抵抗、量子计算、云计算安全、零知识证明
外文关键词: Cloud Computing Security、Homomorphic Encryption、Post-Quantum Cryptography、Quantum Computing、Quantum-Resistant、Zero-Knowledge Proof


现行以计算时间安全为基础的公开金钥密码系统,其安全保证假设来自于破解金钥密码所需时间超过金钥使用寿命,以及破解攻击所耗费资源远高于讯息内容本身价值之上。但随著云计算资源的不断发展增强,应用云计算服务的方式不再只限于摩尔定律的古典计算,一个仅具有数十GFLOPS运算能力的普通用户装置,可以透过任务外包给云平台服务商所提供的人工智能预测和平行运算方式,提升至数百上千个TFLOPS运算能力;更甚者,在量子运算出现后,现有商用计画规模的量子电脑云端运算平台服务,已在特定问题领域达到相当于超级电脑的PFLOPS计算效果。Shor算法已证明透过理想的量子电脑,可于有效的多项式时间内通过遍历走访方式获得质数因子而破解密钥。试想若窃听者外包攻击任务予云端量子电脑,仅依赖于RSA计算複杂度的加密安全将会越来越不可信赖。量子通讯传输网路的提出,虽可以根本上解决窃听问题,但这需要互联网端至用户端网路基础协定全面通讯量子化的配合,并非道近易从之举措。在本研究中,首先简介当代量子电脑能力,整理分析数种已被提出对抗量子电脑攻击的方法,这些方法可区分为两大方向系,分别是以量子物理特性设计的量子密码网路传输;和延伸自传统密码学加入抗量子设计,且可应用于非具量子处理能力电脑之后量子密码学。本论文研究兴趣侧重于后者应用之方法探讨,即用户端不须预先制备测量量子比特的量子态,或执行一些不相容于目前用户端能力的特定量子任务工作,之后进一步提出非单纯依赖计算複杂度保护,并加入零知识证明特性的设计步骤演算,结合全同态加密方式来达到可具抵抗量子攻击的资料隐私保护方案。最后,透过实际操作云端量子电脑进行模拟运算实验,评估窃听者现阶段若透过量子电脑进行攻击时的可窃取能力、以及引入我们的量子抵抗设计后的安全改善分析。


The current public key cryptography systems are implemented based on computational security, where its security commitment comes from the time required of exhaustive key search exceeds that of the crypto key validity, and the attacking resource cost outweighs the value of the message itself. However, with the continuous growth of cloud computing resources, the computing power that cloud computing services can bring no longer conforms to the limit set by Moore’s law. For example, an ordinary client device of mere tens of GFLOPS can enormously augment its computing power exponentially to hundreds of TFLOPS and more by outsourcing its workload to an external cloud services provider with artificial intelligence prediction and parallel computing capability. Moreover, some cloud services giants have paved the way to commercializing quantum computing technology and have solved some domain-specific problems with an efficiency equivalent to PFLOPS of the supercomputer level. Shor’s algorithm formally proved that a quantum computer could traverse the key of factoring problems in polynomial time. Hence, the computational intractability of RSA has gradually unreliable bit by bit. Quantum communication can fundamentally solve the eavesdropping problem but includes many challenges, such as lacking comprehensive quantum network protocols and universal end-point quantum signal devices, which have a long way to go. This study proposes a non-computational complexity scheme based on zero knowledge and fully homomorphic encryption to achieve quantum-safe communication for classical clients without prior quantum ability to measure qubits states nor executing incompatible quantum tasks. Finally, we perform IBM’s cloud quantum computer to run Shor’s factorization to evaluate how “fast” it can be now in the experiments; conduct the performance impact and the security analysis of our proposed scheme regarding its quantum-resistant capability.


[1] Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5): 1484–1509, arXiv:quant-ph/9508027v2
[2] Kleinjung T. et al. (2010). Factorization of a 768-Bit RSA Modulus. In: Rabin T. (eds), Advances in Cryptology. Lecture Notes in Computer Science, volume 6223. Springer, Berlin, Heidelberg
[3] Pritscher, C. P. (2001). Quantum learning beyond duality. Retrieved from https://books.google.com.tw/books?id=1-McfrykKkoC pg=PA4 lpg=PA4 dq=quantum a billion times faster source=bl ots=vkeWDFiFIc sig=ACfU3U2E2O0GGAl3icBlu5e5S8K0E_wuhQ hl=zh-TW sa=X ved=2ahUKEwjn8LrAr5rhAhUEGKYKHW0pAuEQ6AEwBHoECAgQAQ#v=onepage q=quantum a billion times faster f=false
[4] Levitan, B. M. (1994). Hilbert space, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
[5] Wiesner, S. (1983). Conjugate coding. ACM Sigact News. 1983;15(1): 78–88. doi:10.1145/1008908.1008920
[6] Bennett, C. H. Brassard, G. (1984). Quantum cryptography: Public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, volume 175, 8. New York
[7] Bennett, C. H. Brassard, G. (2014, December 4). Quantum cryptography: Public key distribution and coin tossing. Theoretical Computer Science. Theoretical Aspects of Quantum Cryptography – celebrating 30 years of BB84. 560, Part 1: 7–11. doi:10.1016/j.tcs.2014.05.025
[8] Diamanti, E., Lo, H.-k, Qi, B. Yuan, Z. (2016). Practical challenges in quantum key distribution. Quantum Inf. 2, 16025. doi:10.1038/npjqi.2016.25
[9] Huang, D., Huang, P., Lin, D. Zeng, G. (2016). Long-distance continuous-variable quantum key distribution by controlling excess noise. Scientific reports, 6, 19201. doi:10.1038/srep19201
[10] Mailloux, L. O. et al. (2016, July 21). Quantum Key Distribution: Boon or Bust? CSIAC, Retrieved from https://www.csiac.org/journal-article/quantum-key-distribution-boon-or-bust/
[11] Arrighi, P. Salvail, L. (2006). Blind quantum computation. Int. J. Quantum Inform. 4, 883–898
[12] Childs, A. M. (2005). Secure assisted quantum computation. Quantum Info. Comput. 5, 456–466
[13] Broadbent, A., Fitzsimons, J. Kashefi, E. (2009). Universal blind quantum computation. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 517–526
[14] Fitzsimons, J. Kashefi, E. (2012). Unconditionally verifiable blind computation. arXiv:1203.5217
[15] Fitzsimons, J. (2017). Private quantum computation: an introduction to blind quantum computing and related protocols. Quantum Inf. 3, 2056-6387. doi: 10.1038/s41534-017-0025-3
[16] NIST. (2016, March 7). Post-Quantum Cryptography. Retrieved from http://csrc.nist.gov/groups/ST/post-quantum-crypto/
[17] Quisquater, J. -J., Guillou, L. C., and Berson, T. A. (1990). How to Explain Zero-Knowledge Protocols to Your Children. Advances in Cryptology – CRYPTO '89: Proceedings. Lecture Notes in Computer Science, volume 435, 628–631. doi:10.1007/0-387-34805-0_60
[18] Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1), 186–208. doi:10.1137/0218012
[19] Damgård I. (2000). Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In: Preneel B. (eds), Advances in Cryptology — EUROCRYPT. Lecture Notes in Computer Science, volume 1807. Springer, Berlin, Heidelberg
[20] Blum M., Feldman P., and Micali S. (1988). Non-Interactive Zero-Knowledge and Its Applications. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), 103–112. doi:10.1145/62212.62222
[21] Groth J. (2006). Simulation-sound NIZK proofs for a practical language and constant size group signatures. In ASIACRYPT, volume 4248 of Lecture Notes in Computer Science, 444–459
[22] Groth J., and Sahai A. (2008). Efficient non-interactive proof systems for bilinear groups. In EUROCRYPT, volume 4965 of Lecture Notes in Computer Science, 415–432
[23] Blazy O. (2012). Interactive and Non-Interactive Proofs of Knowledge (Doctoral dissertation). Retrieved from https://tel.archives-ouvertes.fr/tel-00768787/file/thesis.pdf
[24] De Santis A., Okamoto T., and Persiano G. (1994). Zero-knowledge proofs of computational power in the shared string model. In: Pieprzyk J., Safavi-Naini R. (eds), Advances in Cryptology — ASIACRYPT'94. Lecture Notes in Computer Science, volume 917. Springer, Berlin, Heidelberg
[25] Chailloux A., Ciocan D.F., Kerenidis I., and Vadhan S. (2008). Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model. In: Canetti R. (eds), Theory of Cryptography. TCC. Lecture Notes in Computer Science, volume 4948. Springer, Berlin, Heidelberg
[26] Martins P., Sousa L., and Mariano A. (2017). A Survey on Fully Homomorphic Encryption: An Engineering Perspective. ACM Comput. Surv. 50(6), Article 83, 33 pages. doi:10.1145/3124441
[27] Pass R. (2004). Alternative Variants of Zero-Knowledge Proofs. [PDF file] (Licentiate Thesis). Stockholm: KTH Numerical Analysis and Computer Science. Retrieved from http://www.cs.cornell.edu/~rafael/papers/raf-lic.pdf
[28] Unruh D. (2016). Computationally Binding Quantum Commitments. In: Fischlin M., Coron JS. (eds), Advances in Cryptology – EUROCRYPT. Lecture Notes in Computer Science, volume 9666. Springer, Berlin, Heidelberg
[29] IBM Qiskit. (2019). Getting started with Qiskit. Retrieved from https://qiskit.org/
[30] D-Wave System Documentation. (n.d.). What is Quantum Annealing?. Retrieved from https://docs.dwavesys.com/docs/latest/c_gs_2.html
[31] Babukhin, D. V., Zhukov, A. A., and Pogosov, W. V. (2020). Hybrid digital-analog simulation of many-body dynamics with superconducting qubits. American Physical Society, 101(5):14, doi:10.1103/PhysRevA.101.052337
[32] Shaffer, R., Megidish, E., Broz, J. et al. (2021). Practical verification protocols for analog quantum simulators. npj Quantum Inf 7, volume 46, doi:10.1038/s41534-021-00380-8
[33] Lamata L., Parra-Rodriguez A., Sanz M., and Solano E. (2018) Digital-analog quantum simulations with superconducting circuits, Advances in Physics: X, 3(1), doi: 10.1080/23746149.2018.1457981
[34] Mostame, S., Huh, J., Kreisbeck, C., Kerman, A. J., Fujita, T., Eisfeld, A., and Aspuru-Guzik, A. (2016) Emulation of complex open quantum systems using superconducting qubits, Quantum Information Processing, volume 16, doi: 10.1007/s11128-016-1489-3
[35] Preskill, J. (2015). Lecture Notes for Ph219/CS219: Quantum Information and Computation Chapter 5, California Institute of Technology, Pasadena CA. Retrieved from http://theory.caltech.edu/~preskill/ph219/chap5_13.pdf
[36] Quantum logic gate. (n.d.). In Wikipedia. Retrieved October 14, 2020, Retrieved from https://en.wikipedia.org/wiki/Quantum_logic_gate
[37] Wang, D. (2015). Classifying Simulators [PowerPoint Slides], Institute for Quantum Science and Technology, Calgary. Retrieved from https://slideplayer.com/slide/5837344/
[38] Qiskit/qiskit-tutorials. (n.d.). Summary of Quantum Operations. Retrieved from https://github.com/Qiskit/qiskit-tutorials/blob/master/tutorials/circuits/3_summary_of_quantum_operations.ipynb
[39] Quantum Protocols and Quantum Algorithms. (n.d.). Shor's Algorithm. Retrieved from https://qiskit.org/textbook/ch-algorithms/shor.html
[40] Lanzagorta, M., and Uhlmann, J. (2008). Quantum Information and Computation VI: Is quantum parallelism real?, SPIE, 16, doi: 10.1117/12.778019
[41] Quantum Protocols and Quantum Algorithms. (n.d.). Grover's Algorithm. Retrieved from https://qiskit.org/textbook/ch-algorithms/grover.html
[42] Hartnett, K. (2018, June 21). Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve. Quanta Magazine. Retrieved from https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
[43] Mavroeidis, V., Vishi, K., Zych, M. Jøsang, A. (2018). The Impact of Quantum Computing on Present Cryptography. International Journal of Advanced Computer Science and Applications. 9. doi:10.14569/IJACSA.2018.090354
[44] Hariss, K., Noura, H., Samhat, A.E., and Chamoun M. (2018). Design and realization of a fully homomorphic encryption algorithm for cloud applications. In: Cuppens N, Cuppens F, Lanet JL, Legay A, Garcia-Alfaro J (eds), Risks and security of internet and systems. Springer International Publishing, Cham, 127–139. doi: 10.1007/978-3-319-76687-4_9
[45] Hariss, K., Noura, H. Samhat, A.E. (2020). An efficient fully homomorphic symmetric encryption algorithm. Multimed Tools Appl, volume 79, 12139–12164. doi:10.1007/s11042-019-08511-2
[46] Santhiya, B. Anitha Kumari, K. (2020). Analysis on DGHV and NTRU Fully Homomorphic Encryption Schemes. In: Kumar L., Jayashree L., Manimegalai R. (eds), Proceedings of International Conference on Artificial Intelligence, Smart Grid and Smart City Applications. AISGSC 2019 2019. Springer, Cham. doi:10.1007/978-3-030-24051-6_61
[47] Alabdulatif, A. Kaosar, M. (2016). Privacy preserving cloud computation using Domingo-Ferrer scheme. Journal of King Saud University - Computer and Information Sciences, 28(1), 27-36. doi:10.1016/j.jksuci.2015.10.001
[48] IBM Quantum. (2020). In this paper we used ibmq_poughkeepsie, which is one of the IBM Quantum Canary Processors. Retrieved from https://quantum-computing.ibm.com/
[49] Qiskit Documentation. (n.d.). Source code for qiskit.algorithms.factorizers.shor. Retrieved from https://qiskit.org/documentation/_modules/qiskit/algorithms/factorizers/shor.html
[50] Syverson, P. F. Oorschot, P. C. (1996). A Unified Cryptographic Protocol Logic. doi:10.21236/ada464967
[51] Hartnett, K. (2019, July 18). Getting Started with Qiskit, Retrieved from https://www.quantamagazine.org/does-nevens-law-describe-quantum-computings-rise-20190618/#:~:text=Neven's%20law%20states%20that%20quantum,supremacy%20is%20around%20the%20corner
[52] Yoshida, H. (2019, June 25). Moore’s Law Is Replaced by Neven's Law for Quantum Computing, Retrieved from https://community.hitachivantara.com/s/article/moores-law-is-replaced-by-nevens-law-for-quantum-computing
[53] Zoufal, C., Lucchi, A. Woerner, S. (2019). Quantum Generative Adversarial Networks for learning and loading random distributions. npj Quantum Inf, 2019, 5(1): 103. doi:10.1038/s41534-019-0223-2
[54] Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st ACM Symposium on Theory of Computing - STOC 2009, pp. 169-178. ACM, New York. doi:10.1038/s41534-019-0223-2
[55] Bonnoron, G. (2018). A journey towards practical fully homomorphic encryption. Cryptography and Security [cs.CR]. Ecole nationale supérieure Mines-Télécom Atlantique, English, 2018, ffNNT: 2018IMTA0073ff. fftel-02011668
[56] Chao, F., Yang X. (2014). Fast key generation for Gentry-style homomorphic encryption. The Journal of China Universities of Posts and Telecommunications, 21(6): 37–44. doi:10.1016/S1005-8885(14)60343-5
[57] Zhang, Y., Liu, R. Lin, D. (2017, September). Improved Key Generation Algorithm for Gentry’s Fully Homomorphic Encryption Scheme. In: Kim H., Kim DC. (eds), Information Security and Cryptology – ICISC 2017. ICISC 2017. Lecture Notes in Computer Science, 2018, 10779: 93-111 Springer, Cham. doi:10.1007/978-3-319-78556-1_6

累计有19527人觉得此论文有用

免责声明

古典用户端相容之量子抵抗与零知识设计
本文内容整理自网络,有修改,版权归原作者所有。如有侵权,我们将立即更正或删除相关内容。
联系邮箱 webmaster(#at)woailunwen.com [ (#at)改为@ ]
同态加密 后量子密码 量子抵抗 量子计算 云计算安全 零知识证明

网友回答

还没有人提问古典用户端相容之量子抵抗与零知识设计,现在提问沙发就是你的!
点击加载更多