劉邦鋒臺灣大學：資訊工程學研究所蕭睆文Hsiao, Huan-WenHuan-WenHsiao2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/53931傳統密碼學為了克服安全通道(secure channel)的不存在而產生了非對性的加解密系統。然而在這個系統下，我們唯一不信任的只是竊取資料的第三者，對於兩造雙方我們則給予完全的信任而與之合作。可是在真實的世界中，或許是商場上的競爭我們必需合作謀求最大利益，但卻又不時想從接收到的資料中盡其可能的獲取最多的資訊；也或許是兩造雙方都是可信的，但我們不知道對方的電腦是否中毒了，是否系統被植入後門而被竊取合作計劃目的之外的額外資訊。往往連對方都是不可完全信任的。 在現段的研究中，已經有許多的演算法能夠在雙方不完全透露自己資訊的情況下達到彼此的合作的目的，但並沒有太多有系統的分析方式能明確的比較出何種演算法較好，可以安全到什麼程度？而本論文的目的即在建立一個，能有系統的分析多人合作私密計算演算法的安全性，進而量化它，並找到演算法中可以安全達到的最高程度。In traditional cryptography, if we want to do some private cooperative computation, one should totally trust the others, and reveals all of this private information to do the co-computation. These algorithms prevent only malicious third-party from security risk. However, the co-worker is not to be trusted in many real case. Nowadays, many algorithms have developed to overcome this risk. Co-operative can be achieved without reveal all of the information one have. This framework is to build an analytical model to measure the security of such algorithms and to find their degree of security.Title Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 Copyright Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Approval Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii ACKNOWLEDGEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . iii 中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix CHAPTER I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A motivating example . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . 7 II. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Modular Arithmetic . . . . . . . . . . . . . . . . . . . 9 2.1.2 Field . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.3 Vector Space . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.4 Row Reduction . . . . . . . . . . . . . . . . . . . . . 10 2.2 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Information Theorem . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Survey and Comparison . . . . . . . . . . . . . . . . . . . . . . 21 III. Degree of Freedom . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . 24 vii 3.2 The Problem of Using Degree of Freedom . . . . . . . . . . . . 27 IV. Average Measurement . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . 29 4.2 Algorithm and Complexity . . . . . . . . . . . . . . . . . . . . 30 4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 V. Practical Issues in Using Average Measurement . . . . . . . . . 43 5.1 The probability to generate a matrix with a good average measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 How to generate matrices with the best average measurement . 46 VI. Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . 50 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2.1 Secrecy Polynomial . . . . . . . . . . . . . . . . . . . 50 6.2.2 Challenges from Protocol Designs . . . . . . . . . . . 53 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57787428 bytesapplication/pdfen-US資訊隱私高效率演算法安全度量安全計算合作計算data privacyefficient algorithmssecrecy measurementsecrecy computationmulti-party privacy computationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53931/1/ntu-96-R94922010-1.pdf