資訊安全中,針對安全多方計算的問題已經發展了許多解法。其中一派以計 算上安全(Computationally Secure)出發,嘗試對安全計算提出通用性(general)的解 法 , 但 是 這 類 作 法 需 要 的 效 能 甚 鉅 。 另 外 一 派 是 以 資 訊 上 安 全 (Information -theoretically Secure)為前提,透過可信任的第三者公正伺服器來提供亂數資料輔 助實際運作的兩方計算,這個方法雖然需要的效能比前者低,但是擴充成多方計 算會造成設計的複雜度變高,一般實際的安全多方運用不見得需要這麼完整的解 法。 為了進一步推廣安全多方計算的運用,需要一個設計上較簡單,執行效率較 高,在處理常用的安全多方計算時能套用或擴充的模型 (model),我們利用加法分 持的概念設計了一個安全多方應用程式的模型,適合解決保障隱私的選舉投票的 類似問題,並以安全會議排程為例,闡述如何考量安全多方計算的需求來應用這 個模型。 / Secure multiparty computation (SMC) allows several untrusting parties to conduct certain computations over their private data jointly without compromising their privacy. Since Yao's pioneer work on secure two-party computation, there have been many proposals of protocols for specific problems as well as of general approaches for secure protocol development. However, those proposals, though general, are all very complex and take a lot of computation resources, thus making people consider them impractical for real-world applications. This thesis focuses on a simple approach to secure multiparty computation, namely additive secret sharing, and presents a framework for developing some real-world applications using it. We argue that, although this approach can solve only a limited scope of SMC problems, it is easy to apply and is computationally efficient. Besides showing some typical examples supported by our framework, we have developed a secure meeting time scheduler to demonstrate the feasibility of this approach.

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

資訊安全的研究裡，運用安全多方計算的方法，可使得多方在不洩漏各自私有資訊的條件下完成某種函式的計算。其中一種做法是利用scalar product來當作計算的基礎演算邏輯單元，並進而建構其他更複雜的安全多方計算。 根據目前現有的安全多方運算協定，可再加以定義出一些基本的運算規則，像是一般的程式語言中常用到的變數型態，如整數、浮點數、布林值，我們可定義出安全的秘密資料形態來，並且要能達到算數計算就必須擁有數值處理的能力，如基本的四則運算等，所以提供了相關聯的安全計算協定。根據安全多方計算的運算平台，可具有處理算術計算的能力，使得可處理一般安全計算的問題。 我們並提供一個script轉譯工具，使得使用者可自行撰寫自己的安全多方計算程式，並可利用此工具來自動將使用者寫的程式碼轉成安全多方運算平台可接受的程式碼，如此一來，解決安全多方計算的問題將會變得更為容易。 / Protocols for secure multi-party computation (SMC) allow participants to share a computation while each party learns only what can be inferred from their own inputs and the output of the computation. This thesis concerns the implementation SMC using of a set of information theoretically secure protocols based on scalar product protocol. This main characteristic of this approach is taking the scalar product computation as the basic building, and then use it to construct more complex computation protocols. We developed an SMC implementation framework for both integers and floating numbers which comprises a set of arithmetic operations that manipulate secret values among involved parties using the scalar product protocol as the basis. Such a library of arithmetic operations is call building blocks. Besides, to ease the writing of more complex user-defined protocols, we developed a simple scripting language and a translation tool that converts user script code to SMC code, which is code composed of the building blocks we developed.

安全多方計算是資訊安全研究裡的一個重要主題，其概念為多方在不洩漏各自私有資訊下能一起完成某種函式的計算。在安全多方計算研究領域裡，有一種作法是以scalar product來當作計算的基礎演算邏輯單元，重而建構其他更複雜的安全多方計算。本論文首先針對scalar product發展一套平行性實作架構，藉此我們再實作出多個不同演算法之comparison計算，其中包含了循序演算法以及平行演算法。我們透過實驗來找出適當的平行計算基礎架構與影響執行時間效能的主要因子，並以執行時間效能上的分析來推導相關時間公式。由上述實證研究我們對於不同演算法之comparison計算來作執行時間效能的預測，從實驗結果可以得知我們推導出來之時間公式極為準確，希望能給予使用者在執行comparison計算有所考量，使其在不同執行環境執行comparison計算能有最佳的執行時間效能。 / Loosely speaking, secure multi-party computation (SMC) involves computing functions with inputs from two or more parties in a distributed network while ensuring that no additional information, other than what can be inferred from each participant’s input and output, is revealed to parties not privy to that information. This thesis concerns the parallel implementation of SMC using a scalar-product (SP) based approach. In this approach, SP is considered as the basic building block for constructing more complex SMC. My thesis first develops a concurrent architecture for implementing two-party scalar product computation. Then it implements several algorithms of secure comparison. Finally, a series of experiments are conducted to collect performance statistics for building time functions that can predict the execution time of comparison computation based on that of the scalar product and other parameters, such as CPU core numbers. From the experimental results, we find that these time functions are very accurate. Hence we argue that these time functions can assist users to obtain the better runtime performance for comparison protocols under their specific execution environments.

安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此設計出來的函數算法，稱為安全的多方計算協定(protocol)。 過去兩年本實驗室根據一套基於向量內積運算(scalar product)發展出的安全多方計算方法，設計了一個雛型的分散式系統框架，開發了一套符合其安全要求的常用算數運算函數庫。 但目前個別的應用問題在此系統上發展安全協定的程式時，使用者必須相當熟悉其架構與程式庫細節，才能開發所需程式，造成推廣上的障礙。有鑑於此，本論文採用領域專屬語言(domain-specific language)的方法與技術，針對一般安全多方協定程式的特徵來進行歸納與分析，找出協助其表達計算步驟的適當抽象機制，並在設計上訂定了以下目標： 1. 設計一高階語言用以描述多方安全計算，以提供使用者撰寫安全多方計算程式。 2. 檢查並確保使用者撰寫的程式不會有資訊洩漏。 3. 多方安全運算執行上能保持一定的效率。 4. 建立多方安全計算的運算流程，讓PDL與現有的運作環境配合，達到各伺服器合作運行多方安全計算的目的。 朝向這四個目標發展出一套協定描述語言與其編譯器。以便與SMC-Protocol以及其環境合作，協助領域專家以更簡便的方式來設計與實驗更多的安全多方協定。我們稱此語言為多方安全計算協定描述語言(Protocol Description Language, PDL)。 / Protocols for secure multi-party computation (SMC) allow participants to share a computation while each party learns only what can be inferred from their own inputs and the output of the computation. In the past two years, we developed an SMC implementation framework for both integers and floating numbers which comprises a set of arithmetic operations that manipulate secret values among involved parties using the scalar product protocol as the basis. Such a library of arithmetic operations is call building blocks. But using this library is not easy. To solve individual SMC problem, programmer should knowing the given framework and protocol detail very well. This difficulty makes them won't consider this framework while facing the need of SMC. To ease the writing of more complex user-defined protocols, using the technique of domain-specific language, this thesis analysis the general needs of SMC, develop a domain-specific language of SMC, and implement a compiler that coverts this language to SMC code, which is executable code composed of the protocols of given framework. We called this language Protocol Description Language, PDL.