臺灣博碩士論文加值系統

隨著資訊的蓬勃發展，資料在網路上的傳輸也越來越頻繁，當遠端雙方需要做秘密通訊時，則必須事先擁有一把共同的密鑰，傳送方才得以先對資料加密，接收方也得以對密文解密，若雙方事先沒有這把共同的密鑰時，就必須透過公鑰密碼系統(public key cryptosystem)先交換出這把共同密鑰。

但是隨著電腦運算速度的不斷提升，密鑰的長度也被迫不斷增長，以延長被破解的時間，未來若量子電腦成功的被發展出來，即使密鑰長度增長，仍然無法抵擋量子電腦快速的平行運算能力，而迅速被破解，所幸Bennett和Brassard在1984年提出BB84的量子密鑰分配協定，配合one-time-pad加密方式，即使是運算能力強大的量子電腦也無法破解，因而使得資料通訊安全再度獲得保障。

自從Bennett和Brassard提出BB84的量子密鑰分配協定後，通訊安全便提升到一個新的里程碑，由於量子的測不準定理(uncertainty principle)，因此可以確保密鑰分配的安全性，但是BB84的協定其密鑰分享效率只有50%，也就是會有一半的光子訊息白白被浪費掉，為了減少光子訊息的浪費，本論文中提出兩個新的方法，第一種稱為：基底機率調整(Bases Probability Adjustment：BPA) 之量子密鑰分配協定，第二種則為：預設基底之量子密鑰分配協定，並且證明可以在不影響原BB84協定安全性之下，有效的提升量子密鑰分享的效率。

本論文的另一個研究主題為：量子模糊傳送協定，主要介紹Crépeau在1994年所提出的1-out-of-2量子模糊傳送協定，以及說明如何使用量子位元託付(quantum bit commitment)來防止接收者的儲存式攻擊(storage attack)，並提出以分段的方式來達成1-out-of-2、1-out-of-n、m-out-of-n的量子模糊傳送協定。

Due to the rapid development of information technology, data communication is more frequent in the network. When two parties need to communicate in secret, they have to share a secret key in advance. The sender encrypts data, and then delivers it to the receiver. The receiver decrypts it using the same secret key. They can share the secret key by public key cryptography.

In order to against breaking, the length of the secret key has to be increased. However, even the length of the secret key is long, they still cannot against the attacks of quantum computers. Fortunately, Bennett and Brassard in 1984 proposed a BB84 quantum key distribution protocol, which is secure from the attack of quantum
computers.

Since BB84 protocol, the communication security has stepped forward to a new milestone. However, the key sharing efficiency is only 50% in BB84 protocol. Therefore, this master thesis will propose two new protocols: The first one is Bases Probability Adjustment (BPA); The second one is Preset Bases Quantum Key Distribution Protocol. These two protocols can improve the key sharing efficiency without affecting the security of BB84.

Another research topic of this master thesis is quantum oblivious transfer. It will introduce Crépeau’s 1-out-of-2 quantum oblivious transfer protocol in 1994, and show how to use quantum bit commitment mechanism to prevent the storage attack. This thesis also proposes 1-out-of-2, 1-out-of-n, and m-out-of-n quantum oblivious transfer protocols.

中文摘要............................................. iv
ABSTRACT............................................. v
致謝................................................. vi
目次................................................ vii
表目錄............................................... ix
圖目錄................................................ x
第一章 緒論............................................ 1
1.1 研究背景........................................... 1
1.2 研究動機與目的...................................... 1
1.3 章節概要........................................... 3
第二章 文獻探討......................................... 4
2.1 量子訊息簡介........................................ 4
2.2 光子的物理特性...................................... 5
2.3 BB84 量子密鑰分配協定................................ 8
2.3.1 協定............................................. 8
2.3.2 效率分析.......................................... 8
2.3.3 安全性分析........................................ 9
2.4 B92 量子密鑰分配協定.................................10
2.4.1 協定..............................................10
2.4.2 效率分析.......................................... 11
2.4.3 安全性分析........................................ 11
2.5 模糊傳送協定簡介.................................... 14
2.6 Crépeau 之量子模糊傳送協定........................... 15
第三章 提升量子密鑰分配協定之效能.......................... 19
3.1 基底機率調整之量子密鑰分配協定......................... 19
3.1.1 協定............................................. 19
3.1.2 公式推導.......................................... 20
3.1.3 實例驗證.......................................... 21
3.1.4 效率分析.......................................... 22
3.1.5 安全性分析......................................... 22
3.2 預設基底之量子密鑰分配協定............................. 24
3.2.1 協定.............................................. 25
3.2.2 公式推導........................................... 26
3.2.3 實例驗證........................................... 27
3.2.4 效率分析........................................... 28
3.2.5 安全性分析......................................... 29
第四章 分段式之量子模糊傳送協定............................. 32
4.1 1 out of 2 協定...................................... 33
4.2 1 out of n 協定...................................... 35
4.3 m out of n 協定...................................... 38
4.4 安全性分析............................................ 41
第五章 結論與未來研究方向.................................. 44
5.1 結論................................................. 44
5.2 未來研究方向.......................................... 44
參考文獻.................................................. 46

