國立臺灣大學電機工程學系暨研究所雷欽隆2006-07-252018-07-062006-07-252018-07-062005-07-31http://ntur.lib.ntu.edu.tw//handle/246246/8054在量子現象被運用來提升計算速度 後，量子電腦的概念已逐漸形成，目前數 個量子位元(Quantum Bit)的電腦已經實驗 成功，而更多量子位元的電腦也正在設計 與驗證中。利用量子電腦之強大計算能 力，Peter Shor 提出可在多項式時間內解出 因數分解的量子演算法。目前密碼學中許 多重要的安全磐石，都將面臨被破解的夢 靨。不過，已有學者利用量子現象設計出 完美安全(Perfect Secure)的密碼技術，這 些新發明著實令密碼學家相當振奮。的 確，量子電腦的來臨對目前資訊安全造成 危機，但也是個轉機，它將為資訊安全與 密碼學開創全新的研究領域。世界各國學 術機構正展開量子計算的相關研究。 本研究計畫的主要標的是量子自動機 理論、量子演算法與量子密碼學。希望藉 由基礎理論之研究能對量子計算之特性與 能力能有更深一層之了解，進而設計出實 用之量子演算法。在量子演算法的設計 上，我們將以密碼應用為主。『水能載舟， 也能覆舟』，我們將探討有哪些傳統的密 碼演算法會因量子計算強大的能力而被破 解。另一方面，我們也將探討有哪些量子 特性可用來建構傳統計算機系統所無法達 成之密碼演算法。 我們將運用量子系統獨特的平行性 (Parallelism)與干涉性發展出比目前更為快 速的密碼分析法(Cryptanalysis)來破解因數 分解(Factorization)、離散對數(Discrete Logarithms)與對稱式密碼系統(Symmetric Cryptosystems)。其次，也將利用量子無 法複製(No-Cloning)之特性與測不準原理 設計出完美安全的高效率量子金鑰交換 (Quantum Key Exchange)協定、低成本之量 子錢幣(Quantum Money)與高效能量子秘 密分享機制(Quantum Secrecy-Sharing Schemes)。最後，本計畫將研究如何應用 量子的其他特性於密碼學中，例如疊加 (Superposition)現象、糾纏(Entanglement)現 象與量子運算之可逆性(Reversibility)等， 以期開發出創新的量子密碼演算法。希望 藉 由本計畫的實施，整合相關的研究資源， 進而提升國內在量子計算理論與演算法領 域的研究水平，迎頭趕上世界水準。Even since the introduction of quantum computation to the computing world, many practical quantum experiments have been successfully carried out. By taking advantage of the tremendous computing power of quantum computers, Peter Shor has shown that factor large numbers can be done in polynomial time. Public key cryptosystems, digital signature schemes as well as many other schemes that depended on this difficulty of factoring large numbers would become vulnerable. On the other hand,perfect secure cryptographic key distribution scheme based on quantum computing has been developed. Indeed, quantum computing will threaten the security of many classical cryptographic schemes, but it can also make classically infeasible computing tasks become feasible. Quantum computing has attracts the attentions of most leading scholars and research institute in the world. The main research targets of this project are quantum automata theory, quantum algorithms and quantum cryptography. By studying the theoretical foundations of quantum computing, we hope we can have a better understanding of the power of quantum computing and can design practical and effective quantum algorithms. In particular, we shall focus on what classically infeasible cryptographic tasks might become feasible using quantum computers. For example, can we break AES (Advanced Encryption Standard) efficiently using quantum computers? We still do not know. In particular, can we solve any NP-hard problem with polynomial-time quantum computation? (I.e., is NP a subset of QP?) Next, we are also interested in what new quantum objects might be created and adopted to construct secure cryptographic protocols that are impossible using classical computation models. We will investigate the possibility of adopting quantum parallelism for fast cryptanalysis. We will also study the possibility of adopting the non-cloning feature of quantum objects to design efficient algorithms for quantum money. In addition, we shall study what other quantum phenomena (such as superposition, entanglement, reversibility, etc.) might be useful for quantum algorithm design. Under this project, we expect to integrate the research potential in the nation and collaborate with leading researchers in the world.application/pdf151793 bytesapplication/pdfzh-TW國立臺灣大學電機工程學系暨研究所量子計算量子演算法量子自 動機理論量子密碼學Quantum ComputingQuantum AlgorithmQuantum AutomataQuantum Cryptographyreporthttp://ntur.lib.ntu.edu.tw/bitstream/246246/8054/1/932218E002103.pdf