臺灣博碩士論文加值系統

本研究的研究目的是比較雙方秘密數值是否相等，而在以往的安全多
方計算的研究，通常雙方的秘密數值經過協定之後，一個為告知方，另外
一個為被告知方，由告知方通知計算後之結果，而被告知方只能相信此訊
息。如果藉由半誠實的第三方可解決上述問題並減少計算量，但找到可以
信任的第三方是比較不容易的。
基於以上問題，本研究提出一新的秘密計算協定，在此協定下參與的
雙方(告知方、被告知方)可以算出彼此所擁有的秘密是否相同。如果不同，
此協定不會洩漏任何秘密值的資訊。本方案亦提供驗證機制，讓被告知方
能驗證告知方是否屬實。

The purpose of this study is to compare the equality of two secret values. Secure
multiparty computation in the previous study, usually through the protocol the
two sides, the one is announcer and the other one be told. The one be told by the
announcer who notified the results of verification, and the one be told only can
believe that the message. Through the semi-honest party can solve by the above
problems and reduce the computation required, but you can find a trusted third
party is not easy.
Based on the above problems, this study proposed in the framework of both the
secret of a new calculation of protocol, in this protocol the two parties (the one
is announcer, the other one be told) can calculate each have a secret are equal or
not. If different, this protocol does not leak any information about the secret
value.

摘要 IV
Abstract V
目錄 VI
圖目錄 VIII
表目錄 IX
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 3
1.3 研究貢獻 5
1.4 論文架構 6
第二章 相關研究 7
2.1 近代密碼學簡介 7
2.1.1 對稱式金鑰密碼系統(Symmetric Key Cryptosystem) 7
2.1.2 非對稱式金鑰密碼系統(Asymmetric Key Cryptosystem) 9
2.2 同態公開金鑰加密(Homomorphic Encryption) 10
2.2.1 加法同態 10
2.2.2 乘法同態 12
2.3 可換式加密(Commutative Encryption) 14
2.4 語意安全(Semantic security) 16
2.5 雙重同態加密(Doubly-homomorphic Encryption) 17
2.6 安全秘密計算(在雙方架構下) 20
2.6.1 Yao 的協定 20
2.7 安全秘密計算(藉由半誠實的第三方) 24
2.7.1 半誠實的第三方(Semi-trust Third Party) 24
2.7.2 Co-operative Private Equality Test 25
第三章研究方法 28
3.1 基礎協定設計 29
3.2 安全性 31
3.3 應用方面 33
第四章 雙方相等性驗證機制 35
4.1 協定設定 36
4.2 驗證方法 40
4.3 安全分析 42
第五章 效能分析 45
5.1 程式架構 46
第六章結論 50
參考文獻 51

[1]. D. Boneh, E. Goh, and K. Nissim. Evaluating 2-dnf formulas on ciphertexts. In Proceedings of Theory of Cryptography (TCC),2005, pp. 325-341.
[2]. A. Beimel, T. Malkin, S. Micali. The all-or-nothing nature of two-party secure computation. In Proceedings of CRYPTO 99, 1999, pp. 80-97.
[3]. E. Biham and A. Shamir, "Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, Vol.4, No.1, 1991, pp. 3-72.
[4]. N. Courtois and J. Pieprzyk: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, Asiacrypt ,2002, LNCS 2501, pp.267-287.
[5]. B. Chevallier-Mames, J. Sebastien Coron, N. McCullagh, D. Naccache, and M.Scott. Secure delegation of elliptic-curve pairing. Cryptology ePrint Archive, 2005, pp.24-35.
[6]. T. Chiang,W. Wang, J. Liau, and -S. Hsu. Secrecy of two-party secure computation. Lecture Notes in Computer Science, 2005, pp. 114-123.
[7]. W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Trans. Inform. Theory, vol. IT-22, 1976, pp. 472-492.
[8]. W. Du and Z. Zhan. A practical approach to solve secure multiparty computation problems. In Proceedings of New Security Paradigms Workshop, 2002, pp. 127-135.
[9]. T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In proceedings of CRYPTO, 1985, pp. 10-18.
[10].R. Fagin, M. Naor, P. Einkler, Comparing information without leaking it, Communications of the ACM 5 , 1996, pp.77-85.
[11]. C. Gentry. Fully homomorphic encryption using ideal lattices. In STOC ’09, ACM, 2009, pp. 169–178.
[12].O. Goldreich, S. Micali and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual
ACM Symposium on Theory of Computing (STOC), 1987, pp. 218-229.
[13]. S. Goldwasser and S. Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proceedings of the 14th ACM Symposium on Theory of Computing (STOC’82), 1982, pp. 365–377.
[14].R. Li and C. K.Wu, Co-operative private equality test. International Journal of Network Security, vol.1, no.3,2005, pp. 149-153.
[15].D. Naccache and J. Stern. A new public key cryptosystem based on higher residues. In Proceddings of Computer and Communications Security (CCS), ACM, 1998, pp. 59-66.
[16].C. P. Schnorr. E_cient Identi_cation and Signatures for Smart Cards. In Crypto '89, LNCS 435, 1990, pp. 235-251.
[17].P. Paillier. Public-key cryptosystem based on composite degree residuosity classes. In Proceedings of Eurocrypt 99, 1999, pp. 223-238.
[18].R. Rivest, A. Shamir, L. Adleman . A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 (2), 1978, pp. 120–126.
[19].J. Vaidya and C. Clifton. Leveraging the ”Multi” in Secure Multi-Party Computation. In Proceedings of the Workshop on Privacy in the Electronic Society, 2003, pp. 53-59.
[20].B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed. (Wiley, 1996).
[21].C. Yao, Protocols for secure computation. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS), 1982, pp. 160-164.
[22].F. Zhang, R. Safavi-Naini, and W. Susilo. An efficient signature scheme from bilinear pairings and its applications. In Proceedings of Public Key Cryptography (PKC) ,2004,pp. 277-290.