[1] 李南逸、張庭魁，量子密鑰交換協定效能提升之研究，電腦學刊(Journal Of
Computers) 第十六卷 第三期, Vol.16, No.3, pp.19-25, September 2004.
[2] 李南逸、張庭魁，預設基底之量子密鑰交換協定，樹德科技大學 2005 資通技
術管理與應用會議, June 2005.
[3] A. Einstein, B. Podolsky, N. Rosen, "Can Quantum-Mechanical Description of Physical Reality be Considered Complete?" Physical Review 47, pp.777-780, 15 May 1935.
[4] A. Ekert, "Quantum Cryptography Based on Bell's Theorem." Physical Review Letters, Vol.67, No.6, pp.661-663, 5 August 1991.
[5] A. Kent, "Quantum Bit String Commitment." Physical Review Letters, Vol.90, No.23, pp.237901, 2003.
[6] A. Kent, "Secure Classical Bit Commitment using Fixed Capacity Communication Channels." quant-ph/9906103, 2004.
[7] A. Kent, "Unconditionally Secure Bit Commitment." Physical Review Letters, Vol.83, pp.1447-1450, 1999.
[8] B. Julsgaard, J. Sherson, J.I. Cirac, J. Fiurášek, and E.S. Polzik, "Experimental Demonstration of Quantum Memory for Light." Nature pp.432-482, 2004.
[9] C. Crépeau, "Equivalence Between Two Flavours of Oblivious Transfers." Lecture Notes In Computer Science, Vol.293, pp.350-354, 1987.
[10] C. Crépeau, "Quantum Oblivious Transfer." Journal of Modern Optics, Vol.41, No.12, pp.2455-2466, 1994.
[11] C. Crépeau and J. Kilian, "Achieving Oblivious Transfer Using Weakened Security Assump." Proceedings of 29th IEEE Symposium on the Foundations of Computer Science, pp.42-52, October 1988.
[12] C. Crépeau, P. Dumais, D. Mayers, L. Salvail, "Computational Collapse of Quantum State with Application to Oblivious Transfer." In Proceedings of TCC 2004, vol.2951 of Lecture Notes in Computer Science, pp.374-393, 2004.
[13] C.E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, Vol.27, pp.379-423 and 623-656, July and October 1948.
[14] C.E. Shannon, "Communication Theory of Secrecy Systems." The Bell Labs Technical Journal, Vol.28, No.4, pp.656-715, May 1949.
[15] C.H. Bennett, "Quantum Cryptography Using Any Two Non-orthogonal States." Physical Review Letters, Vol.68, pp.3121-3124, May 1992.
[16] C.H. Bennett, F. Bessette, G. Brassard, L. Salvail and J. Smolin, "Experimental Quantum Cryptography." Journal of Cryptology, Vol.5, No.1, pp.3-28, 1992.
[17] C.H. Bennett and G. Brassard, "Quantum Cryptography: Public Key Distribution and Coin Tossing." Proceedings of IEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, pp.175-179, December 1984.
[18] C.H. Bennett, G. Brassard, C. Crépeau and M.H. Skubiszewska, "Practical Quantum Oblivious Transfer." Proceedings of Crypto'91, Lecture Notes in Computer Science, Vol.576, pp.351366, April 1992.
[19] C.H. Bennett, G. Brassard, C. Crépeau and Ueli Maurer, "Generalized Privacy Amplification." IEEE Transaction on Information Theory, Vol.41, No.6, pp.1915-1923, November 1995.
[20] C.H. Bennett, G. Brassard and J.-M. Robert, "Privacy Amplification by Public Discussion." SIAM Journal on Computing, Vol.17, No.2, pp.210-229, April 1988.
[21] C.H. Bennett, G. Brassard and N. David Mermin, "Quantum Cryptography without Bell's Theorem." Physical Review Letters, Vol.68, pp.557-559, 1992.
[22] C.H. Bennett, G. Brassard and S. Breidbart, "Quantum Cryptography II: How to re-use a one-time pad safely even if P = NP." unpublished manuscript available from the authors, November 1982.
[23] Christof Zalka, John Proos, "Shor's Discrete Logarithm Quantum Algorithm for Elliptic Curves." QIC Vol.3 No.4, pp.317-344, 2003.
[24] C.N. Yang and C.C. Kuo, "Enhanced Quantum Key Distribution Protocols Using BB84 and B92." Proceedings of the 2002 International Computer Symposium, Vol.2, pp.951-959, December 2002.
[25] D. Gottesman, I. Chuang, "Quantum Digital Signatures." Technical report, available at http://arxiv.org/abs/quant-ph/0105032, 2001.
[26] D. Mayers, "Unconditionally Secure Quantum Bit Commitment is Impossible." Physical Review Letters, Vol.78, pp.3414-3417, 1997.
[27] E.G. Rieffel and W. Polak, "An Introduction to Quantum Computing for Non-Physicists." ACM Computing Surveys, Vol.32, No.3, pp.300-335, September 2000.
[28] G. Brassard, C. Crépeau, J.-M. Robert, "All-or-Nothing Disclosure of Secrets." Proceedings on Advances in cryptology - CRYPTO '86, pp.234-238, 1987.
[29] G. Brassard, C. Crépeau, R. Jozsa and D. Langlois, "A quantum bit commitment scheme provably unbreakable by both parties." In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp.362-371, November 1993.
[30] Gilbert S. Vernam, "Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications", Journal of the IEEE, Vol.55, pp.109-115, 1926.
[31] H. Zbinden, J.D. Gautier, N. Gisin, B. Huttner, A. Muller and W. Tittel, "Interferometry with Faraday Mirrors for Quantum Cryptography." Electronics Letters, Vol.33, pp.586-588, 1997.
[32] J. McKeever, A. Boca, A.D. Boozer, R. Miller, J.R. Buck, A. Kuzmich, H.J. Kimble, "Deterministic Generation of Single Photons from One Atom Trapped in a Cavity." Science 303: pp.1992-1994, February 2004.
[33] L.K. Grover, "A Fast Quantum Mechanical Algorithm for Database Search." In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp.212–219, May 1996.
[34] Lomonaco, Samuel J., "A Quick Glance at Quantum Cryptography." Cryptologia, Vol.23, No.1, pp.1-41, January 1999. (quant-ph/9811056)
[35] Lucien Hardy and Adrian Kent, "Cheat Sensitive Quantum Bit Commitment." Physical Review Letters, Vol.92, No.15, pp.157901, April 2004.
[36] Mark Osjkin, Frederic T. Chong and Isaac L. Chuang, "A Practical Architecture for Reliable Quantum Computers." IEEE Computer, pp.79-87, January 2002.
[37] Miloslav Dusek, Ondrej Haderka, Martin Hendrych, "Generalized Beam-Splitting Attack in Quantum Cryptography with Dim Coherent States." Optics Communications, Vol.169, pp.103-108, 1 October 1999.
[38] Moni Naor and Benny Pinkas, "Computationally Secure Oblivious Transfer." Crypto 99, 1999.
[39] M.O. Rabin, "How to Exchange Secrets by Oblivious Transfer.” Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
[40] Nielsen, Michael A., and Isaac L. Chuang. "Quantum Computation and Quantum Information." Cambridge University Press, Cambridge, UK, 2000.
[41] P.W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." Proc. 35th Annual Symp. on Foundations of Computer Science, pp.124-134, November 1994.
[42] P.W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." SIAM J. Computing Vol.26, pp.1484-1509, 1997.
[43] P.W. Shor and John Preskill, "Simple Proof of Security of the BB84 Quantum Key Distribution Protocol." Physical Review Letters, Vol.85, pp.441-444, 2000.
[44] R. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signature and Public Key Cryptosystems." Communications of the ACM, Vol.21, Issue 2, pp.120-126, February 1978.
[45] Shimon Even, Oded Goldreich, Abraham Lempel, "A Randomized Protocol for Signing Contracts." Communications of the ACM, Vol.28, No.6, pp.637-647, 1985.
[46] S.J.D. Phoenix and P.D. Townsend, "Quantum Cryptography: Protecting our future network with quantum mechanics." Cryptography and Coding: 5th IMA Conference, pp.112-131, December 1995.
[47] S.J.D. Phoenix, S.M. Barnett, P.D. Townsend and K.J. Blow, "Multi-User Quantum Cryptography on Optical Networks." Journal of Modern Optics, Vol.42, No.6, pp.1155-1163, 1995.
[48] S. Wiesner, "Conjugate Coding." manuscript written cirac 1970, unpublished until it appeared in Sigact News, Vol.15, No.1, pp.78-88, 1983.
[49] Tatsuaki Okamoto, Keisuke Tanaka, Shigenori Uchiyama "Quantum Public-Key Cryptosystems." CRYPTO 2000, Vol.1880, pp.147-165, 2000.
[50] T. El Gamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms." IEEE Trans. on Information Theory, Vol.31, pp.469-472, 1985.
[51] V.S. Miller, "Use of Elliptic Curve in Cryptography." Advance in
Cryptology-Crypto '85, pp.417-426, 1985.
[52] W. Diffie and M. Hellman, "New Directions in Cryptography." IEEE Transactions on Information Theory, Vol.22, Issue 6, pp.644-654, November 1976.
[53] W.K. Wootters and W.H. Zurek, "A Single Quantum Cannot Be Cloned." Nature, Vol.299, pp.802-803, October 1982.
[54] W.Y. Hwang, I.G. Koh and Y.D. Han, "Quantum Cryptography without public announcement bases." Physical Letter A, Vol.244, pp.489-494, 1998.
[55] Z. Chen and H. Zhu, "Quantum m-out-of-n Oblivious Transfer." quant-ph/0311039, 2004.